Basic Concepts of Graph

What is a graph?
• A data structure that consists of a set of nodes or vertices and a set of edges that relate the nodes to each other
• The set of edges describes relationships among the vertices

Undirected graphs
• When the edges in a graph have no direction, the graph is
called undirected

Directed Graph

When the edges in a graph have a direction, the graph is called directed graph.

Graph Representation
Vertices can be represent as one dimensional array.
Graph edges are commonly represented in two ways:

1. Adjacency Matrix
An adjacency matrix is 2D array of V x V vertices. Each row and column represent a vertex.
If the value of any element a[i][j] is 1, it represents that there is an edge connecting vertex i and vertex j.

2. Adjacency List
Adjacency list is a collection of unordered lists used to represent a finite graph.

Graph terminology
Complete graph: A graph in which every vertex is directly connected to every other vertex.