Graphs

Graphs are fundamental data structures used to represent relationships between pairs of objects. They consist of a set of vertices (or nodes) and a set of edges (or arcs) that connect pairs of vertices. Graphs can model various real-world scenarios, such as social networks, transportation systems, and computer networks.

9.1 Definition and Representation of Graphs

Definition of Graphs

A graph is a mathematical structure used to model pairwise relationships between objects. It consists of a finite set of vertices (also called nodes) and a set of edges that connect pairs of vertices. Graphs are used to represent many real-world systems, such as social networks, transportation networks, and computer networks.

Vertices (Nodes): The individual entities in the graph. Each vertex represents a point or a location.
Edges (Links): The connections between the vertices. An edge may connect two vertices and can be directed or undirected, depending on the relationship it represents.

Mathematically, a graph $G$ can be defined as:

$G = (V, E)$

Where:

$V$ is a set of vertices.
$E$ is a set of edges, where each edge is a pair of vertices.

Types of Graphs

Undirected Graph: In an undirected graph, edges have no direction. The edge $(u, v)$ is the same as $(v, u)$ .
Directed Graph (Digraph): In a directed graph, edges have a direction, indicated by arrows. The edge $\to v)$ is different from $\to u)$ .
Weighted Graph: A graph where edges have weights assigned to them, which can represent distances, costs, or any other measurable quantity.
Unweighted Graph: A graph where edges do not have weights.

Representation of Graphs

Graphs can be represented in several ways, with the most common being:

Adjacency Matrix:
- A 2D array where the cell at row $i$ and column $j$ indicates the presence (and possibly the weight) of an edge between vertex $i$ and vertex $j$ .
- For an undirected graph with $n$ vertices, the adjacency matrix is symmetric.
Example: For a graph with vertices $A, B, C$ :

Adjacency Matrix:
A B C
A 0 1 0
B 1 0 1
C 0 1 0

Here, there is an edge between $A$ and $B$ , and between $B$ and $C$ .
Adjacency List:
- An array of lists, where each index represents a vertex and contains a list of adjacent vertices.
- This representation is more space-efficient for sparse graphs (where the number of edges is much less than the maximum possible).
Example:

Adjacency List:
A: B
B: A, C
C: B

In this example, vertex $A$ is connected to $B$ , vertex $B$ is connected to both $A$ and $C$ , and vertex $C$ is connected to $B$ .
Edge List:
- A collection of edges, where each edge is represented as a pair (or tuple) of vertices. This representation is straightforward but may be less efficient for certain operations.
Example:

Edge List:
(A, B)
(B, C)
Incidence Matrix:
- A matrix representation where rows represent vertices and columns represent edges. The cell value indicates the relationship between the vertex and the edge (e.g., 1 for an incident edge, 0 otherwise).
Example:

Incidence Matrix:
E1 E2
A 1 0
B 1 1
C 0 1

Here, edge $E 1$ connects vertices $A$ and $B$ , while edge $E 2$ connects $B$ and $C$ .

9.2 Graph Traversal: BFS and DFS

Graph traversal refers to the process of visiting all the vertices in a graph. Two of the most common algorithms for graph traversal are Breadth-First Search (BFS) and Depth-First Search (DFS). Each algorithm explores the graph in a different manner and has its own applications and characteristics.

1. Breadth-First Search (BFS)

BFS is an algorithm that explores the graph level by level, starting from a source vertex and visiting all its neighboring vertices before moving on to the next level of vertices. This traversal uses a queue data structure to keep track of the vertices to be explored next.

Algorithm Steps:

Start from the source vertex and mark it as visited.
Enqueue the source vertex into a queue.
While the queue is not empty:
- Dequeue a vertex from the front of the queue.
- Visit all unvisited neighbors of the dequeued vertex, mark them as visited, and enqueue them.

Characteristics:

BFS guarantees the shortest path in unweighted graphs.
It is useful for finding the shortest path in social networks, routing protocols, and more.

Example Implementation in C:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX 100

// Adjacency List Representation
struct Node {
int vertex;
struct Node* next;
};

struct Graph {
int numVertices;
struct Node** adjLists;
};

// Queue structure
struct Queue {
int items[MAX];
int front;
int rear;
};

// Queue functions
void initQueue(struct Queue* q) {
q->front = -1;
q->rear = -1;
}

