PadhaikoAll subjects

Graphs

Data Structure and Algorithms (ENCT 252)

Open in the Padhaiko app

6.1 Definition, terminologies and types of graphs

Definition

Graph (G = (V, E))

A graph is a non-linear data structure consisting of two finite sets:

  1. (Vertices or Nodes): A non-empty finite set of fundamental entities or points, .
  2. (Edges or Links): A finite set of pairs of vertices representing connections or relationships between vertices, .
Undirected vs. Directed Graph on V = {A, B, C, D}Text
   Undirected Graph                              Directed Graph (Digraph)
         C                                                  C
       /   \                                              ^   ^
      /     \                                            /     \
     A ----- B                                          A ----> B
      \     /                                            \     ^
       \   /                                              v   /
         D                                                  D

   V = {A, B, C, D}                              V = {A, B, C, D}
   E = {(A,B), (A,C), (A,D), (B,C), (B,D)}       E = {<A,B>, <A,C>, <A,D>, <B,C>, <D,B>}

Applications of Graphs

Graph Terminologies

Definition

Fundamental Graph Terminologies

Let be a graph with vertices and edges:

  1. Adjacency and Incidence: Two vertices and are adjacent (neighbors) if there is an edge connecting them; the edge is said to be incident on vertices and .
  2. Degree of a Vertex (): In an undirected graph, the number of edges incident on vertex (with a self-loop counted twice). A vertex with is isolated; a vertex with is a pendant (leaf) vertex.
    • Handshaking Lemma: In any undirected graph, the sum of degrees of all vertices equals twice the number of edges:
  1. In-Degree and Out-Degree (Directed Graph):
    • In-degree (): Number of incoming directed edges having as their head.
    • Out-degree (): Number of outgoing directed edges having as their tail.
    • Across the entire digraph:
  1. Path and Path Length: A path from vertex to vertex is a sequence of vertices with , , and for .
    • The length of an unweighted path is the number of edges ; in a weighted graph, it is the sum of edge weights .
    • A simple path has all distinct vertices (except possibly ).
  2. Cycle (Circuit): A closed path of length in which the starting and ending vertices are the same () and no edge is repeated.
  3. Connectedness:
    • An undirected graph is connected if a path exists between every pair of vertices; otherwise it is disconnected and partitioned into maximal connected components.
    • A directed graph is strongly connected if a directed path exists from to and from to for every pair . It is weakly connected if replacing all directed edges with undirected edges yields a connected graph.
  4. Subgraph and Spanning Subgraph: is a subgraph of if and with endpoints in . If , is a spanning subgraph.

Types of Graphs

Definition

Classification of Graphs

  1. Undirected Graph: Edges have no orientation; an edge can be traversed in both directions ( and ).
  2. Directed Graph (Digraph): Every edge has a fixed direction from to ; .
  3. Weighted Graph (Network): Each edge is assigned a numerical weight representing distance, cost, latency, or capacity.
  4. Unweighted Graph: Edges carry no explicit numerical cost (or all edges have uniform unit weight ).
  5. Simple Graph: Contains neither self-loops (edges connecting a vertex to itself) nor parallel (multiple) edges between the same pair of vertices.
  6. Multigraph: Permits multiple parallel edges between the same pair of vertices, but no self-loops.
  7. Pseudograph: Permits both multiple parallel edges and self-loops .
  8. Complete Graph (): A simple undirected graph in which every pair of distinct vertices is connected by a unique edge. For vertices:
  1. Bipartite Graph: A graph whose vertex set can be partitioned into two disjoint independent sets and (, ) such that every edge connects a vertex in to one in . (Equivalently, a graph is bipartite if and only if it contains no cycle of odd length.)
  2. Complete Bipartite Graph (): A bipartite graph with and in which every vertex of is connected to every vertex of , giving .
  3. Cyclic Graph: A graph containing at least one cycle.
  4. Acyclic Graph: A graph with zero cycles. A directed graph with no directed cycles is called a Directed Acyclic Graph (DAG).
  5. Tree: A connected, acyclic undirected graph. A tree with vertices always has exactly edges.
  6. Forest: A disjoint union of one or more trees (an acyclic undirected graph that need not be connected).
