Graph in C
What is a Graph in Data Structures?
A graph is a data structure consisting of various nodes containing data. These nodes connect several other nodes.
![Graph in C](https://static.tutorialandexample.com/c/graph-in-c1.png)
Components of a Graph
- A graph consists of a group of vertices called nodes.
- It also contains edges that join two vertices. The edges are a set of ordered pair in the form of (u, v).
Definition of Graph
A graph G is referred to as an ordered pair G (V, E) in which V (G) is the set of vertices and E (G) is the set of edges used to connect these vertices.
A graph can be compared to a cyclic tree in which the nodes have a relationship among them instead of a parent-child relationship just like in a tree.
Types of Graphs
There are different types of graphs and data structures. They are:
- Directed graph
- Undirected graph
- Weighted graph
- Unweighted graph
Directed graph
The directed graph is also known as a digraph. In this type of graph, the set of objects is connected and the edges are directed from one node to another and donated with the arrows to depict the direction
![Graph in C](https://static.tutorialandexample.com/c/graph-in-c2.png)
Undirected graphs
A type of graph in which the nodes are connected with the bidirectional edges or edges without any direction. Simply, it means that we cannot determine the starting and ending nodes by their edges.
![Graph in C](https://static.tutorialandexample.com/c/graph-in-c3.png)
Weighted Graph
These are the type of graphs which has values on their edges and paths. It is a simple graph but has associated weights on the edges. These weights are used to determine the shortest path in the graphs.
Unweighted Graph
The graphs which have no weights on their edges and nodes are known as unweighted graphs. It only determines the linkage between the nodes and edges.
Terminologies in Graphs
- Path: It is a connection of multiple nodes which is used to reach the final node from the source node.
- Closed Path: A path can be referred to as a closed path if the source node is the destination node which means V0 = Vf.
- Vertex: A node in a graph is known as a vertex.
- Edge: The path between two nodes is called the edge.
- Loop: An edge that is connected to similar endpoints is known as a loop.
- Adjacent Node: If two nodes are connected with the same edge, then these nodes are known as adjacent or neighbor nodes.
- Degree: The degree of nodes is the number of edges connected to the node.
Representation of Graphs
There are two methods to represent and store the graphs:
- Adjacency to the matrix (Sequential representation)
- Adjacency to the linked list (Linked List representation)
1. The Adjacency Matrix Representation
This is also known as the sequential representation. It is used to represent the mapping relationship between vertices and the edges of the graph. The directed, undirected, weighted, and unweighted graphs can be represented using an adjacency matrix.
An adjacency matrix is an array of 2-D with V x V vertices. Each vertex is represented as a row and column.
The value of the adjacency matrix is determined by some value if the vertex is joined with another vertex with an edge
A [i] [j] = w, A is the adjacency matrix with i and j vertex
w is the value that represents the mapping of the vertex to the edge
- If it is an undirected graph joining from Vi to Vj will give 1 as the value of w.
- If it is a directed graph having multiple vertices, the adjacency matrix Aij can be determined by,
Aij = 1, if any path exists between two vertexes and self-loop between two vertices
Aij = 0, if doesn’t exist.
In other words, we can say, in the adjacency matrix 0 defines the non-existence of the mapping between two nodes and 1 represents the linkage between two nodes.
Adjacency Matrix for Undirected Graphs
In an undirected graph, if there is a linkage between two nodes the value will be 1 else 0. As we don’t know the directions in an undirected graph, the source and destination nodes are unknown, thus if there is any edge between two nodes will give result 1.
An à B or B à A, both are the same and give the value 1.
Adjacency Matrix of Directed Graphs
In a directed graph, we know the directions from one node to another thus the linkage between one node to another will give the value 1. If there is no self-loop in the graph will give the result 0.
If in the graph, there is no self-loop, the result is 0 and the linkage between any of the nodes is resulting in 1.
Adjacency Matrix of Weighted Directed Graphs
In a directed graph, we know the directions from one node to another and we have weights on each node and edges thus the linkage between one node to another will give the value 1. And the resultant value will be replaced by the weights. If there is no self-loop in the graph will give the result 0.
![Graph in C](https://static.tutorialandexample.com/c/graph-in-c4.png)
2. The Adjacency List Representation
It is also known as the Linked List Representation. It can be defined as the representation of the graph as an array of linked lists. Each linked list element represents the edge that connects the nodes and the array index represents the vertex.
![Graph in C](https://static.tutorialandexample.com/c/graph-in-c5.png)
Adjacency List of Undirected Graphs
In this representation, the linkage between the nodes in every possible way is checked and stored in a linked list which stores the value of the node and the pointer of the adjacent node. The pointer part of the last node is stored with NULL if all the nodes are traversed. An undirected graph has twice as many edges as the sum of the lengths of its adjacency lists.
Adjacency List of Directed Graphs
In this representation, we know about the directions by which the linkage between the nodes in every possible way is checked and stored in a linked list which stores the value of the node and the pointer of the adjacent node. The pointer part of the last node is stored with NULL if all the nodes are traversed. The total length of adjacency lists for a directed graph is equal to the number of edges in the graph.
Adjacency List of Weighted Directed Graphs
In the case of the weighted directed field, each node contains an extra field for the weight of the node of the graph.
Implementation of Graphs in C
1. Adjacency Matrix Representation of Graphs in C
CODE
#include <stdio.h>
#define V 4 // number of vertices
void initialize(int a[][V]) { // initializing the matrix to zero
int i, j;
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
a[i][j] = 0;
}
void insrtEdges(int a[][V], int i, int j) { // ading edges
a[i][j] = 1;
a[j][i] = 1;
}
void prntAdjMatrix(int a[][V]) { // printing the matrix
int i, j;
for (i = 0; i < V; i++) {
printf("%d: ", i);
for (j = 0; j < V; j++) {
printf("%d ", a[i][j]);
}
printf("\n");
}
}
int main() {
int adjMat[V][V];
initialize(adjMat);
insrtEdges(adjMat, 0, 1);
insrtEdges(adjMat, 0, 2);
insrtEdges(adjMat, 0, 2);
insrtEdges(adjMat, 2, 1);
insrtEdges(adjMat, 4, 3);
prntAdjMatrix(adjMat);
return 0;
}
OUTPUT
![Graph in C](https://static.tutorialandexample.com/c/graph-in-c6.png)
2. Adjacency List Representation of Graphs in C
CODE
#include <stdio.h>
#include <stdlib.h>
#define N 6 // vertices in the graph
struct Graph
{
struct Node* head[N];
};
struct Node
{
int dt;
struct Node* next;
};
struct Edge {
int src, dt;
};
struct Graph* createGraph(struct Edge edges[], int n)
{
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
for (int i = 0; i < N; i++) {
graph->head[i] = NULL;
}
for (int i = 0; i < n; i++)
{
int src = edges[i].src;
int dt = edges[i].dt;
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->dt = dt;
newNode->next = graph->head[src];
graph->head[src] = newNode;
}
return graph;
}
void printGraph(struct Graph* graph)
{
for (int i = 0; i < N; i++)
{
struct Node* ptr = graph->head[i];
while (ptr != NULL)
{
printf("(%d ---> %d)\t", i, ptr->dt);
ptr = ptr->next;
}
printf("\n");
}
}
int main(void)
{
struct Edge edges[] =
{
{0, 2}, {3, 5}, {2, 1}, {2, 3}, {3, 7}, {4, 4}, {1, 4}
};
int n = sizeof(edges)/sizeof(edges[0]);
struct Graph *graph = createGraph(edges, n);
printGraph(graph);
return 0;
}
OUTPUT
![Graph in C](https://static.tutorialandexample.com/c/graph-in-c7.png)
Graphs in real life
Graphs are used in various areas in real life.
- Google Maps is a widely used example of graphs. It uses graphs to build transportation systems where the vertex can denote the intersection of roads and the edges can be determined as the roads that connect the vertices.
- Graphs are used to represent the progression of computation, the relationship between various objects in computer science
- Facebook also uses graphs in such a way that the users are defined as the vertices and their friendship between other users or vertices is defining a relation that refers to as edges.
- They are used to represent networks, whether roads, telephone networks or circuit networks, etc.
- Various social media websites use graphs such as LinkedIn, Instagram, etc.
- Graphs are used to find the smallest path between two nodes in the Dijkstra algorithm.