bool isEmpty(struct Queue* q) {
return q->rear == -1;
}

void enqueue(struct Queue* q, int value) {
if (q->rear == MAX – 1) return; // Queue is full
if (q->front == -1) q->front = 0;
q->items[++(q->rear)] = value;
}

int dequeue(struct Queue* q) {
if (isEmpty(q)) return -1;
int item = q->items[q->front++];
if (q->front > q->rear) {
q->front = q->rear = -1; // Reset queue
}
return item;
}

// Create graph
struct Graph* createGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->adjLists = malloc(vertices * sizeof(struct Node*));

for (int i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
}
return graph;
}

// Add edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
struct Node* newNode = malloc(sizeof(struct Node));
newNode->vertex = dest;
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;

// For undirected graph
newNode = malloc(sizeof(struct Node));
newNode->vertex = src;
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}

// BFS algorithm
void BFS(struct Graph* graph, int startVertex) {
bool visited[MAX] = { false };
struct Queue q;
initQueue(&q);

visited[startVertex] = true;
enqueue(&q, startVertex);

while (!isEmpty(&q)) {
int currentVertex = dequeue(&q);
printf(“Visited %d\n”, currentVertex);

struct Node* temp = graph->adjLists[currentVertex];
while (temp) {
int adjVertex = temp->vertex;
if (!visited[adjVertex]) {
visited[adjVertex] = true;
enqueue(&q, adjVertex);
}
temp = temp->next;
}
}
}

int main() {
struct Graph* graph = createGraph(5);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 4);

printf(“BFS starting from vertex 0:\n”);
BFS(graph, 0);

return 0;
}

2. Depth-First Search (DFS)

DFS is an algorithm that explores as far as possible along each branch before backtracking. It can be implemented using recursion or a stack.

Algorithm Steps:

Start from the source vertex and mark it as visited.
For each unvisited neighbor of the current vertex:
- Recursively visit the neighbor.

Characteristics:

DFS does not guarantee the shortest path.
It is useful for exploring all possible paths, topological sorting, and solving puzzles like mazes.

Example Implementation in C:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX 100

// Adjacency List Representation
struct Node {
int vertex;
struct Node* next;
};

struct Graph {
int numVertices;
struct Node** adjLists;
};

// Create graph
struct Graph* createGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->adjLists = malloc(vertices * sizeof(struct Node*));

for (int i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
}
return graph;
}

// For undirected graph
newNode = malloc(sizeof(struct Node));
newNode->vertex = src;
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}

// DFS algorithm
void DFSUtil(struct Graph* graph, int vertex, bool visited[]) {
visited[vertex] = true;
printf(“Visited %d\n”, vertex);

struct Node* temp = graph->adjLists[vertex];
while (temp) {
int adjVertex = temp->vertex;
if (!visited[adjVertex]) {
DFSUtil(graph, adjVertex, visited);
}
temp = temp->next;
}
}

void DFS(struct Graph* graph, int startVertex) {
bool visited[MAX] = { false };
DFSUtil(graph, startVertex, visited);
}

int main() {
struct Graph* graph = createGraph(5);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 4);

printf(“DFS starting from vertex 0:\n”);
DFS(graph, 0);

return 0;
}

9.3 Minimum Spanning Trees: Kruskal’s and Prim’s Algorithm

A Minimum Spanning Tree (MST) of a graph is a subset of its edges that connects all the vertices together without any cycles and with the minimum possible total edge weight. Two of the most well-known algorithms for finding the MST of a graph are Kruskal’s Algorithm and Prim’s Algorithm.

1. Kruskal’s Algorithm

Kruskal’s Algorithm is a greedy algorithm that finds the MST by selecting edges in order of increasing weight. It ensures that no cycles are formed and that all vertices are connected.

Algorithm Steps:

Sort all the edges in the graph in non-decreasing order of their weights.
Initialize an empty tree (MST).
Iterate through the sorted edges, adding each edge to the MST if it does not form a cycle (using a Union-Find data structure to check for cycles).
Stop when there are $V - 1$ edges in the MST (where $V$ is the number of vertices).

Time Complexity: $\log E)$ , where $E$ is the number of edges.

Example Implementation in C:

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

// Structure to represent an edge
struct Edge {
int src, dest, weight;
};

