Introduction to Graphs

A graph is a collection of nodes (also called vertices) and edges that connect pairs of nodes. Graphs are an abstract data structure used to represent relationships between objects. A graph G is typically denoted as G = (V, E), where:

• V is the set of vertices (nodes).

• E is the set of edges, where each edge connects two vertices.

Graphs are highly versatile and can be used to represent a wide variety of real-world systems and problems. Depending on the nature of the edges and vertices, graphs can take on different forms, leading to various types of graphs that serve different purposes.

Types of Graphs

1. Directed Graph (Digraph): In a directed graph, the edges have a direction associated with them, meaning that each edge goes from one vertex to another specific vertex. The direction is typically represented with an arrow.

   • Directed Edge: An edge (u, v) means there is a connection from node u to node v, but not necessarily in the reverse direction.

   • Example: Social media networks where a user follows another user. The relationship is not always mutual.

Example Representation:

    A → B → C
        ↑  
        ↓   
        D

2. Undirected Graph: In an undirected graph, the edges have no direction, meaning that if an edge connects vertices u and v, the relationship is bidirectional. In other words, u is connected to v, and v is connected to u.

   • Undirected Edge: An edge (u, v)means that u and v are connected, and the relationship is mutual.

   • Example: A network of roads between cities, where travel is possible in both directions.

Example Representation:

    A -- B -- C
        |    /
        D -- E

Real-World Examples of Graphs

Graphs are used extensively in many areas of computer science, as well as in real-world scenarios. Here are some common applications:

1. Social Networks:

   • Nodes represent people or accounts.

   • Edges represent relationships (e.g., friendships or followers).

   • Directed graphs can represent networks like Twitter, where following is one-way.

   • Undirected graphs can represent Facebook friendships, which are mutual.

2. Road Networks:

   • Nodes represent intersections or cities.

   • Edges represent roads connecting these locations.

   • Undirected graphs are used where roads allow two-way travel.

   • Directed graphs can represent one-way streets.

3. Internet/Computer Networks:

   • Nodes represent computers, routers, or servers.

   • Edges represent communication links (e.g., physical cables, wireless connections).

   • Directed graphs can represent asymmetric bandwidth, where data flow capacity differs in each direction.

4. Web Pages (Hyperlink Structure):

   • Nodes represent web pages.

   • Edges represent hyperlinks between pages.

   • This is a directed graph where a hyperlink points from one page to another.

5. Transportation Networks:

   • Nodes represent airports, train stations, or bus stops.

   • Edges represent flights, train routes, or bus routes between them.

   • This can be a directed graph if certain routes only allow one-way travel.

6. Recommendation Systems:

   • Nodes represent users and products (e.g., movies, books).

   • Edges represent preferences or interactions (e.g., user A likes product B).

7. Electrical Circuits:

   • Nodes represent circuit components (e.g., resistors, capacitors).

   • Edges represent the connections between components (wires).

Graph Terminology

Understanding the basic terminology of graphs is essential for working with them. Here's a breakdown of the key concepts:

Vertices and Edges

• Vertices (also called nodes) are the fundamental units of a graph. Each vertex represents a unique entity or point in the graph. The set of vertices in a graph G is often denoted as V(G).

• Edges are the connections between vertices. An edge connects two vertices and represents the relationship between them. In an undirected graph, an edge between vertices u and v is written as (u, v), meaning both u and v are connected. In a directed graph, the edge is directional, and (u, v) indicates a connection from u to v.

Example:

A --- B    // Vertices A and B are connected by an edge.

Degree of a Vertex

The degree of a vertex is the number of edges connected to that vertex. The degree can be further classified into in-degree and out-degree, especially in directed graphs.

• In-degree: The number of edges directed into a vertex. In other words, the number of incoming edges.

• Out-degree: The number of edges directed out of a vertex. In other words, the number of outgoing edges.

