Advanced Data Structures: Graphs in C
Hello there, fellow coder! Today, we’re going to dive into the fascinating world of graphs in C. Graphs are an advanced data structure that can represent relationships between items in a more general way than other data structures like arrays, linked lists, stacks, queues, and even trees. So, buckle up and let’s get started!
Table of Contents
What is a Graph?
A graph is a nonlinear data structure that consists of nodes, often called vertices, and edges. Each edge connects a pair of vertices. Graphs are used to solve many reallife problems that involve representing networks, including computer networks, social networks, web pages, etc.
Types of Graphs
There are two main types of graphs: directed and undirected. In a directed graph, each edge has a direction. In an undirected graph, edges do not have a direction; if there’s an edge from vertex A to vertex B, there’s implicitly an edge from vertex B to vertex A.
Representing Graphs in C
There are several ways to represent a graph in C, but the two most common ways are adjacency matrix and adjacency list.
Adjacency Matrix
An adjacency matrix is a 2D array of size V x V where V is the number of vertices in the graph. Let’s look at an example:
#include<stdio.h>
#define V 5
void addEdge(int graph[V][V], int src, int dest) {
graph[src][dest] = 1;
graph[dest][src] = 1;
}
void printGraph(int graph[V][V]) {
int i, j;
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
printf("%d ", graph[i][j]);
}
printf("\n");
}
}
int main() {
int graph[V][V] = {0};
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
printGraph(graph);
return 0;
}
CCode Explanation
In this code, we first define a 2D array graph
of size V x V and initialize all its elements to 0. The addEdge
function sets graph[src][dest]
and graph[dest][src]
to 1, indicating that there’s an edge between the src
and dest
vertices. The printGraph
function prints the adjacency matrix.
Adjacency List
An adjacency list represents a graph as an array of linked lists. The index of the array represents a vertex and each element in its linked list represents the other vertices that form an edge with the vertex. The adjacency list representation of a graph is more spaceefficient than the adjacency matrix if the graph is sparse (i.e., the number of edges is much less than the number of vertices).
Here’s an example:
#include<stdio.h>
#include<stdlib.h>
struct Node {
int dest;
struct Node* next;
};
struct List {
struct Node *head;
};
struct Graph {
int V;
struct List* array;
};
struct Node* newListNode(int dest) {
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode>dest = dest;
newNode>next = NULL;
return newNode;
}
struct Graph* createGraph(int V)
CCode Explanation
In this code, we first define a `Node` structure that has two members: `dest` and `next`. The `dest` member stores the destination vertex and `next` points to the next node in the list.
Next, we define a `List` structure that has a single member `head`, which points to the first node in each list.
Then, we define a `Graph` structure that has two members: `V`, which stores the number of vertices in the graph, and `array`, which is an array of `List`.
The `newListNode` function creates a new node for a given destination vertex. The `createGraph` function creates a graph with `V` vertices; no edges are added yet.
Graph Traversal
Graph traversal is the process of visiting every vertex in a graph. Two of the most common graph traversal algorithms are DepthFirst Search (DFS) and BreadthFirst Search (BFS).
DepthFirst Search (DFS)
DFS is a graph traversal method that explores as far as possible along each branch before backtracking. Here’s a simple implementation of DFS:
void DFS(struct Graph* graph, int vertex, bool visited[]) {
visited[vertex] = true;
printf("%d ", vertex);
struct Node* temp = graph>array[vertex].head;
while(temp) {
int adjVertex = temp>dest;
if(!visited[adjVertex]) {
DFS(graph, adjVertex, visited);
}
temp = temp>next;
}
}
CCode Explanation
In this code, the `DFS` function takes a graph, a vertex, and a `visited` array. It marks the current vertex as visited and prints it. Then, it recursively calls `DFS` for all adjacent vertices of the current vertex.
BreadthFirst Search (BFS)
BFS is another graph traversal method that explores all the vertices at the present depth before moving on to vertices at the next depth level. BFS uses a queue data structure to keep track of vertices to visit.
Here’s a simple implementation of BFS:
void BFS(struct Graph* graph, int startVertex) {
bool visited[V];
for(int i = 0; i < V; i++)
visited[i] = false;
List* queue = createList();
visited[startVertex] = true;
addToList(queue, startVertex);
while(!isListEmpty(queue)) {
printList(queue);
int currentVertex = removeFromFront(queue);
struct Node* temp = graph>array[currentVertex].head;
while(temp) {
int adjVertex = temp>dest;
if(!visited[adjVertex]) {
addToList(queue, adjVertex);
visited[adjVertex] = true;
}
temp = temp>next;
}
}
}
CCode Explanation
In this code, the BFS
function takes a graph and a start vertex. It creates a visited
array to keep track of visited vertices and a queue to keep track of vertices to visit. It marks the start vertex as visited and adds it to the queue. Then, it enters a while loop that continues until the queue is empty. In each iteration of the loop, it removes a vertex from the front of the queue and adds all its unvisited adjacent vertices to the back of the queue.
Wrapping Up
And that’s a wrap on our journey through graphs in C! We’ve covered a lot of ground, from the basics of what a graph is, to different ways to represent a graph in C, to graph traversal methods. I hope you’ve found this tutorial helpful and that it’s given you a solid foundation in working with graphs in C.
Frequently Asked Questions (FAQ)

What is a graph in advanced data structure?
A graph in advanced data structures is a nonlinear data structure that consists of nodes, often called vertices, and edges. Each edge connects a pair of vertices. Graphs are used to solve many reallife problems that involve representing networks, including computer networks, social networks, web pages, etc.

What are the 3 types of graph data structure?
There are many types of graphs, but the three most commonly discussed are undirected graphs, directed graphs, and weighted graphs. Undirected graphs have edges that do not have a direction. Directed graphs, also known as digraphs, have edges with direction. Weighted graphs have edges that carry a certain weight or cost.

How to create a graph data structure in C?
In C, a graph can be represented in various ways, the two most common being an adjacency matrix and an adjacency list. An adjacency matrix is a 2D array of size V x V where V is the number of vertices in the graph. An adjacency list is a more spaceefficient way to represent a graph, especially if the graph is sparse. It represents a graph as an array of linked lists.

Is C good for data structures?
Yes, C is an excellent language for learning data structures. It’s a powerful, efficient language that gives you lowlevel control over your computer’s memory. This makes it ideal for implementing complex data structures like graphs. Plus, the skills you learn from manipulating data structures in C are easily transferable to other languages.
Related Tutorials
 Introduction to Data Structures in C
 Trees in C
 Advanced Data Structures: Binary Trees in C
 Advanced Data Structures: Segment Trees in C
 Advanced Data Structures: Heaps in C
Remember, practice is key when it comes to mastering data structures and algorithms. So, don’t just read these tutorials—get your hands dirty with some coding as well!