// Structure to represent a graph
struct Graph {
int numVertices;
int numEdges;
struct Edge* edges;
};

// Find function for Union-Find
int find(int parent[], int i) {
if (parent[i] == -1) {
return i;
}
return find(parent, parent[i]);
}

// Union function for Union-Find
void unionSets(int parent[], int x, int y) {
int xset = find(parent, x);
int yset = find(parent, y);
parent[xset] = yset;
}

// Function to compare edges for sorting
int compare(const void* a, const void* b) {
struct Edge* edge1 = (struct Edge*)a;
struct Edge* edge2 = (struct Edge*)b;
return edge1->weight > edge2->weight;
}

// Kruskal’s Algorithm to find MST
void kruskalMST(struct Graph* graph) {
int parent[MAX];
for (int i = 0; i < graph->numVertices; i++) {
parent[i] = -1; // Initialize parent array
}

// Sort edges based on weight
qsort(graph->edges, graph->numEdges, sizeof(graph->edges[0]), compare);

printf(“Edges in the Minimum Spanning Tree:\n”);
int edgeCount = 0;

for (int i = 0; i < graph->numEdges; i++) {
struct Edge edge = graph->edges[i];
int x = find(parent, edge.src);
int y = find(parent, edge.dest);

// If the edge doesn’t form a cycle, include it in the result
if (x != y) {
printf(“%d – %d: %d\n”, edge.src, edge.dest, edge.weight);
unionSets(parent, x, y);
edgeCount++;
}

// Stop if we have V – 1 edges
if (edgeCount == graph->numVertices – 1) {
break;
}
}
}

int main() {
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = 4;
graph->numEdges = 5;
graph->edges = malloc(graph->numEdges * sizeof(struct Edge));

// Adding edges
graph->edges[0] = (struct Edge){0, 1, 10};
graph->edges[1] = (struct Edge){0, 2, 6};
graph->edges[2] = (struct Edge){0, 3, 5};
graph->edges[3] = (struct Edge){1, 3, 15};
graph->edges[4] = (struct Edge){2, 3, 4};

kruskalMST(graph);

free(graph->edges);
free(graph);
return 0;
}

2. Prim’s Algorithm

Prim’s Algorithm is another greedy algorithm that finds the MST by starting from an arbitrary vertex and expanding the MST one edge at a time. It always selects the edge with the smallest weight that connects a vertex in the MST to a vertex outside it.

Algorithm Steps:

Start with an arbitrary vertex and mark it as part of the MST.
Initialize a priority queue (or min-heap) to keep track of the edges connecting the vertices in the MST to those outside.
While there are still vertices not included in the MST:
- Extract the minimum weight edge from the priority queue.
- Add the edge to the MST and mark the connected vertex as part of the MST.
- Add all edges connected to the new vertex that lead to unvisited vertices into the priority queue.

Time Complexity: $\log V)$ , where $V$ is the number of vertices and $E$ is the number of edges.

Example Implementation in C:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX 100

// Structure to represent a graph
struct Graph {
int numVertices;
int cost[MAX][MAX];
};

// Function to find the vertex with the minimum key value
int minKey(int key[], bool mstSet[], int vertices) {
int min = INT_MAX, minIndex;
for (int v = 0; v < vertices; v++) {
if (mstSet[v] == false && key[v] < min) {
min = key[v];
minIndex = v;
}
}
return minIndex;
}

// Prim’s Algorithm to find MST
void primMST(struct Graph* graph) {
int parent[MAX]; // Array to store the constructed MST
int key[MAX]; // Key values used to pick the minimum weight edge
bool mstSet[MAX]; // To track vertices included in MST

// Initialize all keys to infinity and mstSet to false
for (int i = 0; i < graph->numVertices; i++) {
key[i] = INT_MAX;
mstSet[i] = false;
}

// Start from the first vertex
key[0] = 0;
parent[0] = -1; // First node is always root of MST

for (int count = 0; count < graph->numVertices – 1; count++) {
int u = minKey(key, mstSet, graph->numVertices);
mstSet[u] = true; // Include vertex in MST

// Update key value and parent index of the adjacent vertices
for (int v = 0; v < graph->numVertices; v++) {
if (graph->cost[u][v] && mstSet[v] == false && graph->cost[u][v] < key[v]) {
parent[v] = u;
key[v] = graph->cost[u][v];
}
}
}

// Print the constructed MST
printf(“Edge \tWeight\n”);
for (int i = 1; i < graph->numVertices; i++) {
printf(“%d – %d \t%d\n”, parent[i], i, graph->cost[i][parent[i]]);
}
}