Summary of Graph Types and Edge Bounds
Graph TypeParallel Edges Allowed?Self-Loops Allowed?Characteristic Property / Edge Count
Simple GraphNoNo (undirected) or (directed)
MultigraphYesNoMultiple routes between the same vertex pair
PseudographYesYesParallel edges plus self-loops
Complete Graph ()NoNoEvery vertex has degree ;
Complete Bipartite ()NoNoPartitions ;
TreeNoNoConnected and acyclic;
ForestNoNoAcyclic with connected components;

6.2 Representation of graphs: Adjacency matrix, incidence matrix and adjacency list

To process a graph with vertices and edges in memory, three standard representations are used: Adjacency Matrix, Incidence Matrix, and Adjacency List.

1. Adjacency Matrix

Definition

Adjacency Matrix Representation

An adjacency matrix of a graph with vertices is a array of size :

For an undirected graph, the adjacency matrix is always symmetric ().

Consider the three -vertex graphs from the lecture notes with vertices ordered :

  1. Undirected Graph with edges
  2. Directed Graph with edges
  3. Weighted Directed Graph with edges

2. Incidence Matrix

Definition

Incidence Matrix Representation

An incidence matrix of a graph with vertices and edges is an matrix whose rows correspond to vertices and columns correspond to edges:

Every column of sums to , and the sum of row equals .

Every column of has one and one (column sum ).

For the same -vertex graphs with labeled edges , , , (and in the directed graph), the incidence matrices (rows ; columns ) are:

3. Adjacency List

Definition

Adjacency List Representation

An adjacency list represents a graph as an array adj[0 .. V-1] of pointers, where adj[i] points to a singly linked list of all vertices adjacent to vertex .

Adjacency Lists for the Three 4-Vertex GraphsText
Undirected Graph:            Directed Graph:              Weighted Directed Graph:
A -> [C] -> [D] -> NULL      A -> [C] -> [D] -> NULL      A -> [C|4] -> [D|3] -> NULL
B -> [C] -> [D] -> NULL      B -> [C] -> NULL             B -> [C|2] -> NULL
C -> [A] -> [B] -> NULL      C -> NULL                    C -> NULL
D -> [A] -> [B] -> NULL      D -> [B] -> NULL             D -> [B|5] -> NULL
Adjacency List Representation of a Graph in CC
#include <stdio.h>
#include <stdlib.h>

typedef struct AdjNode {
    int dest;
    int weight;
    struct AdjNode *next;
} AdjNode;

typedef struct Graph {
    int numVertices;
    AdjNode **adjLists;
} Graph;

AdjNode *createNode(int dest, int weight) {
    AdjNode *node = (AdjNode *)malloc(sizeof(AdjNode));
    node->dest = dest;
    node->weight = weight;
    node->next = NULL;
    return node;
}

void addDirectedEdge(Graph *g, int src, int dest, int weight) {
    AdjNode *node = createNode(dest, weight);
    node->next = g->adjLists[src];
    g->adjLists[src] = node;
}
Comparison of Graph Representations
FeatureAdjacency MatrixIncidence MatrixAdjacency List
Space Complexity
Check if
Iterate over neighbors of
Add an edge (resize) (head insert)
Best suited forDense graphs ()Multigraphs, hypergraphs, circuit equationsSparse graphs ()

6.3 Transitive closure and Warshall’s algorithm

Definition

Transitive Closure of a Directed Graph

The transitive closure of a directed graph with vertices is an boolean reachability matrix (often denoted or ) defined by:

Computing the transitive closure by running matrix multiplication or repeated searches can be replaced by Warshall's Algorithm, an dynamic programming method.

Theorem

Warshall's Algorithm for Transitive Closure

Let be the boolean adjacency matrix of a directed graph with vertices . Define if and only if there is a directed path from to whose intermediate vertices belong only to the subset .

For , the matrix is computed from via the boolean recurrence:

After stages, is the transitive closure of .

Warshall's Transitive Closure Algorithm in CC
void warshallTransitiveClosure(int n, int A[n][n], int R[n][n]) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            R[i][j] = A[i][j];

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                R[i][j] = R[i][j] || (R[i][k] && R[k][j]);
            }
        }
    }
}

Trace on the Notes' 4-Vertex Digraph

