Formula Sheets: Graphs | Programming and Data Structures - Computer Science Engineering (CSE) PDF Download

 Page 1


Graphs F orm ula Sheet
Graph Basics
• Definition : G = (V,E) , where V is set of v ertices (|V| =n ), E is set of edges (|E| =m ).
• T yp es : Directed/Undirected, W eigh ted/Un w eigh ted, Cyclic/A cyclic.
• Degree : deg(v) = n um b er of edges inciden t to v ,
?
deg(v
i
) = 2m (undirected).
• Directed Graph : In-degree deg
in
(v) , Out-degree deg
out
(v) ,
?
deg
in
(v) =
?
deg
out
(v) =m .
• P ath Length : Num b er of edges in path, or sum of edge w eigh ts (w eigh ted graph).
Graph Represen tation
• A djacency Matrix : A[n][n] , A[i][j] = 1 (un w eigh ted) or w eigh t (w eigh ted) if edge (i,j) exists,
else 0.
– Space Complexit y: O(n
2
) .
– Edge Chec k: O(1) .
– Neigh b or T ra v ersal: O(n) .
• A djacency List : Arra y of lists, eac h v ertex v stores list of neigh b ors.
– Space Complexit y: O(n+m) (undirected), O(n+m) (directed).
– Edge Chec k: O( deg(v)) .
– Neigh b or T ra v ersal: O( deg(v)) .
• Edge List : Store edges as (u,v,w) , where w is w eigh t.
– Space Complexit y: O(m) .
– Edge Chec k: O(m) .
Graph T ra v ersal
• Depth-First Searc h (DFS) :
– Time Complexit y: O(n+m) (adjacency list), O(n
2
) (adjacency matrix).
– Space Complexit y: O(n) (recursion stac k or visited arra y).
– Recurrence: T(v) =
?
neigh b ors u
T(u)+O(1) , total O(n+m) .
– Applications: Cycle detection, connected comp onen ts, top ological sorting.
• Breadth-First Searc h (BFS) :
– Time Complexit y: O(n+m) (adjacency list), O(n
2
) (adjacency matrix).
– Space Complexit y: O(n) (queue and vis ited arra y).
– Shortest P ath (Un w eigh ted): dist(v) = lev el(v) , Time Complexit y O(n+m) .
– Applications: Shortest path, bipartite c hec king, connected comp onen ts.
Flo y d-W arshall Algorithm
• Purp ose : All-pairs shortest paths in w eigh ted graph (handles negativ e w eigh ts, no negativ e cycles).
• F orm ula : D[i][j]
(k)
= min(D[i][j]
(k-1)
,D[i][k]
(k-1)
+D[k][j]
(k-1)
) , where D[i][j]
(k)
is shortest
path from i to j using v ertices{1,2,...,k} .
• Time Complexit y : O(n
3
) .
• Space Complexit y : O(n
2
) (distance matrix), O(n
2
) for predecessor matrix.
• Initialization : D[i][j] =w(i,j) if edge exists,8 otherwise, D[i][i] = 0 .
• Negativ e Cycle Detection : D[i][i]< 0 for an y i .
1
Page 2