In an undirected graph, the degree of a vertex is simply the number of edges connected to it.

Example in a directed graph:

A → B → C

• The in-degree of vertex B is 1 (one incoming edge from A).

• The out-degree of vertex B is 1 (one outgoing edge to C).

Path, Cycle, and Circuit

• Path: A path is a sequence of edges that connect a sequence of distinct vertices. A path must not repeat any vertices or edges. In a directed graph, the edges in a path must follow the direction of the edges.

  Example: In a graph \(A \rightarrow B \rightarrow C\), the path is \(A \rightarrow B \rightarrow C \) .

• Cycle: A cycle is a path that starts and ends at the same vertex, with no other repeated vertices along the path. In a directed graph, the edges in a cycle must follow the direction of the edges.

  Example: \(A \rightarrow B \rightarrow C \rightarrow A\) is a cycle because it forms a closed loop.

• Circuit: A circuit is a special type of cycle in which a vertex can be visited multiple times, but the path still starts and ends at the same vertex.

Connected and Disconnected Graphs

• Connected Graph: A graph is connected if there is a path between every pair of vertices. In other words, it is possible to reach any vertex from any other vertex in the graph.

  Example of a connected graph:

    A --- B
     \   /
       C
  

• Disconnected Graph: A graph is disconnected if there is at least one pair of vertices for which there is no path connecting them. A disconnected graph can be broken into two or more connected components.

  Example of a disconnected graph:

    A --- B     D
     \   /     / \
       C      E   F
  

Here, A, B, and C are connected, and D, E, and F form a separate, connected component, disconnected from the one formed by A, B, and C.

Subgraphs, Trees, and Forests

• Subgraph: A subgraph is a portion of a graph that consists of a subset of the vertices and edges from the original graph. A subgraph must adhere to the connectivity of the original graph; if there is an edge between two vertices in the original graph, the same edge must exist in the subgraph if both vertices are included.

  Example: Original graph:

    A --- B --- C
         / \
        D   E
  

  Subgraph:

    A --- B --- C
  

• Tree: A tree is a special type of graph that is connected and acyclic (it has no cycles). A tree with n vertices always has n-1 edges, and there is exactly one path between any pair of vertices. Trees are often used to model hierarchical structures.

  Example:

        A
       / \
      B   C
         / \
        D   E
  

• Forest: A forest is a collection of disjoint trees. In other words, it is a graph that contains no cycles and may consist of multiple unconnected trees.

  Example:

      A      D
     / \    / \
    B   C  E   F
  

In this example, we have two disconnected trees, making the graph a forest.

Graph Representation

Graphs can be represented in several ways depending on the application and structure of the graph. The most common representations are the adjacency matrix, adjacency list, and incidence matrix. Each method has different strengths and weaknesses in terms of space complexity and ease of use for certain operations.

1. Adjacency Matrix

An adjacency matrix is a 2D array where both the rows and columns represent vertices. The value at position \( A[u][v] \) indicates whether there is an edge between vertices \( u \) and \( v \) :

• For an undirected graph, the matrix is symmetric, meaning \( A[u][v] = A[v][u] \) .

• For a directed graph, \( A[u][v] = 1 \) represents an edge from \( u \) to \( v \) .

C Code for Adjacency Matrix Representation

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

#define MAX_VERTICES 10

// Function to create an adjacency matrix for an undirected graph
void createAdjMatrix(int adjMatrix[MAX_VERTICES][MAX_VERTICES], int vertices) {
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            adjMatrix[i][j] = 0;  // Initialize matrix with 0 (no edges)
        }
    }

    int u, v, edges;
    printf("Enter the number of edges: ");
    scanf("%d", &edges);

    for (int i = 0; i < edges; i++) {
        printf("Enter edge (u v): ");
        scanf("%d %d", &u, &v);
        adjMatrix[u][v] = 1; // Mark the edge in the matrix
        adjMatrix[v][u] = 1; // For undirected graph
    }
}