int main() {
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = 5;

// Cost matrix representation of the graph
int cost[MAX][MAX] = {
{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0}
};
for (int i = 0; i < graph->numVertices; i++) {
for (int j = 0; j < graph->numVertices; j++) {
graph->cost[i][j] = cost[i][j];
}
}

primMST(graph);

free(graph);
return 0;
}

9.4 Shortest Path Algorithms: Dijkstra’s Algorithm

Dijkstra’s Algorithm is a popular algorithm used to find the shortest paths from a source vertex to all other vertices in a weighted graph. It is particularly efficient for graphs with non-negative edge weights.

Overview

The algorithm maintains a set of vertices whose shortest distance from the source is known, and it repeatedly selects the vertex with the smallest known distance to explore its neighbors. The primary steps are as follows:

Initialization: Set the distance to the source vertex to zero and the distances to all other vertices to infinity. Mark all vertices as unvisited.
Exploration: Select the unvisited vertex with the smallest distance. For each unvisited neighbor, calculate the tentative distance from the source through the current vertex. If this distance is less than the known distance, update it.
Mark as Visited: After exploring all neighbors of the selected vertex, mark it as visited.
Repeat: Continue the process until all vertices are visited or the smallest distance among the unvisited vertices is infinity.

Time Complexity: $O(V^2)$ with a simple implementation, but it can be reduced to $\log V)$ using a priority queue (min-heap).

Example Implementation in C

Here’s a C program that implements Dijkstra’s Algorithm using a simple adjacency matrix for representation:

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>

#define V 5 // Number of vertices in the graph

// Function to find the vertex with the minimum distance value
int minDistance(int dist[], bool sptSet[]) {
int min = INT_MAX, minIndex;

for (int v = 0; v < V; v++) {
if (sptSet[v] == false && dist[v] < min) {
min = dist[v];
minIndex = v;
}
}
return minIndex;
}

// Function to implement Dijkstra’s Algorithm
void dijkstra(int graph[V][V], int src) {
int dist[V]; // Output array. dist[i] holds the shortest distance from src to i
bool sptSet[V]; // Shortest path tree set

// Initialize all distances as INFINITE and sptSet as false
for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
sptSet[i] = false;
}

// Distance from source to itself is always 0
dist[src] = 0;

// Find the shortest path for all vertices
for (int count = 0; count < V – 1; count++) {
// Pick the minimum distance vertex from the set of vertices not yet processed
int u = minDistance(dist, sptSet);
sptSet[u] = true; // Mark the picked vertex as processed

// Update dist value of the adjacent vertices of the picked vertex
for (int v = 0; v < V; v++) {
// Update dist[v] if and only if it is not in sptSet, there is an edge from u to v,
// and the total weight of path from src to v through u is smaller than the current value of dist[v]
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}

// Print the constructed distance array
printf(“Vertex \t Distance from Source\n”);
for (int i = 0; i < V; i++) {
printf(“%d \t %d\n”, i, dist[i]);
}
}

int main() {
// Example graph represented as an adjacency matrix
int graph[V][V] = {
{0, 10, 0, 30, 100},
{10, 0, 50, 0, 0},
{0, 50, 0, 20, 10},
{30, 0, 20, 0, 60},
{100, 0, 10, 60, 0}
};

dijkstra(graph, 0); // Running Dijkstra’s algorithm from vertex 0

return 0;
}

Explanation of the Code

Graph Representation: The graph is represented as an adjacency matrix where graph[i][j] holds the weight of the edge from vertex i to vertex j. A value of 0 indicates no direct edge.
minDistance Function: This function finds the vertex with the minimum distance value that has not yet been included in the shortest path tree.
dijkstra Function: This function implements the main logic of Dijkstra’s algorithm. It initializes the distances and explores the graph to find the shortest paths.
Output: The program prints the shortest distance from the source vertex to all other vertices in the graph.

Here’s a program to implement graph traversal algorithms: Breadth-First Search (BFS) and Depth-First Search (DFS). The program uses an adjacency list representation of the graph.