Consider the digraph on (indexed ) with directed edges , , , and :

Since vertex (row ) has out-degree , row remains all zeros, while vertices can reach every vertex .


6.4 Graph traversals: Breadth-first search, depth-first search and topological sort

Graph traversal is the systematic process of visiting every vertex and edge of a graph exactly once.

Breadth-First Search (BFS)

Definition

Breadth-First Search (BFS)

Breadth-First Search (BFS) traverses a graph level by level outward from a source vertex , visiting all vertices at distance (in number of edges) before visiting any vertex at distance . It uses a FIFO Queue to manage the frontier.

Algorithm:

  1. Initialize visited[v] = 0 for all .
  2. Mark source vertex as visited[s] = 1 and enqueue(Q, s).
  3. While is not empty:
    • u = dequeue(Q) and output u.
    • For every vertex adjacent to : if visited[v] == 0, set visited[v] = 1 and enqueue(Q, v).
Breadth-First Search (BFS) in CC
void bfs(int n, int adj[n][n], int start) {
    int visited[100] = {0}, queue[100];
    int front = 0, rear = 0;

    visited[start] = 1;
    queue[rear++] = start;

    while (front < rear) {
        int u = queue[front++];
        printf("%d ", u);
        for (int v = 0; v < n; v++) {
            if (adj[u][v] && !visited[v]) {
                visited[v] = 1;
                queue[rear++] = v;
            }
        }
    }
}

Depth-First Search (DFS)

Definition

Depth-First Search (DFS)

Depth-First Search (DFS) explores as deeply as possible along each branch before backtracking when a vertex has no unvisited neighbors. It uses a LIFO Stack (either explicitly or via the recursion call stack).

Algorithm:

  1. Initialize visited[v] = 0 for all .
  2. Starting at source vertex , mark visited[u] = 1 and output u.
  3. For each neighbor of : if visited[v] == 0, recursively invoke DFS(v).
  4. Backtrack when all neighbors of have been visited.
Recursive Depth-First Search (DFS) in CC
void dfs(int n, int adj[n][n], int visited[], int u) {
    visited[u] = 1;
    printf("%d ", u);
    for (int v = 0; v < n; v++) {
        if (adj[u][v] && !visited[v]) {
            dfs(n, adj, visited, v);
        }
    }
}

For the tree-structured graph in the notes where connects to , connects to , and connects to :

AspectBreadth-First Search (BFS)Depth-First Search (DFS)
Auxiliary Data StructureFIFO QueueLIFO Stack (or recursion stack)
Exploration StrategyLevel by level (shallowest vertices first)Branch by branch to maximum depth, then backtracks
Shortest Path PropertyGuarantees shortest path (minimum edges) in unweighted graphsDoes not guarantee shortest paths
Time Complexity (adjacency list), (matrix) (adjacency list), (matrix)
Space Complexity (frontier width) (maximum recursion depth)
Key ApplicationsUnweighted shortest paths, web crawlers, peer-to-peer broadcastingCycle detection, topological sorting, strongly connected components, maze solving

Topological Sort

Definition

Topological Sorting of a DAG

A topological sort of a Directed Acyclic Graph (DAG) is a linear ordering of all its vertices such that for every directed edge , vertex appears before vertex in the ordering.

If a directed graph contains a cycle, no topological ordering exists. A DAG may have more than one valid topological order.