// Function to display the adjacency matrix
void displayAdjMatrix(int adjMatrix[MAX_VERTICES][MAX_VERTICES], int vertices) {
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            printf("%d ", adjMatrix[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int vertices;
    printf("Enter the number of vertices: ");
    scanf("%d", &vertices);

    int adjMatrix[MAX_VERTICES][MAX_VERTICES];
    createAdjMatrix(adjMatrix, vertices);
    displayAdjMatrix(adjMatrix, vertices);

    return 0;
}

Space Complexity:

• The space complexity of an adjacency matrix is \( O(V^2) \) , where \( V \) is the number of vertices.

• This representation is inefficient for sparse graphs, as it requires space for every possible edge, even when most entries are 0.

2. Adjacency List

An adjacency list represents the graph by maintaining a list for each vertex, where each list contains the vertices adjacent to that vertex.

C Code for Adjacency List Representation

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

// Structure to represent an adjacency list node
struct Node {
    int vertex;
    struct Node* next;
};

// Structure to represent an adjacency list
struct Graph {
    int vertices;
    struct Node** adjLists;
};

// Function to create a new adjacency list node
struct Node* createNode(int vertex) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = vertex;
    newNode->next = NULL;
    return newNode;
}

// Function to create a graph with adjacency lists
struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->vertices = vertices;
    graph->adjLists = (struct Node**)malloc(vertices * sizeof(struct Node*));

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

    return graph;
}

// Function to add an edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest) {
    // Add edge from src to dest
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // Add edge from dest to src (for undirected graph)
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// Function to print the adjacency list representation of the graph
void printGraph(struct Graph* graph) {
    for (int v = 0; v < graph->vertices; v++) {
        struct Node* temp = graph->adjLists[v];
        printf("\n Vertex %d\n: ", v);
        while (temp) {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    int vertices = 5;
    struct Graph* graph = createGraph(vertices);
    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;
}

Space Complexity:

• The space complexity of an adjacency list is \( O(V + E) \) , where \( V \) is the number of vertices and \( E \) is the number of edges.

• This representation is space-efficient for sparse graphs, as it only stores the existing edges.

3. Incidence Matrix

An incidence matrix is a 2D array where rows represent vertices and columns represent edges. The entries in the matrix indicate which vertices are connected by each edge.

C Code for Incidence Matrix Representation

#include <stdio.h>

#define MAX_VERTICES 10
#define MAX_EDGES 20

// Function to create an incidence matrix for an undirected graph
void createIncidenceMatrix(int incidenceMatrix[MAX_VERTICES][MAX_EDGES], int vertices, int edges) {
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < edges; j++) {
            incidenceMatrix[i][j] = 0;  // Initialize matrix with 0
        }
    }

    int u, v;
    for (int i = 0; i < edges; i++) {
        printf("Enter edge %d (u v): ", i + 1);
        scanf("%d %d", &u, &v);
        incidenceMatrix[u][i] = 1; // Mark the vertex-edge incidence
        incidenceMatrix[v][i] = 1; // For undirected graph
    }
}

