Graph algorithms formulas for GATE Data Structures and Algorithms

Use the matrix when the graph is dense (E close to V^2) or constant-time edge checks are needed; use the list when the graph is sparse (E much smaller than V^2). An undirected graph's adjacency lists hold 2E entries in total (each edge appears in both endpoints' lists); a directed graph's hold E.

The degree sum counts every undirected edge once from each end. Consequence: every undirected graph has an even number of odd-degree vertices. In a directed graph, the sum of in-degrees = the sum of out-degrees = E.

Exactly one of the two holds. The first means v is a descendant of u in the DFS forest (the intervals are nested). The second means neither is a descendant of the other (the intervals are disjoint). Partial overlap, d[u] < d[v] < f[u] < f[v], is impossible.

The first holds for any spanning tree of a connected graph on V vertices, whatever the weights. The second is for a graph with k connected components, where Kruskal run to completion produces a minimum spanning forest.

For example, K_4 has 4^2 = 16 spanning trees. This counts spanning trees, not MSTs; with distinct weights, exactly one of them is the MST.

Correctness is guaranteed only when all edge weights are non-negative. The array version suits dense graphs (E close to V^2); the binary-heap version suits sparse graphs (E much smaller than V^2).

Each of the V−1 rounds scans all E edges once; the extra negative-cycle check costs another O(E).

d_k[i][j] is the length of the shortest path from i to j whose intermediate vertices all lie in {1,...,k}. d_0 is the input: d_0[i][i] = 0, d_0[i][j] = w(i,j) where a direct edge exists, and infinity otherwise. The answer is d_V.

Three nested loops over all V vertices. It is correct with negative edge weights as long as there is no negative-weight cycle, and it detects one if present. Replacing min with OR and + with AND gives the transitive-closure (reachability) algorithm, also O(V^3).