Graphs
Open in the Padhaiko app6.1 Definition, terminologies and types of graphs
Graph (G = (V, E))
A graph is a non-linear data structure consisting of two finite sets:
- (Vertices or Nodes): A non-empty finite set of fundamental entities or points, .
- (Edges or Links): A finite set of pairs of vertices representing connections or relationships between vertices, .
- In an undirected graph, each edge is an unordered pair , written , meaning traversal is bidirectional between and .
- In a directed graph (digraph), each edge is an ordered pair directed from the initial vertex (tail) to the terminal vertex (head) .
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
Fundamental Graph Terminologies
Let be a graph with vertices and edges:
- 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 .
- 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:
- 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:
- 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 ).
- Cycle (Circuit): A closed path of length in which the starting and ending vertices are the same () and no edge is repeated.
- 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.
- Subgraph and Spanning Subgraph: is a subgraph of if and with endpoints in . If , is a spanning subgraph.
Types of Graphs
Classification of Graphs
- Undirected Graph: Edges have no orientation; an edge can be traversed in both directions ( and ).
- Directed Graph (Digraph): Every edge has a fixed direction from to ; .
- Weighted Graph (Network): Each edge is assigned a numerical weight representing distance, cost, latency, or capacity.
- Unweighted Graph: Edges carry no explicit numerical cost (or all edges have uniform unit weight ).
- Simple Graph: Contains neither self-loops (edges connecting a vertex to itself) nor parallel (multiple) edges between the same pair of vertices.
- Multigraph: Permits multiple parallel edges between the same pair of vertices, but no self-loops.
- Pseudograph: Permits both multiple parallel edges and self-loops .
- Complete Graph (): A simple undirected graph in which every pair of distinct vertices is connected by a unique edge. For vertices:
- 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.)
- Complete Bipartite Graph (): A bipartite graph with and in which every vertex of is connected to every vertex of , giving .
- Cyclic Graph: A graph containing at least one cycle.
- Acyclic Graph: A graph with zero cycles. A directed graph with no directed cycles is called a Directed Acyclic Graph (DAG).
- Tree: A connected, acyclic undirected graph. A tree with vertices always has exactly edges.
- Forest: A disjoint union of one or more trees (an acyclic undirected graph that need not be connected).
| Graph Type | Parallel Edges Allowed? | Self-Loops Allowed? | Characteristic Property / Edge Count |
|---|---|---|---|
| Simple Graph | No | No | (undirected) or (directed) |
| Multigraph | Yes | No | Multiple routes between the same vertex pair |
| Pseudograph | Yes | Yes | Parallel edges plus self-loops |
| Complete Graph () | No | No | Every vertex has degree ; |
| Complete Bipartite () | No | No | Partitions ; |
| Tree | No | No | Connected and acyclic; |
| Forest | No | No | Acyclic 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
Adjacency Matrix Representation
An adjacency matrix of a graph with vertices is a array of size :
- Unweighted Graph:
- Weighted Graph:
For an undirected graph, the adjacency matrix is always symmetric ().
Consider the three -vertex graphs from the lecture notes with vertices ordered :
- Undirected Graph with edges
- Directed Graph with edges
- Weighted Directed Graph with edges
2. Incidence Matrix
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:
- Undirected Graph:
Every column of sums to , and the sum of row equals .
- Directed Graph (without self-loops):
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
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 .
- In an undirected graph, each edge appears twice (once in
adj[u]and once inadj[v]), so the total number of list nodes is . - In a directed graph, each edge appears once (in
adj[u]), so the total number of list nodes is . - In a weighted graph, each list node stores both the neighbor vertex index and the edge weight.
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#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;
}| Feature | Adjacency Matrix | Incidence Matrix | Adjacency List |
|---|---|---|---|
| Space Complexity | |||
| Check if | |||
| Iterate over neighbors of | |||
| Add an edge | (resize) | (head insert) | |
| Best suited for | Dense graphs () | Multigraphs, hypergraphs, circuit equations | Sparse graphs () |
6.3 Transitive closure and Warshall’s algorithm
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.
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 .
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)
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:
- Initialize
visited[v] = 0for all . - Mark source vertex as
visited[s] = 1andenqueue(Q, s). - While is not empty:
u = dequeue(Q)and outputu.- For every vertex adjacent to : if
visited[v] == 0, setvisited[v] = 1andenqueue(Q, v).
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)
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:
- Initialize
visited[v] = 0for all . - Starting at source vertex , mark
visited[u] = 1and outputu. - For each neighbor of : if
visited[v] == 0, recursively invokeDFS(v). - Backtrack when all neighbors of have been visited.
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 :
- BFS order from : (level : ; level : ; level : ).
- DFS order from : (explores left subtree completely before ).
| Aspect | Breadth-First Search (BFS) | Depth-First Search (DFS) |
|---|---|---|
| Auxiliary Data Structure | FIFO Queue | LIFO Stack (or recursion stack) |
| Exploration Strategy | Level by level (shallowest vertices first) | Branch by branch to maximum depth, then backtracks |
| Shortest Path Property | Guarantees shortest path (minimum edges) in unweighted graphs | Does not guarantee shortest paths |
| Time Complexity | (adjacency list), (matrix) | (adjacency list), (matrix) |
| Space Complexity | (frontier width) | (maximum recursion depth) |
| Key Applications | Unweighted shortest paths, web crawlers, peer-to-peer broadcasting | Cycle detection, topological sorting, strongly connected components, maze solving |
Topological Sort
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:
- 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.
- 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.
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 , , , , , :
- Initial in-degrees: .
- Starting with in-degree vertices , valid topological orderings include and .
6.5 Minimum spanning tree: Kruskal’s algorithm and prim’s algorithm
Spanning Tree and Minimum Spanning Tree (MST)
Let be a connected, undirected graph with vertices.
- A spanning tree of is a connected, acyclic subgraph where includes all vertices and has exactly:
- If is weighted with edge weight function , a Minimum Spanning Tree (MST) is a spanning tree whose total edge weight
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:
- Initialize
mstSet = {start_vertex}andkey[v] = ∞for all other vertices (key[start] = 0). - Repeat times:
- Select the vertex with the minimum
key[u](the lightest edge connectingmstSetto ). - Add (and its connecting edge) to
mstSet. - For every neighbor of : if , update and .
- Select the vertex with the minimum
#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 :
| Iteration | Current mstSet | Candidate Cut Edges | Selected Min Edge | Running 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:
- Sort all edges in non-decreasing order of weight: .
- Initialize and place each vertex in its own disjoint set (
parent[v] = v). - For each edge in sorted order:
- If
find(u) != find(v)(no cycle is formed):- Add to and perform
union(u, v). - Stop once .
- Add to and perform
- If
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: , , , , , , :
| Edge | Weight | Component Check | Decision | Connected 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 .
| Aspect | Prim's Algorithm | Kruskal's Algorithm |
|---|---|---|
| Core Approach | Vertex-based: grows a single connected tree from a starting vertex | Edge-based: merges a forest of disjoint components using sorted edges |
| Intermediate Structure | Always remains a single connected tree at every step | Forms a forest of disconnected trees that merge into one tree at the end |
| Cycle Avoidance | Implicitly 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 For | Dense graphs () | Sparse graphs () or when edges are already sorted |
6.6 Shortest-paths problems: Dijkstra’s algorithm, Floyd- Warshall algorithm
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).
- Single-Source Shortest Paths (SSSP): Find shortest paths from one fixed source vertex to every other vertex (solved by Dijkstra's Algorithm when ).
- 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:
- Initialize and for all . Set .
- While :
- Extract the unvisited vertex having the minimum distance and add to .
- Relax neighbors: For each unvisited neighbor of :
#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: , , , , , , , .
| Iteration | Selected | Visited Set | Relaxations Performed | ||||||
|---|---|---|---|---|---|---|---|---|---|
| Init | — | Source initialized to | |||||||
| 1 | , | ||||||||
| 2 | , | ||||||||
| 3 | |||||||||
| 4 | , | ||||||||
| 5 | |||||||||
| 6 | All vertices visited |
- Shortest paths from :
- (cost )
- (cost )
- (cost )
- (cost )
- (cost )
Floyd–Warshall Algorithm (All-Pairs Shortest Path)
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 .
- Base Case (, direct edges only):
- 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.)
#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];
}
}
}
}
}| Aspect | Dijkstra's Algorithm | Floyd-Warshall Algorithm |
|---|---|---|
| Problem Solved | Single-Source Shortest Path (one source to all ) | All-Pairs Shortest Path (every pair ) |
| Design Paradigm | Greedy algorithm | Dynamic Programming |
| Negative Edge Weights | Not allowed (fails if ) | Allowed (as long as no negative-weight cycle exists) |
| Time Complexity | (matrix) or (min-heap) | |
| Space Complexity |
Worked Examples
6.1
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 :
The final transitive closure matrix is:
with reachable pairs (every vertex reaches since forms a directed cycle, while vertex has in-degree ).
6.2
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:
| Edge | Weight | Component Test | Action | Edges Picked |
|---|---|---|---|---|
| Accept | ||||
| Accept | ||||
| Accept | ||||
| Accept | ||||
| Accept | ||||
| Reject (cycle ) | ||||
| Reject (cycle ) | ||||
| Accept | ||||
| Accept | ||||
| already in same component | Reject (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 .)
The MST consists of the edges with total minimum weight .
6.3
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 ):
The final all-pairs shortest-path distance matrix is:
Exercises
Exercises
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: , , , .
The adjacency matrix has row sums ; the incidence matrix has column sums ; the adjacency list has total nodes; and verifies the Handshaking Lemma.
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):
Transitive closure matrix:
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 push2. 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 is5). - Popping the stack from top to bottom yields the DFS Topological Order: .
- BFS (Kahn's) topological order: (or ).
- DFS topological order: .
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:
| Edge | Weight | Cycle Check | Action |
|---|---|---|---|
| Connects and | Accept () | ||
| Connects and | Accept () | ||
| Connects and | Accept () | ||
| Connects and | Accept () | ||
| Reject (cycle ) | |||
| Connects and | Accept () | ||
| Reject (cycle ) | |||
| Connects and | Accept ( — Stop) |
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 .
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 :
| Iteration | mstSet | Cut Edges Available | Chosen Min Edge | Cumulative Weight |
|---|---|---|---|---|
| 1 | of weight | |||
| 2 | of weight | |||
| 3 | of weight | |||
| 4 | of weight | |||
| 5 | of weight |
The MST edges selected by Prim's algorithm from are with total MST weight .
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 :
| Iteration | Finalized | 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
Shortest distances from : , (), (), (), (), and ().