# Basics of Graph Theory With Examples [Latest] 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.

• adj[i][j] = 1 if (i, j) has an edge connecting them

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;
};
// Initializes an adjacency matrix for the graph
// 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));
}
return matrix;
}
void free_matrix(Graph g) {
return;
for (int i=0; i<g.v; i++)
}
void add_edge(Graph g, int i, int j) {
// Adds an edge connecting two vertices i and j
exit(1);
}
else if (i > g.v || j > g.v) {
fprintf(stderr, "Invalid Vertex Numbern");
exit(1);
}
}
void remove_edge(Graph g, int i, int j) {
// Sets the edge from i to j as zero
exit(1);
}
else if (i > g.v || j > g.v) {
fprintf(stderr, "Invalid Vertex Numbern");
exit(1);
}
}
int check_if_exists(Graph g, int i, int j) {
// Checks if there is an edge from vertex i to j
exit(1);
}
else if (i > g.v || j > g.v) {
fprintf(stderr, "Invalid Vertex Numbern");
return 0;
}
}
int main() {
// Graph with 4 vertices
Graph g = {4, NULL};
printf("Created a Graph Structure with %d verticesn", g.v);
// Let's connect the 4 vertices using 6 edges
// 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
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.

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;
};
// Initializes an adjacency matrix for the graph
// 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++)
}
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);
}
}
return;
for (int i=0; i<g.v; i++)
}
void print_list(Node* 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
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
// 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
// Make the new node as the head
}
void remove_edge(Graph g, int i, int j) {
// Sets the edge from i to j as zero
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
if (!temp) {
return;
}
if (!(temp->next)) {
if (temp->vertex == j) {
free(temp);
}
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
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
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);
// Let's connect the 4 vertices using edges
// 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);
}
return 0;
}
```

Output

```Created a Graph Structure with 4 vertices
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.