Graph Algorithms | Algorithms

Introduction to Graphs

A graph is a data structure that consists of a set of nodes (also called vertices) and a set of edges that connect pairs of nodes. Graphs are used to model relationships between objects. For example, a social network can be represented as a graph where each person is a node and each friendship is an edge.

Types of Graphs

Graphs can be categorized based on various properties:

Directed Graph: Edges have a direction, indicating a one-way relationship.
Undirected Graph: Edges do not have a direction, indicating a two-way relationship.
Weighted Graph: Edges have a weight or cost associated with them.
Unweighted Graph: Edges do not have any weight or cost.

Graph Representation

Graphs can be represented in multiple ways in a computer. The two most common representations are:

Adjacency Matrix: A 2D array where the element at row i and column j indicates the presence (and possibly the weight) of an edge from node i to node j.
Adjacency List: An array of lists. The index of the array represents a node, and each element in the list represents the nodes adjacent to that node.

Example: Adjacency Matrix

Consider the following graph:

The adjacency matrix representation of the above graph would be:

Depth-First Search (DFS)

Depth-First Search (DFS) is an algorithm for traversing or searching tree or graph data structures. It starts at a given node (called the "root" or "starting node") and explores as far as possible along each branch before backtracking.

Example: DFS in C

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

#define MAX 100

int n;
int adj[MAX][MAX];
int visited[MAX];

void DFS(int v) {
    printf("%d ", v);
    visited[v] = 1;
    for (int i = 0; i < n; i++) {
        if (adj[v][i] == 1 && !visited[i]) {
            DFS(i);
        }
    }
}

int main() {
    printf("Enter number of vertices: ");
    scanf("%d", &n);
    printf("Enter adjacency matrix:\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &adj[i][j]);
        }
    }
    for (int i = 0; i < n; i++) {
        visited[i] = 0;
    }
    printf("DFS traversal starting from vertex 0:\n");
    DFS(0);
    return 0;
}

Input:

Output:

0 1 2 3

Breadth-First Search (BFS)

Breadth-First Search (BFS) is another algorithm for traversing or searching tree or graph data structures. It starts at a given node and explores all of its neighbors at the present depth level before moving on to nodes at the next depth level.

Example: BFS in C

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

#define MAX 100

int n;
int adj[MAX][MAX];
int visited[MAX];
int queue[MAX];
int front = -1, rear = -1;

void enqueue(int v) {
    if (rear == MAX - 1) return;
    if (front == -1) front = 0;
    rear++;
    queue[rear] = v;
}

int dequeue() {
    if (front == -1) return -1;
    int v = queue[front];
    if (front == rear) front = rear = -1;
    else front++;
    return v;
}

void BFS(int start) {
    visited[start] = 1;
    enqueue(start);
    while (front != -1) {
        int v = dequeue();
        printf("%d ", v);
        for (int i = 0; i < n; i++) {
            if (adj[v][i] == 1 && !visited[i]) {
                visited[i] = 1;
                enqueue(i);
            }
        }
    }
}

int main() {
    printf("Enter number of vertices: ");
    scanf("%d", &n);
    printf("Enter adjacency matrix:\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &adj[i][j]);
        }
    }
    for (int i = 0; i < n; i++) {
        visited[i] = 0;
    }
    printf("BFS traversal starting from vertex 0:\n");
    BFS(0);
    return 0;
}

Input:

Output:

0 1 2 3

Dijkstra's Algorithm

Dijkstra's algorithm is used to find the shortest path between nodes in a graph, which may represent, for example, road networks. It works by iteratively selecting the node with the smallest tentative distance and updating the distances of its neighbors.

Example: Dijkstra's Algorithm in C

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

#define MAX 100
#define INFINITY INT_MAX

int n;
int adj[MAX][MAX];
int dist[MAX];
int visited[MAX];

int minDistance() {
    int min = INFINITY, minIndex;
    for (int v = 0; v < n; v++) {
        if (!visited[v] && dist[v] <= min) {
            min = dist[v];
            minIndex = v;
        }
    }
    return minIndex;
}

void dijkstra(int src) {
    for (int i = 0; i < n; i++) {
        dist[i] = INFINITY;
        visited[i] = 0;
    }
    dist[src] = 0;
    for (int count = 0; count < n - 1; count++) {
        int u = minDistance();
        visited[u] = 1;
        for (int v = 0; v < n; v++) {
            if (!visited[v] && adj[u][v] && dist[u] != INFINITY && dist[u] + adj[u][v] < dist[v]) {
                dist[v] = dist[u] + adj[u][v];
            }
        }
    }
    printf("Vertex Distance from Source\n");
    for (int i = 0; i < n; i++) {
        printf("%d tt %d\n", i, dist[i]);
    }
}

int main() {
    printf("Enter number of vertices: ");
    scanf("%d", &n);
    printf("Enter adjacency matrix (use 0 for no connection and positive weights for edges):\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &adj[i][j]);
        }
    }
    printf("Enter source vertex: ");
    int src;
    scanf("%d", &src);
    dijkstra(src);
    return 0;
}

Input:

5
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
0

Output:

Vertex Distance from Source
0 tt 0
1 tt 10
2 tt 50
3 tt 30
4 tt 60

Conclusion

Graph algorithms are fundamental in computer science and are used in various applications, from network routing to social media analysis. Understanding how to represent graphs and implement basic algorithms like DFS, BFS, and Dijkstra's is crucial for solving complex problems involving relationships and connections between objects.