Graphs
Basics to be understood before getting into C program:
Adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements
of the matrix indicate whether pairs of vertices are adjacent or not in the
graph.
Adjacency
Matrix is a 2D array of size V x V where V is the number of vertices in a
graph.
The
adjacency matrix, sometimes also called the connection matrix, of a simple
labeled graph is a matrix with rows and columns labeled by graph vertices,
with a 1 or 0 in position according to
whether 
and 
are adjacent or not. For a simple graph with no self-loops, the adjacency matrix must have 0s on the diagonal. For an undirected graph, the adjacency matrix is symmetric.
and are adjacent or not. For a simple graph with no self-loops, the adjacency matrix must have 0s on the diagonal. For an undirected graph, the adjacency matrix is symmetric.
The illustration above shows adjacency matrices
for particular labeling of the claw graph, cycle graph 
, and complete graph .
, and complete graph .
Kinds of Graphs
Various
flavors of graphs have the following specializations and particulars about how
they are usually drawn.
·
Undirected
Graphs.
In
an undirected graph, the order of the vertices in the pairs in the Edge set
doesn't matter. Thus, if we view the sample graph above we could have written
the Edge set as {(4,6),(4,5),(3,4),(3,2),(2,5)),(1,2)),(1,5)}. Undirected
graphs usually are drawn with straight lines between the vertices.
The adjacency relation is symmetric in
an undirected graph, so if u ~ v then
it is also the case
that v ~ u.
·
Directed Graphs.
In
a directed graph the order of the vertices in the pairs in the edge set
matters. Thus u is adjacent to v only if the pair (u,v) is in the Edge set. For
directed graphs we usually use arrows for the arcs between vertices. An arrow
from u to v is drawn only if (u,v) is in the Edge set. The directed graph below.
Graphs, adjacency matric and C
Programming
Graph
Adjacency Matrix [derived from above graph]
A Graph can be represented in 2 ways
1. 2 Dimension array a[i][j] ---> Memory requirement:Adjacency matrix representation of a graph wastes
lot of memory space.
2. Array of linked list [which is represented below]
Array of linked list [derived from
above adjacency matrix]
C program
/**********************************************************************
* A C Program to demonstrate adjacency list representation of graphs
**********************************************************************/
#include <stdio.h>
#include <stdlib.h>
/* A structure to represent an adjacency list node
* EACH NODE IN THE ADJACENCY LIST
*/
struct adj_list_node
{
int dest;
struct adj_list_node* next;
};
/* A structure to represent an adjacency list
* THE 1ST NODE IN THE ROW LINKED LIST I.E ADJACENCY LIST.
*/
struct adj_list
{
struct adj_list_node *head;
};
/* A structure to represent a graph. A graph
* is an array of adjacency lists.
* Size of array will be v (number of vertices
* in graph)
*/
struct graph_ds
{
int v;
struct adj_list* array;
};
/*******************************************************************
* A utility function to create a new adjacency list node
* i.e. create a new node in each adjacency list. The next pointer
* of the last node in the adjacency list is made to point to NULL.
******************************************************************/
struct adj_list_node* newadj_list_node(int dest)
{
struct adj_list_node* new_node =
(struct adj_list_node*) malloc(sizeof(struct adj_list_node));
new_node->dest = dest;
new_node->next = NULL;
return new_node;
}
/************************************************************
* Creates a graph of v vertices
************************************************************/
struct graph_ds* create_graph(int v)
{
/* Allocate memory for graph data structure */
struct graph_ds* graph =
(struct graph_ds*) malloc(sizeof(struct graph_ds));
graph->v = v;
/* Create an array of adjacency lists. Allocate
* memory for the 1st node each of the adjacency list
* rows.
* The 1st nodes in each adjacency list together form
* the array.
* Size of array will be v
*/
graph->array =
(struct adj_list*) malloc(v * sizeof(struct adj_list));
/* Initialize each adjacency list as empty by
* making head as NULL. The head pointer of 1st node
* in each adjacency list(row) is made to point to
* NULL.
*/
int i;
for (i = 0; i < v; ++i)
graph->array[i].head = NULL;
return graph;
}
/* Adds an edge to an undirected graph */
void add_edge(struct graph_ds* graph, int src, int dest)
{
/*
* Add an edge from src to dest. A new node is
* added to the adjacency list of src. The node
* is added at the begining.
*/
printf("Add edge start\n");
struct adj_list_node* new_node = newadj_list_node(dest);
/* From the Linked listed Array, choose the row linked list corresponding
* to index of the array which is equal to "src".
* Initially, Graph's Row Head pointer[src] points to NULL or current
* node [old destination node, which has connection to the src node].
* 'or'
* When new node (new destination node which also has connection to source
* node) is added, new_node next is made to point to current node.
* Here, current node is the old dest node connected to src.
* Then, update Graph's Row head pointer to point to new node.
* i.e.
* Direction of addition of new node. [right to left]
* [graph's row Head pointer]
* ^
* |
* |
* [new_node]--->[current_node]--->[old_node]-->[old_node]---> NULL
*/
new_node->next = graph->array[src].head;
printf("new_node->dest :%d\n", new_node->dest);
graph->array[src].head = new_node;
printf("to index graph->array[%d].head->dest ---> add: %d\n",
src, graph->array[src].head->dest);
/*****************************************************************
* Since graph is undirected i.e symmetrix adjacent matrix,
* do the above for row Head pointer in linked list array whose
* index is "dest".
* i.e. New_node's next points to the current node connected to
* dest. Update the row head pointer to point to the new node.
*
* Now, we have achieved A-->B and B-->A symmetry, in the graph.
*****************************************************************/
new_node = newadj_list_node(src);
new_node->next = graph->array[dest].head;
graph->array[dest].head = new_node;
printf("to index graph->array[%d].head->dest ---> add: %d\n",
dest, graph->array[dest].head->dest);
printf("Add edge [%d <-----> %d] complete\n", src, dest);
}
/*
* Print the adjacency list representation of graph.
*/
void print_graph(struct graph_ds* graph)
{
int v;
for (v = 0; v < graph->v; ++v)
{
struct adj_list_node* vertex_header = graph->array[v].head;
printf("\n Adjacency list of vertex %d\n head ", v);
while (vertex_header)
{
printf("-> %d", vertex_header->dest);
vertex_header = vertex_header->next;
}
printf("\n");
}
}
/******************************************************************
input: Create edges
0 --> 1 ,0 --> 4,
1 --> 2, 1 --> 3, 1 --> 4,
2 --> 3,
3 --> 4
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Adjacency Matrix representation of above.
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
0 1 2 3 4
###############
0 # 0 1 0 0 1 ----> vertex 0 is connected to vertex 4 and 1.
1 # 1 0 1 1 1 ----> vertex 1 is connected to vertex 0, 2, 3 and 4.
2 # 0 1 0 1 0 ----> vertex 2 is connected to vertex 1 and 3.
3 # 0 1 1 0 1 ----> vertex 3 is connected to vertex 1, 2 and 4.
4 # 1 1 0 1 0 ----> vertex 4 is connected to vertex 0, 1 and 3.
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Adjacency Linked list is the memory efficient way of
representing the graphs.
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
output:
Adjacency list of vertex 0
head -> 4-> 1
Adjacency list of vertex 1
head -> 4-> 3-> 2-> 0
Adjacency list of vertex 2
head -> 3-> 1
Adjacency list of vertex 3
head -> 4-> 2-> 1
Adjacency list of vertex 4
head -> 3-> 1-> 0
******************************************************************/
/* Main program to test the above functions */
int main()
{
/* create the graph given in above figure. i.e. 5 vertices */
int v = 5;
/* Now, create graph */
struct graph_ds* graph = create_graph(v);
add_edge(graph, 0, 1);
add_edge(graph, 0, 4);
add_edge(graph, 1, 2);
add_edge(graph, 1, 3);
add_edge(graph, 1, 4);
add_edge(graph, 2, 3);
add_edge(graph, 3, 4);
/* print the adjacency list representation of the above graph */
print_graph(graph);
return 0;
}
* A C Program to demonstrate adjacency list representation of graphs
**********************************************************************/
#include <stdio.h>
#include <stdlib.h>
/* A structure to represent an adjacency list node
* EACH NODE IN THE ADJACENCY LIST
*/
struct adj_list_node
{
int dest;
struct adj_list_node* next;
};
/* A structure to represent an adjacency list
* THE 1ST NODE IN THE ROW LINKED LIST I.E ADJACENCY LIST.
*/
struct adj_list
{
struct adj_list_node *head;
};
/* A structure to represent a graph. A graph
* is an array of adjacency lists.
* Size of array will be v (number of vertices
* in graph)
*/
struct graph_ds
{
int v;
struct adj_list* array;
};
/*******************************************************************
* A utility function to create a new adjacency list node
* i.e. create a new node in each adjacency list. The next pointer
* of the last node in the adjacency list is made to point to NULL.
******************************************************************/
struct adj_list_node* newadj_list_node(int dest)
{
struct adj_list_node* new_node =
(struct adj_list_node*) malloc(sizeof(struct adj_list_node));
new_node->dest = dest;
new_node->next = NULL;
return new_node;
}
/************************************************************
* Creates a graph of v vertices
************************************************************/
struct graph_ds* create_graph(int v)
{
/* Allocate memory for graph data structure */
struct graph_ds* graph =
(struct graph_ds*) malloc(sizeof(struct graph_ds));
graph->v = v;
/* Create an array of adjacency lists. Allocate
* memory for the 1st node each of the adjacency list
* rows.
* The 1st nodes in each adjacency list together form
* the array.
* Size of array will be v
*/
graph->array =
(struct adj_list*) malloc(v * sizeof(struct adj_list));
/* Initialize each adjacency list as empty by
* making head as NULL. The head pointer of 1st node
* in each adjacency list(row) is made to point to
* NULL.
*/
int i;
for (i = 0; i < v; ++i)
graph->array[i].head = NULL;
return graph;
}
/* Adds an edge to an undirected graph */
void add_edge(struct graph_ds* graph, int src, int dest)
{
/*
* Add an edge from src to dest. A new node is
* added to the adjacency list of src. The node
* is added at the begining.
*/
printf("Add edge start\n");
struct adj_list_node* new_node = newadj_list_node(dest);
/* From the Linked listed Array, choose the row linked list corresponding
* to index of the array which is equal to "src".
* Initially, Graph's Row Head pointer[src] points to NULL or current
* node [old destination node, which has connection to the src node].
* 'or'
* When new node (new destination node which also has connection to source
* node) is added, new_node next is made to point to current node.
* Here, current node is the old dest node connected to src.
* Then, update Graph's Row head pointer to point to new node.
* i.e.
* Direction of addition of new node. [right to left]
* [graph's row Head pointer]
* ^
* |
* |
* [new_node]--->[current_node]--->[old_node]-->[old_node]---> NULL
*/
new_node->next = graph->array[src].head;
printf("new_node->dest :%d\n", new_node->dest);
graph->array[src].head = new_node;
printf("to index graph->array[%d].head->dest ---> add: %d\n",
src, graph->array[src].head->dest);
/*****************************************************************
* Since graph is undirected i.e symmetrix adjacent matrix,
* do the above for row Head pointer in linked list array whose
* index is "dest".
* i.e. New_node's next points to the current node connected to
* dest. Update the row head pointer to point to the new node.
*
* Now, we have achieved A-->B and B-->A symmetry, in the graph.
*****************************************************************/
new_node = newadj_list_node(src);
new_node->next = graph->array[dest].head;
graph->array[dest].head = new_node;
printf("to index graph->array[%d].head->dest ---> add: %d\n",
dest, graph->array[dest].head->dest);
printf("Add edge [%d <-----> %d] complete\n", src, dest);
}
/*
* Print the adjacency list representation of graph.
*/
void print_graph(struct graph_ds* graph)
{
int v;
for (v = 0; v < graph->v; ++v)
{
struct adj_list_node* vertex_header = graph->array[v].head;
printf("\n Adjacency list of vertex %d\n head ", v);
while (vertex_header)
{
printf("-> %d", vertex_header->dest);
vertex_header = vertex_header->next;
}
printf("\n");
}
}
/******************************************************************
input: Create edges
0 --> 1 ,0 --> 4,
1 --> 2, 1 --> 3, 1 --> 4,
2 --> 3,
3 --> 4
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Adjacency Matrix representation of above.
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
0 1 2 3 4
###############
0 # 0 1 0 0 1 ----> vertex 0 is connected to vertex 4 and 1.
1 # 1 0 1 1 1 ----> vertex 1 is connected to vertex 0, 2, 3 and 4.
2 # 0 1 0 1 0 ----> vertex 2 is connected to vertex 1 and 3.
3 # 0 1 1 0 1 ----> vertex 3 is connected to vertex 1, 2 and 4.
4 # 1 1 0 1 0 ----> vertex 4 is connected to vertex 0, 1 and 3.
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Adjacency Linked list is the memory efficient way of
representing the graphs.
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
output:
Adjacency list of vertex 0
head -> 4-> 1
Adjacency list of vertex 1
head -> 4-> 3-> 2-> 0
Adjacency list of vertex 2
head -> 3-> 1
Adjacency list of vertex 3
head -> 4-> 2-> 1
Adjacency list of vertex 4
head -> 3-> 1-> 0
******************************************************************/
/* Main program to test the above functions */
int main()
{
/* create the graph given in above figure. i.e. 5 vertices */
int v = 5;
/* Now, create graph */
struct graph_ds* graph = create_graph(v);
add_edge(graph, 0, 1);
add_edge(graph, 0, 4);
add_edge(graph, 1, 2);
add_edge(graph, 1, 3);
add_edge(graph, 1, 4);
add_edge(graph, 2, 3);
add_edge(graph, 3, 4);
/* print the adjacency list representation of the above graph */
print_graph(graph);
return 0;
}
Output
Neelkanth $:./a.out
Add edge start
new_node->dest :1
to index graph->array[0].head->dest ---> add: 1
to index graph->array[1].head->dest ---> add: 0
Add edge [0 <-----> 1] complete
Add edge start
new_node->dest :4
to index graph->array[0].head->dest ---> add: 4
to index graph->array[4].head->dest ---> add: 0
Add edge [0 <-----> 4] complete
Add edge start
new_node->dest :2
to index graph->array[1].head->dest ---> add: 2
to index graph->array[2].head->dest ---> add: 1
Add edge [1 <-----> 2] complete
Add edge start
new_node->dest :3
to index graph->array[1].head->dest ---> add: 3
to index graph->array[3].head->dest ---> add: 1
Add edge [1 <-----> 3] complete
Add edge start
new_node->dest :4
to index graph->array[1].head->dest ---> add: 4
to index graph->array[4].head->dest ---> add: 1
Add edge [1 <-----> 4] complete
Add edge start
new_node->dest :3
to index graph->array[2].head->dest ---> add: 3
to index graph->array[3].head->dest ---> add: 2
Add edge [2 <-----> 3] complete
Add edge start
new_node->dest :4
to index graph->array[3].head->dest ---> add: 4
to index graph->array[4].head->dest ---> add: 3
Add edge [3 <-----> 4] complete
Adjacency list of vertex 0
head -> 4-> 1
Adjacency list of vertex 1
head -> 4-> 3-> 2-> 0
Adjacency list of vertex 2
head -> 3-> 1
Adjacency list of vertex 3
head -> 4-> 2-> 1
Adjacency list of vertex 4
head -> 3-> 1-> 0
Add edge start
new_node->dest :1
to index graph->array[0].head->dest ---> add: 1
to index graph->array[1].head->dest ---> add: 0
Add edge [0 <-----> 1] complete
Add edge start
new_node->dest :4
to index graph->array[0].head->dest ---> add: 4
to index graph->array[4].head->dest ---> add: 0
Add edge [0 <-----> 4] complete
Add edge start
new_node->dest :2
to index graph->array[1].head->dest ---> add: 2
to index graph->array[2].head->dest ---> add: 1
Add edge [1 <-----> 2] complete
Add edge start
new_node->dest :3
to index graph->array[1].head->dest ---> add: 3
to index graph->array[3].head->dest ---> add: 1
Add edge [1 <-----> 3] complete
Add edge start
new_node->dest :4
to index graph->array[1].head->dest ---> add: 4
to index graph->array[4].head->dest ---> add: 1
Add edge [1 <-----> 4] complete
Add edge start
new_node->dest :3
to index graph->array[2].head->dest ---> add: 3
to index graph->array[3].head->dest ---> add: 2
Add edge [2 <-----> 3] complete
Add edge start
new_node->dest :4
to index graph->array[3].head->dest ---> add: 4
to index graph->array[4].head->dest ---> add: 3
Add edge [3 <-----> 4] complete
Adjacency list of vertex 0
head -> 4-> 1
Adjacency list of vertex 1
head -> 4-> 3-> 2-> 0
Adjacency list of vertex 2
head -> 3-> 1
Adjacency list of vertex 3
head -> 4-> 2-> 1
Adjacency list of vertex 4
head -> 3-> 1-> 0