Two standard algorithms compute a topological sort:

  1. DFS-Based Topological Sort (Reverse Post-Order):
    • Run DFS across all unvisited vertices.
    • Once a vertex has finished exploring all its outgoing neighbors (post-order finish), push onto a stack.
    • After all vertices are visited, pop elements from the stack to obtain a valid topological ordering.
  2. BFS-Based Topological Sort (Kahn's In-Degree Algorithm):
    • Compute the in-degree for every vertex .
    • Enqueue all vertices with into a queue .
    • While is not empty:
      • Dequeue vertex and append to the topological order.
      • For every outgoing neighbor of : decrement by ; if becomes , enqueue .
    • If fewer than vertices are output when empties, the graph has a cycle.
BFS-Based Topological Sort (Kahn's Algorithm) in CC
void topologicalSortBFS(int n, int adj[n][n]) {
    int indegree[100] = {0}, queue[100], front = 0, rear = 0;

    for (int u = 0; u < n; u++)
        for (int v = 0; v < n; v++)
            if (adj[u][v]) indegree[v]++;

    for (int v = 0; v < n; v++)
        if (indegree[v] == 0) queue[rear++] = v;

    while (front < rear) {
        int u = queue[front++];
        printf("%d ", u);
        for (int v = 0; v < n; v++) {
            if (adj[u][v] && --indegree[v] == 0) {
                queue[rear++] = v;
            }
        }
    }
}

For the 6-vertex DAG in the notes with edges , , , , , :


6.5 Minimum spanning tree: Kruskal’s algorithm and prim’s algorithm

Definition

Spanning Tree and Minimum Spanning Tree (MST)

Let be a connected, undirected graph with vertices.

is minimum among all possible spanning trees of .

Both Prim's Algorithm and Kruskal's Algorithm are greedy algorithms that build an MST step-by-step using the cut property (the lightest edge crossing any cut of is safe to include in an MST).

Prim's Algorithm

Strategy (Vertex-Growing Greedy): Start from an arbitrary seed vertex and grow a single connected tree one edge at a time by always picking the minimum-weight edge that connects a vertex already in (mstSet) to a vertex outside .

Algorithm Steps:

  1. Initialize mstSet = {start_vertex} and key[v] = ∞ for all other vertices (key[start] = 0).
  2. Repeat times:
    • Select the vertex with the minimum key[u] (the lightest edge connecting mstSet to ).
    • Add (and its connecting edge) to mstSet.
    • For every neighbor of : if , update and .
Prim's Minimum Spanning Tree Algorithm in CC
#include <limits.h>

void primMST(int n, int cost[n][n]) {
    int parent[100], key[100], inMST[100] = {0};
    for (int i = 0; i < n; i++) key[i] = INT_MAX;

    key[0] = 0;
    parent[0] = -1;

    for (int count = 0; count < n - 1; count++) {
        int u = -1, minKey = INT_MAX;
        for (int v = 0; v < n; v++) {
            if (!inMST[v] && key[v] < minKey) {
                minKey = key[v];
                u = v;
            }
        }
        inMST[u] = 1;
        for (int v = 0; v < n; v++) {
            if (cost[u][v] && !inMST[v] && cost[u][v] < key[v]) {
                parent[v] = u;
                key[v] = cost[u][v];
            }
        }
    }
}

Trace of Prim's Algorithm (Notes Example)

For the 5-vertex graph on with edges , , , , , , starting at vertex :

Prim's Algorithm Execution Starting from Vertex B
IterationCurrent mstSetCandidate Cut Edges Selected Min EdgeRunning Cost
Init of weight
2 of weight
3 of weight
4 of weight

All vertices are now in mstSet with edges and total MST weight .

Kruskal's Algorithm

Strategy (Edge-Sorting Greedy): Treat every vertex initially as a separate component (forest of single-node trees). Sort all edges in non-decreasing order of weight, and scan them one by one: add an edge to the MST if and only if and belong to different connected components (i.e., adding does not form a cycle), tracked via a Disjoint-Set (Union-Find) structure.

Algorithm Steps:

  1. Sort all edges in non-decreasing order of weight: .
  2. Initialize and place each vertex in its own disjoint set (parent[v] = v).
  3. For each edge in sorted order:
    • If find(u) != find(v) (no cycle is formed):
      • Add to and perform union(u, v).
      • Stop once .
Kruskal's MST Algorithm with Union-Find in CC
typedef struct { int u, v, w; } Edge;

int findRoot(int parent[], int i) {
    while (parent[i] != i) i = parent[i];
    return i;
}

int kruskalMST(int n, int m, Edge edges[]) {
    /* Assume edges[0..m-1] are already sorted in non-decreasing order of w */
    int parent[100], mstWeight = 0, picked = 0;
    for (int i = 0; i < n; i++) parent[i] = i;

    for (int i = 0; i < m && picked < n - 1; i++) {
        int rootU = findRoot(parent, edges[i].u);
        int rootV = findRoot(parent, edges[i].v);
        if (rootU != rootV) {
            parent[rootU] = rootV;
            mstWeight += edges[i].w;
            picked++;
        }
    }
    return mstWeight;
}

Trace of Kruskal's Algorithm (Notes Example)

For the 5-vertex graph on with edges sorted by weight: , , , , , , :

Kruskal's Algorithm Edge-by-Edge Trace
EdgeWeightComponent CheckDecisionConnected Components
find(A) != find(B)Accept ()
find(D) != find(E)Accept ()
find(B) != find(C)Accept ()
find(C) != find(D)Accept () (Stop: edges)
find(A) == find(E)Reject (cycle )—

Total MST cost .

AspectPrim's AlgorithmKruskal's Algorithm
Core ApproachVertex-based: grows a single connected tree from a starting vertexEdge-based: merges a forest of disjoint components using sorted edges
Intermediate StructureAlways remains a single connected tree at every stepForms a forest of disconnected trees that merge into one tree at the end
Cycle AvoidanceImplicitly avoided by only considering edges to Explicitly checked using Union-Find (Disjoint-Set)
Time Complexity (matrix) or (binary heap) or (dominated by sorting edges)
Best Suited ForDense graphs ()Sparse graphs () or when edges are already sorted

6.6 Shortest-paths problems: Dijkstra’s algorithm, Floyd- Warshall algorithm

Definition

Shortest-Path Problems and Edge Relaxation

Given a weighted graph , the path weight of a path is . The shortest-path distance is the minimum path weight over all paths from to (or if no path exists).

  1. Single-Source Shortest Paths (SSSP): Find shortest paths from one fixed source vertex to every other vertex (solved by Dijkstra's Algorithm when ).
  2. All-Pairs Shortest Paths (APSP): Find shortest paths between every pair of vertices (solved by the Floyd–Warshall Algorithm).

Edge Relaxation: Maintaining an upper-bound estimate on , relaxing an edge tests whether going through improves the shortest known path to :

Dijkstra's Algorithm (Single-Source Shortest Path)

Principle: Dijkstra's algorithm is a greedy algorithm that requires non-negative edge weights (). It maintains a visited set of vertices whose final shortest-path distances from source are already determined, and repeatedly selects the unvisited vertex with the smallest tentative distance , adds to , and relaxes all outgoing edges .

Algorithm Steps:

  1. Initialize and for all . Set .
  2. While :
    • Extract the unvisited vertex having the minimum distance and add to .
    • Relax neighbors: For each unvisited neighbor of :
Dijkstra's Single-Source Shortest-Path Algorithm in CC
#include <limits.h>

void dijkstra(int n, int cost[n][n], int src, int dist[]) {
    int visited[100] = {0};
    for (int i = 0; i < n; i++) dist[i] = INT_MAX;
    dist[src] = 0;

    for (int count = 0; count < n - 1; count++) {
        int u = -1, minDist = INT_MAX;
        for (int v = 0; v < n; v++) {
            if (!visited[v] && dist[v] < minDist) {
                minDist = dist[v];
                u = v;
            }
        }
        if (u == -1) break;
        visited[u] = 1;

        for (int v = 0; v < n; v++) {
            if (!visited[v] && cost[u][v] > 0 && dist[u] + cost[u][v] < dist[v]) {
                dist[v] = dist[u] + cost[u][v];
            }
        }
    }
}

Trace of Dijkstra's Algorithm (Notes Example)

Consider the 6-vertex directed weighted graph from the notes on with source and edges: , , , , , , , .

Dijkstra's Algorithm Distance Table from Source A
IterationSelected Visited Set Relaxations Performed
Init—Source initialized to
1,
2,
3
4,
5
6All vertices visited

Floyd–Warshall Algorithm (All-Pairs Shortest Path)

Theorem

Floyd–Warshall All-Pairs Shortest-Path Algorithm

Let be a weighted graph with vertices and no negative-weight cycles. Define as the length of the shortest path from vertex to vertex using only intermediate vertices from .

  1. Base Case (, direct edges only):
  1. Dynamic Programming Recurrence ():

After , gives the shortest-path distance between every pair in time and space. (If any diagonal entry satisfies , the graph contains a negative-weight cycle.)

Floyd-Warshall All-Pairs Shortest-Path Algorithm in CC
#define INF 100000000

void floydWarshall(int n, int D[n][n]) {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (D[i][k] < INF && D[k][j] < INF && D[i][k] + D[k][j] < D[i][j]) {
                    D[i][j] = D[i][k] + D[k][j];
                }
            }
        }
    }
}
AspectDijkstra's AlgorithmFloyd-Warshall Algorithm
Problem SolvedSingle-Source Shortest Path (one source to all )All-Pairs Shortest Path (every pair )
Design ParadigmGreedy algorithmDynamic Programming
Negative Edge WeightsNot allowed (fails if )Allowed (as long as no negative-weight cycle exists)
Time Complexity (matrix) or (min-heap)
Space Complexity

