In this article, we’ll touch upon the graph theory basics. Graph Theory is a branch of mathematics that aims at studying problems related to a structure called a Graph.
In this article, we will try to understand the basics of Graph Theory, and also touch upon a C programmer’s perspective for representing such problems.
What is a Graph?
A Graph is a structure that consists of a set of nodes/vertices that map to a set of edges. How do they map together?
Well, the words themselves give you a hint. A node/vertex is a point on the graph, and edges join two vertices together, through a line segment. We represent an edge joining a pair of vertices by => edge = (u, v)
The below figure represents a Graph having 3 vertices and 2 edges. We don’t need to connect all the vertices together in a graph.
Now that you know what a Graph is, let’s look at the types of Graphs.
Types of Graphs
The highest level of demarcation is based on the direction.
That is, there are two types of graphs based on this category: Undirected and Directed.
Undirected Graph
An undirected graph is a graph where every edge is represented as an unordered pair e = (1, 2). This means that the order doesn’t matter to us, since (1, 2) is the same as (2, 1).
All graphs which do not have an arrow between vertices are called Undirected Graphs.
Directed Graph
A directed graph is a graph where every edge is directed (unidirectional). This means that the edges e1 = (1, 2) and e2 = (2, 1) are different.
They represent oppositely directed edges between 1 and 2.
We represent any connection by an arrow mark to show the direction of the edge.
These are the two major types of Graphs, which themselves have different divisions. We will continue to cover this topic as we go along in the future.
Weighted Graphs
There is one more type of graph, called a Weighted Graph, which we use in a lot of problems.
This is simply any directed/undirected graph with each edge having a weight/cost associated with it.
Now that we know the basics of graphs, let us look at the implementation of these graphs in C.
Implementation of Graphs
There are two ways of implementing a graph.
- Adjacency Matrix
- Adjacency List
Using Adjacency Matrices
An Adjacency Matrix adj is a matrix where:
- adj[i][j] = 1 if (i, j) has an edge connecting them
- adj[i][j] = 0 otherwise
This has the advantage of an O(1) time complexity for searching and updating values, but has a space complexity of O(n^2).
For the directed graph below, let’s figure out the adjacency matrix.
We denote the matrix to have the element adj[i][j] = 1 only if there is a directed edge from i to j.
Constructing the matrix is very simple, so let’s quickly look at an example in C. Here, we implement the adjacency matrix as a 2D-array.
The implementation is as below. Code is self-explanatory for anyone familiar with C programming and pointers.
/**
Code for https://journaldev.com article
Purpose: Adjacency Matrix representation of a Graph
@author: Vijay Ramachandran
@date: 10-02-2020
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct Graph Graph;
struct Graph {
// Number of vertices
int v;
// Adjacency Matrix
int** adj;
};
int** init_adjacency_matrix(Graph g) {
// Initializes an adjacency matrix for the graph
if (g.adj)
return g.adj;
// Allocates memory for the matrix
// and sets every element to 0
int** matrix = (int**) calloc (g.v, sizeof(int*));
for (int i=0; i<g.v; i++) {
matrix[i] = (int*) calloc (g.v, sizeof(int));
}
g.adj = matrix;
printf("Initialized Adjacency Matrix!n");
return matrix;
}
void free_matrix(Graph g) {
// Free the adjacency matrix
if (!g.adj)
return;
for (int i=0; i<g.v; i++)
free(g.adj[i]);
free(g.adj);
}
void add_edge(Graph g, int i, int j) {
// Adds an edge connecting two vertices i and j
if (!g.adj) {
fprintf(stderr, "Adjacency Matrix not initialized!n");
exit(1);
}
else if (i > g.v || j > g.v) {
fprintf(stderr, "Invalid Vertex Numbern");
exit(1);
}
g.adj[i-1][j-1] = 1;
}
void remove_edge(Graph g, int i, int j) {
// Sets the edge from i to j as zero
if (!g.adj) {
fprintf(stderr, "Adjacency Matrix not initialized!n");
exit(1);
}
else if (i > g.v || j > g.v) {
fprintf(stderr, "Invalid Vertex Numbern");
exit(1);
}
g.adj[i-1][j-1] = 0;
}
int check_if_exists(Graph g, int i, int j) {
// Checks if there is an edge from vertex i to j
if (!g.adj) {
fprintf(stderr, "Adjacency Matrix not initialized!n");
exit(1);
}
else if (i > g.v || j > g.v) {
fprintf(stderr, "Invalid Vertex Numbern");
return 0;
}
return g.adj[i-1][j-1];
}
int main() {
// Graph with 4 vertices
Graph g = {4, NULL};
printf("Created a Graph Structure with %d verticesn", g.v);
g.adj = init_adjacency_matrix(g);
// Let's connect the 4 vertices using 6 edges
add_edge(g, 1, 2);
add_edge(g, 2, 1);
add_edge(g, 2, 3);
add_edge(g, 2, 4);
add_edge(g, 3, 1);
add_edge(g, 4, 3);
// Check if the edge is connected
printf("Is there an edge from 1 to 2?n");
if (check_if_exists(g, 1, 2))
printf("Yesn");
else
printf("Non");
printf("Is there an edge from 4 to 3?n");
if (check_if_exists(g, 4, 3))
printf("Yesn");
else
printf("Non");
printf("Is there an edge from 1 to 3?n");
if (check_if_exists(g, 1, 3))
printf("Yesn");
else
printf("Non");
free_matrix(g);
return 0;
}
Output
Created a Graph Structure with 4 vertices Initialized Adjacency Matrix! Is there an edge from 1 to 2? Yes Is there an edge from 4 to 3? Yes Is there an edge from 1 to 3? No
The problem is that we always need to use O(n^2) elements for storage, and hence, we often use adjacency lists to represent graphs.
Using Adjacency Lists
An Adjacency List is a list that can be used to represent connected vertices.
The idea is to store a linked list for vertex, that consists of all vertices which are directly connected to it.
We can implement this using an array of linked lists.
A simple implementation in C is given below.
/**
Code for https://journaldev.com article
Purpose: Adjacency List representation of a Graph
@author: Vijay Ramachandran
@date: 10-02-2020
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct Graph Graph;
typedef struct Node Node;
struct Node {
// To represent the linked list node.
// Contains the vertex index
int vertex;
// And a pointer to the next element in the linked list
Node* next;
};
struct Graph {
// Number of vertices
int v;
// Array of Adjacency Lists
Node** adj_lists;
};
Node** init_adjacency_lists(Graph g) {
// Initializes an adjacency matrix for the graph
if (g.adj_lists)
return g.adj_lists;
// Allocates memory for the lists
// There is a list for every vertex in the graph
// which means there are g.v adjacent lists
Node** adj_lists = (Node**) calloc (g.v, sizeof(Node*));
// Set them to NULL initially
for (int i = 0; i < g.v; i++)
adj_lists[i] = NULL;
printf("Initialized Adjacency Lists!n");
return adj_lists;
}
void free_list(Node* list) {
// Frees all nodes in the list, headed by 'list'
Node* temp = list;
while(temp) {
Node* rm_node = temp;
temp = rm_node->next;
rm_node->next = NULL;
free(rm_node);
}
}
void free_adj_lists(Graph g) {
// Free the adjacency matrix
if (!g.adj_lists)
return;
for (int i=0; i<g.v; i++)
free_list(g.adj_lists[i]);
free(g.adj_lists);
}
void print_list(Node* list) {
// Prints the linked list
Node* temp = list;
while(temp) {
printf("Node: %d -> ", temp->vertex);
temp = temp->next;
}
printf("n");
}
Node* create_node(int vertex) {
// Creates a LinkedList node to hold the vertex
Node* node = (Node*) calloc (1, sizeof(Node));
node->next = NULL;
node->vertex = vertex;
return node;
}
void add_edge(Graph g, int i, int j) {
// Adds an edge connecting two vertices i and j
if (!g.adj_lists) {
fprintf(stderr, "Adjacency Lists not initialized!n");
exit(1);
}
else if (i > g.v || j > g.v) {
fprintf(stderr, "Invalid Vertex Numbern");
exit(1);
}
// Create the new node in the souce vertex
// adjacency list and add the destination
// vertex to it
// Create a node containing the dst vertex index
Node* node = create_node(j);
// Insert at the source list
// Let's insert at the top, since it doesn't
// matter whether we insert at the head or not
node->next = g.adj_lists[i-1];
// Make the new node as the head
g.adj_lists[i-1] = node;
}
void remove_edge(Graph g, int i, int j) {
// Sets the edge from i to j as zero
if (!g.adj_lists) {
fprintf(stderr, "Adjacency Lists not initialized!n");
exit(1);
}
else if (i > g.v || j > g.v) {
fprintf(stderr, "Invalid Vertex Numbern");
exit(1);
}
// Search for vertex j in i's adjacency list
Node* temp = g.adj_lists[i-1];
if (!temp) {
return;
}
if (!(temp->next)) {
if (temp->vertex == j) {
free(temp);
g.adj_lists[i-1] = NULL;
}
return;
}
while (temp->next) {
if (temp->vertex == j) {
// We have found an edge! Remove this element.
Node* rm_node = temp;
temp->next = rm_node->next;
rm_node->next = NULL;
free(rm_node);
return;
}
temp = temp->next;
}
// No element found :(
return;
}
int check_if_exists(Graph g, int i, int j) {
// Checks if there is an edge from vertex i to j
if (!g.adj_lists) {
fprintf(stderr, "Adjacency Lists not initialized!n");
exit(1);
}
else if (i > g.v || j > g.v) {
fprintf(stderr, "Invalid Vertex Numbern");
return 0;
}
// Search for vertex j in i's adjacency list
Node* temp = g.adj_lists[i-1];
if (!temp) {
return 0;
}
if (!(temp->next)) {
if (temp->vertex == j) {
return 1;
}
return 0;
}
while (temp->next) {
if (temp->vertex == j) {
// We have found an edge! Remove this element.
return 1;
}
temp = temp->next;
}
// No element found :(
return 0;
}
int main() {
// Graph with 4 vertices
Graph g = {4, NULL};
printf("Created a Graph Structure with %d verticesn", g.v);
g.adj_lists = init_adjacency_lists(g);
// Let's connect the 4 vertices using edges
add_edge(g, 1, 2);
add_edge(g, 2, 1);
add_edge(g, 2, 3);
add_edge(g, 2, 4);
add_edge(g, 3, 1);
add_edge(g, 4, 3);
// Check if the edge is connected
printf("Is there an edge from 1 to 2?n");
if (check_if_exists(g, 1, 2))
printf("Yesn");
else
printf("Non");
printf("Is there an edge from 4 to 3?n");
if (check_if_exists(g, 4, 3))
printf("Yesn");
else
printf("Non");
printf("Is there an edge from 1 to 3?n");
if (check_if_exists(g, 1, 3))
printf("Yesn");
else
printf("Non");
printf("nPrinting the Adjacency Lists for every Vertex:n");
for (int i=0; i<g.v; i++) {
printf("Vertex: %d , ", i+1);
print_list(g.adj_lists[i]);
}
free_adj_lists(g);
return 0;
}
Output
Created a Graph Structure with 4 vertices Initialized Adjacency Lists! Is there an edge from 1 to 2? Yes Is there an edge from 4 to 3? Yes Is there an edge from 1 to 3? No Printing the Adjacency Lists for every Vertex: Vertex: 1 , Node: 2 -> Vertex: 2 , Node: 4 -> Node: 3 -> Node: 1 -> Vertex: 3 , Node: 1 -> Vertex: 4 , Node: 3 ->
Conclusion
With that, we have covered the basics of Graph Theory. In the upcoming articles, we will take a look at how we can solve different graph theory problems and their implementation in C.
In the meantime, do go through our latest C Programming articles, which cover differ aspects of C.