Graphs F orm ula Sheet
Graph Basics
• Definition : G = (V,E) , where V is set of v ertices (|V| =n ), E is set of edges (|E| =m ).
• T yp es : Directed/Undirected, W eigh ted/Un w eigh ted, Cyclic/A cyclic.
• Degree : deg(v) = n um b er of edges inciden t to v ,
?
deg(v
i
) = 2m (undirected).
• Directed Graph : In-degree deg
in
(v) , Out-degree deg
out
(v) ,
?
deg
in
(v) =
?
deg
out
(v) =m .
• P ath Length : Num b er of edges in path, or sum of edge w eigh ts (w eigh ted graph).
Graph Represen tation
• A djacency Matrix : A[n][n] , A[i][j] = 1 (un w eigh ted) or w eigh t (w eigh ted) if edge (i,j) exists,
else 0.
– Space Complexit y: O(n
2
) .
– Edge Chec k: O(1) .
– Neigh b or T ra v ersal: O(n) .
• A djacency List : Arra y of lists, eac h v ertex v stores list of neigh b ors.
– Space Complexit y: O(n+m) (undirected), O(n+m) (directed).
– Edge Chec k: O( deg(v)) .
– Neigh b or T ra v ersal: O( deg(v)) .
• Edge List : Store edges as (u,v,w) , where w is w eigh t.
– Space Complexit y: O(m) .
– Edge Chec k: O(m) .
Graph T ra v ersal
• Depth-First Searc h (DFS) :
– Time Complexit y: O(n+m) (adjacency list), O(n
2
) (adjacency matrix).
– Space Complexit y: O(n) (recursion stac k or visited arra y).
– Recurrence: T(v) =
?
neigh b ors u
T(u)+O(1) , total O(n+m) .
– Applications: Cycle detection, connected comp onen ts, top ological sorting.
• Breadth-First Searc h (BFS) :
– Time Complexit y: O(n+m) (adjacency list), O(n
2
) (adjacency matrix).
– Space Complexit y: O(n) (queue and vis ited arra y).
– Shortest P ath (Un w eigh ted): dist(v) = lev el(v) , Time Complexit y O(n+m) .
– Applications: Shortest path, bipartite c hec king, connected comp onen ts.
Flo y d-W arshall Algorithm
• Purp ose : All-pairs shortest paths in w eigh ted graph (handles negativ e w eigh ts, no negativ e cycles).
• F orm ula : D[i][j]
(k)
= min(D[i][j]
(k-1)
,D[i][k]
(k-1)
+D[k][j]
(k-1)
) , where D[i][j]
(k)
is shortest
path from i to j using v ertices{1,2,...,k} .
• Time Complexit y : O(n
3
) .
• Space Complexit y : O(n
2
) (distance matrix), O(n
2
) for predecessor matrix.
• Initialization : D[i][j] =w(i,j) if edge exists,8 otherwise, D[i][i] = 0 .
• Negativ e Cycle Detection : D[i][i]< 0 for an y i .
1
T op ological Sorting
• Purp ose : Linear ordering of v ertices in D A G (Directed A cyclic Graph) suc h that u? v implies
u b efore v .
• Algorithms :
– DFS-Based: P ostorder rev erse, Time Complexit y O(n+m) , Space Complexit y O(n) .
– Kahn’s Algorithm: Remo v e no des with deg
in
= 0 , Time Complexit y O(n +m) , Space Com-
plexit y O(n) (queue).
• Condition : Graph m ust b e D A G, cycle detection via DFS or Kahn’s (O(n+m) ).
• Num b er of T op ological Orders : Exp onen tial in general, O(n!) for complete D A G.
Spanning T ree
• Definition : Subgraph of undirected connected graph, includes all v ertices, n-1 edges, no cycles.
• Minim um Spanning T ree (MST) :
– Kruskal’s Algorithm: Sort edges, add non-cycle edges, Time Complexit y O(mlogm) , Space
Complexit y O(n+m) .
– Prim’s Algorithm: Gro w tree from v ertex, use priorit y queue, Time Complexit y O(mlogn)
(binary heap), O(n
2
) (arra y).
– T otal W eigh t: W
MST
=
?
w(e
i
) , where e
i
? MST.
• Num b er of Spanning T rees (Complete Graph) : n
n-2
(Ca yley’s form ula).
• Space Complexit y : O(n) for visited arra y , O(n) for priorit y queue i n Prim’s.
Basic Op erations
• A dd Edge : O(1) (adjacency list), O(1) (adjacency matrix).
• Remo v e Edge : O( deg(v)) (adjacency list), O(1) (adjacency matrix).
• A dd V ertex : O(1) (adjacency list), O(n) (adjacency matrix).
• Connected Comp onen ts : DFS/BFS, Time Complexit y O(n+m) , Space Complexit y O(n) .
• Cycle Detection :
– Undirected: DFS/BFS, O(n+m) .
– Directed: DFS, O(n+m) , c hec k bac k edges.
Applications
• DFS : T op ological sorting, cycle detection, strongly connected comp onen ts (K osara ju’s,O(n+m) ).
• BFS : Shor test path (un w eigh ted), bipartite graph c hec k, flo o d fill.
• Flo yd-W arshall : All-pairs shortest paths, transitiv e closure (O(n
3
) ).
• MST : Net w ork design, c lustering, appro ximation algorithms.
• T op ological Sorting : Course sc heduling, build systems, dep endency resolution.
2
Page 3


