### Graphs

‘Graph’ is an ‘abstract data type’ which is used to implement ‘undirected graph’ and ‘directed graph’ concepts from mathematics.

Graph consists of finite set of ‘vertices (nodes)’ and interconnecting ‘edges’ to them. For undirected graph, edges are undirected too. And for directed graph, edges are directed. Each vertex is associated with a values called ‘vertex value’. A values can be associated with edges called as ‘edge value’.

Graph operations
Following are the operations that can be performed on a graph:
 Operation Function format Explanation Adjacent (G, x, y) Check if x and y vertices in graph G are adjacent. Neighbors (G, x) List all the neighbor-vertices of vertex x in graph G Add vertex (G, x) Add vertex x in graph G, if it is not there. Remove vertex (G, x) Remove vertex x from graph G, if it is there. Add edge (G, x, y) Add edge in between vertices x and y in graph G, if it is not there. Remove edge (G, x, y) Remove edge in between vertices x and y in graph G, if it is there. Get vertex value (G, x) Get values of vertex x in graph G. Set vertex value (G, x, v) Set values of vertex x in graph G. Get edge value (G, x, y) Get value of edge in between x and y in graph G, if edges have value. Set edge value (G, x, y, v) Set value of edge in between x and y in graph G, if edges have value.

Graph representation

Graph is represented by following methods:

Adjacency List representation of graph is a collection of mapping of each vertex and the list of neighboring vertices to it.

An ‘array of linked lists’ is used to implement Adjacency List as follows:
i. First node of each linked list in this list would represent the vertex for which we are finding adjacent vertices.
ii. Next nodes in each after the first node represents vertices adjacent to the vertex denoted by first node.
iii. Data in first node of the linked is considered as the weight of that node.
iv. Data in rest of the nodes of the linked list is considered as the weight of that edge.

Adjacency List for above graph would be:

This allows to store following information:
ii. Data on edges
iii. Cost of an edge

We cannot store the direction of an edge using this method.

Adjacency matrix is 2-D matrix where rows represent the vertices and columns represent destination vertices. Data on edge and vertices must be stored externally. Only cost of one edge is stored for each pair of vertices. We cannot store direction of an edge using this method.

Adjacency Matrix can be represented using 2D arrays as follows:

 10 20 30 40 50 60 10 0 7 5 0 0 0 20 7 0 6 0 4 0 30 5 6 0 12 0 0 40 0 0 12 0 10 9 50 0 4 0 10 0 0 60 0 0 0 9 0 0
Following are the time complexities required to perform general operations on graphs using above mentioned graph representations:

Graph traversal

For Graph traversal, we keep track whether that vertex is visited or not. Consider following graph.
Matrix representation of this graph would be:

Matrix representation of this graph would be:

 1 2 3 4 5 6 1 0 7 5 0 0 0 2 7 0 6 0 4 0 3 5 6 0 12 0 0 4 0 0 12 0 10 9 5 0 4 0 10 0 0 6 0 0 0 9 0 0

Following are the methods for graph traversal:

Breadth First Search traversal algorithm for graphs starts with given node and traverses neighboring vertex first and then traverses child vertex. It uses ‘queue’ for this purpose. This algorithm is used to find the shortest path from one vertex to another in a graph.

In BFS, initially all vertices are marked as ‘non-visited’. We mark them as ‘visited’ as soon as we visit them. Whenever we process a vertex, we add each of its neighboring vertex onto a queue. Once that vertex is processed, we remove next vertex from queue and process it in a same way.

If we take first vertex i.e. root = 2, BFS algorithm should traverse graph as per follows:

Result of BFS traversal is: 2 1 3 5 4 6

2. Depth First Search (DFS)
Depth First Search (DFS) traversal algorithm for Graphs is similar to that for Trees. It starts with given node, traverses first sub-tree starting with this node, and then traverses other sub-tree and goes on. DFS can be implemented using ‘recursion’.

In DFS, we mark each vertex that we visit as ‘visited’. As soon as we find non-visited vertex, we start traversing its child node. It means, a child vertex of a given vertex is traversed before its sibling vertex. DFS method requires less memory compared to BFS method.

If we take first vertex i.e. root = 2, DFS algorithm should traverse graph as per follows:

Result of DFS traversal is: 2 1 3 4 5 6

Creating Adjacency Matrix & BFS and DFS traversal of graph using C
Above graph example is only taken to execute implementation of Adjacency matrix creation and BFS and DFS traversal of graph.

 Code:   #include "stdio.h" #define visited 1 #define not_visited 0   /*Add edge between vertices verA and verB with weight*/ void Add_Edge(int adjM[][20], int verA, int verB, int weight){                 adjM[verA][verB] = weight;                 adjM[verB][verA] = weight;                 printf("\nEdge %d-%d is added to Graph.", verA, verB);                 }   void Drawline(int n){                 printf("\n");                 int i;                 for(i=0; i