C Program for Graph Traversal Algorithms

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_VERTICES 100

// Structure to represent a graph
struct Graph {
int numVertices;
int adj[MAX_VERTICES][MAX_VERTICES];
};

// Function to create a graph with a given number of vertices
struct Graph* createGraph(int vertices) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->numVertices = vertices;

// Initialize adjacency matrix
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
graph->adj[i][j] = 0;
}
}
return graph;
}

// Function to add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
graph->adj[src][dest] = 1;
graph->adj[dest][src] = 1; // For undirected graph
}

// Breadth-First Search (BFS) function
void bfs(struct Graph* graph, int start) {
bool visited[MAX_VERTICES] = {false};
int queue[MAX_VERTICES], front = -1, rear = -1;

// Mark the start vertex as visited and enqueue it
visited[start] = true;
queue[++rear] = start;

printf(“BFS Traversal starting from vertex %d:\n”, start);

while (front < rear) {
int current = queue[++front];
printf(“%d “, current);

// Explore the neighbors
for (int i = 0; i < graph->numVertices; i++) {
if (graph->adj[current][i] && !visited[i]) {
visited[i] = true;
queue[++rear] = i;
}
}
}
printf(“\n”);
}

// Depth-First Search (DFS) function
void dfsUtil(struct Graph* graph, int vertex, bool visited[]) {
visited[vertex] = true;
printf(“%d “, vertex);

// Explore the neighbors
for (int i = 0; i < graph->numVertices; i++) {
if (graph->adj[vertex][i] && !visited[i]) {
dfsUtil(graph, i, visited);
}
}
}

// Function to initiate DFS traversal
void dfs(struct Graph* graph, int start) {
bool visited[MAX_VERTICES] = {false};
printf(“DFS Traversal starting from vertex %d:\n”, start);
dfsUtil(graph, start, visited);
printf(“\n”);
}

int main() {
int vertices = 5; // Number of vertices in the graph
struct Graph* graph = createGraph(vertices);

// Adding edges to the graph
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);

// Perform BFS and DFS traversals
bfs(graph, 0); // Starting BFS from vertex 0
dfs(graph, 0); // Starting DFS from vertex 0

// Free allocated memory
free(graph);
return 0;
}

Explanation of the Code

Graph Representation: The graph is represented using an adjacency matrix where graph->adj[i][j] holds 1 if there is an edge between vertex i and vertex j, and 0 otherwise.
Creating the Graph: The createGraph function initializes a graph with a specified number of vertices, setting all adjacency matrix entries to zero.
Adding Edges: The addEdge function adds an undirected edge between the specified source and destination vertices.
Breadth-First Search (BFS):
- The bfs function initializes a queue and marks the starting vertex as visited. It explores all its neighbors, marking them visited and enqueuing them until the queue is empty.
Depth-First Search (DFS):
- The dfsUtil function is a recursive helper function that marks a vertex as visited and recursively explores its unvisited neighbors.
- The dfs function initializes the visited array and starts the DFS traversal.
Main Function: In the main function, a sample graph is created, edges are added, and both BFS and DFS traversals are initiated starting from vertex 0.

Output

When the program is executed, it will display the BFS and DFS traversals starting from vertex 0.

Summary

BFS is suitable for finding the shortest path in unweighted graphs and explores all neighbors at the present depth before moving on to vertices at the next depth level.
DFS is useful for exploring all paths and can be used in applications like topological sorting and cycle detection.

These traversal algorithms are fundamental in graph theory and have numerous applications in computer science, including network routing, social network analysis, and pathfinding in game development.

Graphs

Graphs

9.1 Definition and Representation of Graphs

Definition of Graphs

Types of Graphs

Representation of Graphs

9.2 Graph Traversal: BFS and DFS

1. Breadth-First Search (BFS)

2. Depth-First Search (DFS)

9.3 Minimum Spanning Trees: Kruskal’s and Prim’s Algorithm

1. Kruskal’s Algorithm

2. Prim’s Algorithm

9.4 Shortest Path Algorithms: Dijkstra’s Algorithm

Overview

Example Implementation in C

Explanation of the Code

C Program for Graph Traversal Algorithms

Explanation of the Code

Output

Summary

Discussion