Graphs F orm ula Sheet
Graph Basics
• Definition : G = (V,E) , where V is set of v ertices (|V| =n ), E is set of edges (|E| =m ).
• T yp es : Directed/Undirected, W eigh ted/Un w eigh ted, Cyclic/A cyclic.
• Degree : deg(v) = n um b er of edges inciden t to v ,
?
deg(v
i
) = 2m (undirected).
• Directed Graph : In-degree deg
in
(v) , Out-degree deg
out
(v) ,
?
deg
in
(v) =
?
deg
out
(v) =m .
• P ath Length : Num b er of edges in path, or sum of edge w eigh ts (w eigh ted graph).
Graph Represen tation
• A djacency Matrix : A[n][n] , A[i][j] = 1 (un w eigh ted) or w eigh t (w eigh ted) if edge (i,j) exists,
else 0.
– Space Complexit y: O(n
2
) .
– Edge Chec k: O(1) .
– Neigh b or T ra v ersal: O(n) .
• A djacency List : Arra y of lists, eac h v ertex v stores list of neigh b ors.
– Space Complexit y: O(n+m) (undirected), O(n+m) (directed).
– Edge Chec k: O( deg(v)) .
– Neigh b or T ra v ersal: O( deg(v)) .
• Edge List : Store edges as (u,v,w) , where w is w eigh t.
– Space Complexit y: O(m) .
– Edge Chec k: O(m) .
Graph T ra v ersal
• Depth-First Searc h (DFS) :
– Time Complexit y: O(n+m) (adjacency list), O(n
2
) (adjacency matrix).
– Space Complexit y: O(n) (recursion stac k or visited arra y).
– Recurrence: T(v) =
?
neigh b ors u
T(u)+O(1) , total O(n+m) .
– Applications: Cycle detection, connected comp onen ts, top ological sorting.
• Breadth-First Searc h (BFS) :
– Time Complexit y: O(n+m) (adjacency list), O(n
2
) (adjacency matrix).
– Space Complexit y: O(n) (queue and vis ited arra y).
– Shortest P ath (Un w eigh ted): dist(v) = lev el(v) , Time Complexit y O(n+m) .
– Applications: Shortest path, bipartite c hec king, connected comp onen ts.
Flo y d-W arshall Algorithm
• Purp ose : All-pairs shortest paths in w eigh ted graph (handles negativ e w eigh ts, no negativ e cycles).
• F orm ula : D[i][j]
(k)
= min(D[i][j]
(k-1)
,D[i][k]
(k-1)
+D[k][j]
(k-1)
) , where D[i][j]
(k)
is shortest
path from i to j using v ertices{1,2,...,k} .
• Time Complexit y : O(n
3
) .
• Space Complexit y : O(n
2
) (distance matrix), O(n
2
) for predecessor matrix.
• Initialization : D[i][j] =w(i,j) if edge exists,8 otherwise, D[i][i] = 0 .
• Negativ e Cycle Detection : D[i][i]< 0 for an y i .
1
T op ological Sorting
• Purp ose : Linear ordering of v ertices in D A G (Directed A cyclic Graph) suc h that u? v implies
u b efore v .
• Algorithms :
– DFS-Based: P ostorder rev erse, Time Complexit y O(n+m) , Space Complexit y O(n) .
– Kahn’s Algorithm: Remo v e no des with deg
in
= 0 , Time Complexit y O(n +m) , Space Com-
plexit y O(n) (queue).
• Condition : Graph m ust b e D A G, cycle detection via DFS or Kahn’s (O(n+m) ).
• Num b er of T op ological Orders : Exp onen tial in general, O(n!) for complete D A G.
Spanning T ree
• Definition : Subgraph of undirected connected graph, includes all v ertices, n-1 edges, no cycles.
• Minim um Spanning T ree (MST) :
– Kruskal’s Algorithm: Sort edges, add non-cycle edges, Time Complexit y O(mlogm) , Space
Complexit y O(n+m) .
– Prim’s Algorithm: Gro w tree from v ertex, use priorit y queue, Time Complexit y O(mlogn)
(binary heap), O(n
2
) (arra y).
– T otal W eigh t: W
MST
=
?
w(e
i
) , where e
i
? MST.
• Num b er of Spanning T rees (Complete Graph) : n
n-2
(Ca yley’s form ula).
• Space Complexit y : O(n) for visited arra y , O(n) for priorit y queue i n Prim’s.
Basic Op erations
• A dd Edge : O(1) (adjacency list), O(1) (adjacency matrix).
• Remo v e Edge : O( deg(v)) (adjacency list), O(1) (adjacency matrix).
• A dd V ertex : O(1) (adjacency list), O(n) (adjacency matrix).
• Connected Comp onen ts : DFS/BFS, Time Complexit y O(n+m) , Space Complexit y O(n) .
• Cycle Detection :
– Undirected: DFS/BFS, O(n+m) .
– Directed: DFS, O(n+m) , c hec k bac k edges.
Applications
• DFS : T op ological sorting, cycle detection, strongly connected comp onen ts (K osara ju’s,O(n+m) ).
• BFS : Shor test path (un w eigh ted), bipartite graph c hec k, flo o d fill.
• Flo yd-W arshall : All-pairs shortest paths, transitiv e closure (O(n
3
) ).
• MST : Net w ork design, c lustering, appro ximation algorithms.
• T op ological Sorting : Course sc heduling, build systems, dep endency resolution.
2
P e rformance Metrics
• Time Complexit y Comparison :
– T ra v ersal: O(n+m) (list), O(n
2
) (matrix).
– Flo yd-W arshall: O(n
3
) .
– MST: O(mlogn) (Kruskal/Prim with heap).
– T op ological Sort: O(n+m) .
• Space Complexit y :
– A djacency List: O(n+m) , Matrix: O(n
2
) .
– T ra v ersal: O(n) (stac k/queue).
– Flo yd-W arshall: O(n
2
) .
– MST: O(n+m) (Kruskal), O(n) (Prim with heap).
• Scalabilit y :
– Sparse Graph (m«n
2
): Use adjacency list.
– Dense Graph (m˜n
2
): Matrix more space-e?icien t.
• Cac he E?iciency : List b etter for sparse graphs, matrix w orse due to O(n
2
) access.
3