Worked Examples

Example 6.1

6.1 (8 marks)

Use Warshall's algorithm to compute the transitive closure of the -vertex directed graph with vertices and directed edges . Show each intermediate matrix and count the total number of reachable ordered pairs (-entries) at each stage.

Constructing the initial adjacency matrix : From the given edge set , there are direct edges:

Stages and :

  • For (intermediate vertex ): Column is all zeros ( for all ), because no edge enters vertex . Thus no new paths are formed:
  • For (intermediate vertex ): Column has at rows and Row has a at column . Setting and to yields:

Stages and :

  • For (intermediate vertex ): Column has at rows and Row has a at column . Setting to yields:
  • For (intermediate vertex ): Column has at rows and Row has at columns . Every row gains in columns :
Answer:

The final transitive closure matrix is:

with reachable pairs (every vertex reaches since forms a directed cycle, while vertex has in-degree ).

Example 6.2

6.2 (8 marks)

Find the Minimum Spanning Tree (MST) and its total weight using Kruskal's algorithm for the -vertex weighted undirected graph from the lecture notes with vertices and edges: , , , , , , , , , , , , , .

Sorting all edges in non-decreasing order of weight:

Since , the MST requires edges.

Scanning sorted edges and checking for cycles with Union-Find:

Kruskal's Execution on the 9-Vertex Graph
EdgeWeightComponent TestActionEdges Picked
Accept
Accept
Accept
Accept
Accept
Reject (cycle )
Reject (cycle )
Accept
Accept
already in same componentReject (cycle)
Accept (Stop: edges)