// Function to display the incidence matrix
void displayIncidenceMatrix(int incidenceMatrix[MAX_VERTICES][MAX_EDGES], int vertices, int edges) {
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < edges; j++) {
            printf("%d ", incidenceMatrix[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int vertices, edges;
    printf("Enter the number of vertices: ");
    scanf("%d", &vertices);
    printf("Enter the number of edges: ");
    scanf("%d", &edges);

    int incidenceMatrix[MAX_VERTICES][MAX_EDGES];
    createIncidenceMatrix(incidenceMatrix, vertices, edges);
    displayIncidenceMatrix(incidenceMatrix, vertices, edges);

    return 0;
}

Space Complexity:

• The space complexity of an incidence matrix is \( O(V \times E) \) , where \( V \) is the number of vertices and \( E \) is the number of edges.

• This representation is useful for edge-specific operations, but it is less space-efficient than the adjacency list for sparse graphs.

Comparison of Graph Representations

Graph Operations

Graphs are an essential data structure used in a variety of applications, including pathfinding, cycle detection, and scheduling tasks. The most commonly used algorithms for graph traversal are Depth First Search (DFS) and Breadth First Search (BFS). We will also explore Topological Sort, which is crucial in handling directed acyclic graphs (DAGs).

Depth First Search (DFS) is a graph traversal technique that explores as far as possible along each branch before backing up. The algorithm starts at a given vertex, marks it as visited, and explores its adjacent vertices recursively (or using a stack). This means it goes deep into the graph, visiting one branch entirely before moving to another branch.

DFS Strategy

1. Visit a Vertex: Start at a given vertex, mark it as visited.

2. Explore Deeper: From the current vertex, explore its adjacent vertices that haven't been visited.

3. Backtrack: If all adjacent vertices are visited, backtrack to the previous vertex to explore other paths.

4. Repeat: Continue the process until all vertices are visited.

DFS can be implemented both recursively (using the call stack) and iteratively (using an explicit stack).

Recursive DFS Implementation

The recursive version of DFS is simple. It uses the system’s call stack to remember the vertices that it needs to revisit later. If there’s an adjacent vertex that hasn’t been visited, the algorithm recursively calls DFS on that vertex.

Strategy:

• Maintain a visited[] array to keep track of the visited vertices.

• Start DFS from a given vertex, mark it as visited, and recursively visit its neighbors.

C Code: Recursive DFS

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

#define MAX_VERTICES 100

// Recursive function for DFS
void DFS(int vertex, bool visited[], int adjMatrix[MAX_VERTICES][MAX_VERTICES], int vertices) {
    visited[vertex] = true;  // Mark the vertex as visited
    printf("%d ", vertex);   // Process the current vertex (visit)

    // Recursively visit all unvisited neighbors
    for (int i = 0; i < vertices; i++) {
        if (adjMatrix[vertex][i] == 1 && !visited[i]) {
            DFS(i, visited, adjMatrix, vertices);
        }
    }
}

int main() {
    int vertices = 4;
    bool visited[MAX_VERTICES] = {false};  // Keep track of visited vertices

    // Adjacency matrix representation of the graph
    int adjMatrix[MAX_VERTICES][MAX_VERTICES] = {
        {0, 1, 1, 0},
        {1, 0, 0, 1},
        {1, 0, 0, 1},
        {0, 1, 1, 0}
    };

    // Perform DFS starting from vertex 0
    printf("DFS starting from vertex 0:\n");
    DFS(0, visited, adjMatrix, vertices);

    return 0;
}

Iterative DFS Implementation

The iterative version of DFS uses an explicit stack to simulate the behavior of the recursive approach. You push the starting vertex onto the stack, and in a loop, keep visiting the vertices, pushing their unvisited neighbors onto the stack.

Strategy:

• Use a stack to simulate recursion.

• Push the starting vertex onto the stack.

• In a loop, pop a vertex, visit it, and push all unvisited neighbors onto the stack.

C Code: Iterative DFS

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

#define MAX_VERTICES 100

void DFSIterative(int startVertex, int adjMatrix[MAX_VERTICES][MAX_VERTICES], int vertices) {
    bool visited[MAX_VERTICES] = {false};  // Track visited vertices
    int stack[MAX_VERTICES];
    int top = -1;  // Initialize an empty stack

    // Push the starting vertex onto the stack
    stack[++top] = startVertex;

    while (top != -1) {
        int currentVertex = stack[top--];  // Pop the vertex from the stack

        if (!visited[currentVertex]) {
            printf("%d ", currentVertex);  // Visit the node
            visited[currentVertex] = true;
        }

        // Push all adjacent unvisited vertices onto the stack
        for (int i = 0; i < vertices; i++) {
            if (adjMatrix[currentVertex][i] == 1 && !visited[i]) {
                stack[++top] = i;
            }
        }
    }
}

int main() {
    int vertices = 4;
    int adjMatrix[MAX_VERTICES][MAX_VERTICES] = {
        {0, 1, 1, 0},
        {1, 0, 0, 1},
        {1, 0, 0, 1},
        {0, 1, 1, 0}
    };

    printf("Iterative DFS starting from vertex 0:\n");
    DFSIterative(0, adjMatrix, vertices);

    return 0;
}

Applications of DFS

1. Cycle Detection: DFS can be used to detect cycles in both directed and undirected graphs.

2. Pathfinding: DFS helps in finding paths between vertices in a graph.

3. Connected Components: DFS can find connected components in an undirected graph.

4. Topological Sorting: DFS is used in topological sorting of directed acyclic graphs (DAGs).

Breadth First Search (BFS) is a graph traversal algorithm that explores all the vertices at the present level (breadth) before moving on to the next level. It is similar to level-order traversal in binary trees. BFS explores neighbors of each vertex first, using a queue to keep track of the vertices to be explored.

BFS Strategy

1. Start with a Vertex: Enqueue the starting vertex, mark it as visited.

2. Process Level by Level: Dequeue the vertex, visit it, and enqueue all its unvisited neighbors.

3. Repeat: Continue this process until the queue is empty, meaning all vertices have been visited.

BFS is generally used when you need to explore vertices layer by layer, or when you want the shortest path in an unweighted graph.

Queue-based Implementation

BFS uses a queue to explore each vertex. The algorithm works by marking a vertex as visited, enqueuing it, and then exploring its neighbors. The queue ensures that we process each level completely before moving deeper into the graph.

Strategy:

• Use a queue to store vertices to be explored.

• Enqueue the starting vertex and mark it as visited.

• Dequeue vertices one by one, visit them, and enqueue their unvisited neighbors.

C Code: BFS

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

#define MAX_VERTICES 100

// Function for BFS
void BFS(int startVertex, int adjMatrix[MAX_VERTICES][MAX_VERTICES], int vertices) {
    bool visited[MAX_VERTICES] = {false};  // Keep track of visited vertices
    int queue[MAX_VERTICES];
    int front = 0, rear = 0;  // Initialize an empty queue

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

    while (front < rear) {
        int currentVertex = queue[front++];  // Dequeue the vertex
        printf("%d ", currentVertex);        // Visit the node

        // Enqueue all adjacent unvisited vertices
        for (int i = 0; i < vertices; i++) {
            if (adjMatrix[currentVertex][i] == 1 && !visited[i]) {
                visited[i] = true;
                queue[rear++] = i;
            }
        }
    }
}

int main() {
    int vertices = 4;
    int adjMatrix[MAX_VERTICES][MAX_VERTICES] = {
        {0, 1, 1, 0},
        {1, 0, 0, 1},
        {1, 0, 0, 1},
        {0, 1, 1, 0}
    };

    printf("BFS starting from vertex 0:\n");
    BFS(0, adjMatrix, vertices);
    return 0;
}

Applications of BFS

1. Shortest Path in Unweighted Graphs: BFS can find the shortest path between two vertices in an unweighted graph.

2. Level-Order Traversal: BFS is used to perform level-order traversal in trees and graphs.

3. Connected Components: BFS helps identify all connected components in a graph.

4. Bipartite Graph Checking: BFS can determine if a graph is bipartite by attempting to color the graph with two colors.

Topological Sort is an ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge \( u \to v \) , vertex \( u \) comes before vertex \( v \) in the ordering. It is used in applications like task scheduling, where some tasks must be completed before others, and dependency resolution in software packages.

Topological Sort Strategy

The idea is to perform a DFS traversal on the graph. As we finish processing a vertex (i.e., after visiting all its neighbors), we add it to a stack. The vertices are popped from the stack at the end to give the topologically sorted order.

Strategy:

• Perform DFS for each vertex.

• As soon as a vertex finishes (i.e., all adjacent vertices are visited), push it to a stack.

• Pop all elements from the stack to get the topologically sorted order.

C Code: Topological Sort using DFS

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

#define MAX_VERTICES 100

// DFS function for Topological Sort
void topologicalSortDFS(int vertex, bool visited[], int adjMatrix[MAX_VERTICES][MAX_VERTICES], int vertices, int* stack, int* top) {
    visited[vertex] = true;

    // Visit all adjacent unvisited vertices
    for (int i = 0; i < vertices; i++) {
        if (adjMatrix[vertex][i] == 1 && !visited[i]) {
            topologicalSortDFS(i, visited, adjMatrix, vertices, stack, top);
        }
    }

    // Push the vertex to the stack after all adjacent vertices are processed
    stack[(*top)++] = vertex;
}

// Function to perform Topological Sort on a graph
void topologicalSort(int adjMatrix[MAX_VERTICES][MAX_VERTICES], int vertices) {
    bool visited[MAX_VERTICES] = {false};  // Track visited vertices
    int stack[MAX_VERTICES];
    int top = 0;

    // Call DFS for all vertices
    for (int i = 0; i < vertices; i++) {
        if (!visited[i]) {
            topologicalSortDFS(i, visited, adjMatrix, vertices, stack, &top);
        }
    }

    // Print vertices in reverse order of the stack to get the topological order
    printf("Topological Sort: ");
    for (int i = top - 1; i >= 0; i--) {
        printf("%d ", stack[i]);
    }
    printf("\n");
}

int main() {
    int vertices = 6;
    int adjMatrix[MAX_VERTICES][MAX_VERTICES] = {
        {0, 1, 1, 0, 0, 0},
        {0, 0, 0, 1, 1, 0},
        {0, 0, 0, 1, 0, 0},
        {0, 0, 0, 0, 0, 1},
        {0, 0, 0, 0, 0, 1},
        {0, 0, 0, 0, 0, 0}
    };

    topologicalSort(adjMatrix, vertices);
    return 0;
}

Applications of Topological Sort

1. Task Scheduling: Topological sorting is used to schedule tasks where certain tasks must be done before others.

2. Dependency Resolution: In software systems, it helps resolve dependencies between libraries or modules.

3. Course Prerequisites: Topological sorting can determine the correct order in which courses should be taken based on prerequisites.

Exercises

1. Print Graph Representation: Write a C program to represent a graph using an adjacency matrix and print the matrix for a given graph with (n) nodes and (m) edges. This will test basic understanding of graph representation.

2. Find Degree of a Node: Implement a function to calculate and return the degree (in-degree and out-degree for directed graphs) of a given node in a graph represented as an adjacency list.

3. Check if Graph is Complete: Write a program to check if a given undirected graph is a complete graph, where every node is connected to every other node, using an adjacency matrix representation.

4. DFS Traversal: Implement Depth First Search (DFS) for a graph using recursion. Start from a given node and traverse all reachable nodes, printing the order of traversal.

5. BFS Traversal: Implement Breadth First Search (BFS) for a graph. Use a queue to traverse the graph starting from a given node and print the order of traversal.

6. Cycle Detection in Undirected Graph: Implement a function to detect a cycle in an undirected graph using DFS. If a cycle is found, return true; otherwise, return false.

7. Cycle Detection in Directed Graph: Write a program to detect a cycle in a directed graph using DFS and backtracking techniques. Output whether the graph contains a cycle or not.

8. Connected Components: Implement an algorithm to find all the connected components in an undirected graph. Output the components as sets of nodes.

9. Topological Sort: Write a function to perform topological sorting of a Directed Acyclic Graph (DAG). Print the sorted order of nodes.