Summing the weights of the MST edges:

(Note: Picking instead of yields an alternative valid MST of the exact same weight .)

Answer:

The MST consists of the edges with total minimum weight .

Example 6.3

6.3 (8 marks)

Apply the Floyd–Warshall algorithm to find the all-pairs shortest-path distance matrix for the -vertex directed graph with weighted adjacency matrix:

Stage (allowing vertex as intermediate): Using :

Stage (allowing vertices as intermediates): Using row and column of :

Stages and :

  • For (via vertex ):
  • For (via vertex ):
Answer:

The final all-pairs shortest-path distance matrix is:


Exercises

Exercises

Question 1

How is a graph represented using an adjacency matrix, incidence matrix, and adjacency list? For the undirected graph with and , construct all three representations and verify the Handshaking Lemma.

1. Adjacency Matrix (): Ordering vertices as , set where an edge exists:

2. Incidence Matrix () and 3. Adjacency List:

  • Incidence Matrix (rows ; columns ):
  • Adjacency List:

Verifying the Handshaking Lemma: Row sums give the vertex degrees: , , , .

Answer:

The adjacency matrix has row sums ; the incidence matrix has column sums ; the adjacency list has total nodes; and verifies the Handshaking Lemma.

Question 2

Explain the concept of transitive closure and use Warshall's algorithm to find the transitive closure of the directed graph with and directed edges .

Concept of transitive closure and Warshall's rule: The transitive closure of a digraph is the boolean matrix in which if there is a directed path of length from to , and otherwise. Warshall's algorithm starts with and updates:

Computing for :

  • Initial matrix ( ones):
  • (via ): and ( ones):
  • (via ): and ( ones):
  • (via ): Row is all , so ( ones).
  • (via ): Column has in rows and Row is , so rows become all ( ones):
Answer:

Transitive closure matrix:

Question 3

Determine both the breadth-first (Kahn's in-degree) and depth-first topological sortings for the -vertex Directed Acyclic Graph (DAG) with vertices and directed edges , , , , , .

1. Breadth-First Topological Sort (Kahn's Algorithm): Compute initial in-degrees for all vertices (sum of in-degrees ):

  • Enqueue vertices with in-degree : .
  • Dequeue (output 4): decrement , . .
  • Dequeue (output 5): decrement , . Enqueue .
  • Dequeue (output 0): no outgoing edges. .
  • Dequeue (output 2): decrement . Enqueue .
  • Dequeue (output 3): decrement . Enqueue .
  • Dequeue (output 1): .
  • BFS Topological Order: (or if is dequeued before ).

2. Depth-First Topological Sort: Iterate over vertices and push each vertex onto stack upon finishing all its descendants:

  • Start at : no outgoing neighbors push 0. Stack: [0].
  • Next unvisited : no outgoing neighbors push 1. Stack: [0, 1].
  • Next unvisited : visits ( already visited) push 3, then push 2. Stack: [0, 1, 3, 2].
  • Next unvisited : neighbors already visited push 4. Stack: [0, 1, 3, 2, 4].
  • Next unvisited : neighbors already visited push 5. Stack: [0, 1, 3, 2, 4, 5] (top is 5).
  • Popping the stack from top to bottom yields the DFS Topological Order: .
Answer:
  • BFS (Kahn's) topological order: (or ).
  • DFS topological order: .
Question 4

Differentiate between Breadth-First Search (BFS) and Depth-First Search (DFS). Then construct the Minimum Spanning Tree (MST) using Kruskal's algorithm for the -vertex graph on with weighted edges: , , , , , , , , .

Key differences between BFS and DFS:

  • Data structure: BFS uses a FIFO Queue; DFS uses a LIFO Stack (or recursion).
  • Traversal order: BFS explores level-by-level (breadthwise) and finds shortest paths in unweighted graphs; DFS plunges along a branch to a dead end before backtracking.
  • Complexity: Both run in time with adjacency lists and auxiliary space.

Tracing Kruskal's algorithm on the -vertex graph ( edges needed): Sort all edges in ascending order of weight:

Kruskal's Edge Selection Trace
EdgeWeightCycle CheckAction
Connects and Accept ()
Connects and Accept ()
Connects and Accept ()
Connects and Accept ()
Reject (cycle )
Connects and Accept ()
Reject (cycle )
Connects and Accept ( — Stop)
Answer:

BFS uses a FIFO queue for level-order traversal while DFS uses a LIFO stack for depth-first backtracking. By Kruskal's algorithm, the MST consists of with total minimum cost .

Question 5

Explain Prim's algorithm for finding a Minimum Spanning Tree. Trace Prim's algorithm starting from vertex on the -vertex weighted graph from the lecture notes with vertices and edges: , , , , , , , .

Principle of Prim's algorithm: Prim's algorithm starts from a single root vertex and grows one connected spanning tree mstSet by repeatedly selecting the minimum-weight edge with and until all vertices are included ( edges).

Step-by-step execution starting from vertex :

Prim's Algorithm Trace Starting at Vertex f
IterationmstSetCut Edges AvailableChosen Min EdgeCumulative Weight
1 of weight
2 of weight
3 of weight
4 of weight
5 of weight
Answer:

The MST edges selected by Prim's algorithm from are with total MST weight .

Question 6

Discuss Dijkstra's shortest-path algorithm and find the shortest paths and distances from source vertex to all other vertices in the -vertex undirected weighted graph with vertices and edges: , , , , , , , .

Overview of Dijkstra's algorithm: Dijkstra's algorithm finds single-source shortest paths in a graph with non-negative edge weights by maintaining tentative distances (initialized to and for ) and greedily finalizing the unvisited vertex with minimum , relaxing all its incident edges via .

Distance table trace from source :

Dijkstra's Shortest-Path Trace from Source A
IterationFinalized Visited Set
Init—
1
2
3
4
5
6

At iteration 5, finalizing () checks edge with , so remains via path .

  • Shortest paths from :
    • : distance
    • : distance
    • : distance
    • : distance
    • : distance
    • : distance
Answer:

Shortest distances from : , (), (), (), (), and ().

Past exam questions for Data Structure and Algorithms

← Balanced binary tree · Introduction to red-black tree · B-Tree: Need…Sorting Algorithms →