Last updated on: 10 November 2008 06:01:18 PM

This page will be updated with the following items:
-. As I said before, Graph is the biggest branch in Algorithmic study...
This page is reserved for things that I don't understand now, but hopefully I will, someday in the future =)

Go to Programming Section

Contents:

1. Introduction to Graph
2. Searching a Graph
3. Finding Connected Components (Flood Fill)
4. Minimum Spanning Trees (MST)
5. Single-Source Shortest Paths
6. All-Pairs Shortest Paths
7. Other Graph Algorithms
 - Graph Transpose
 - Eulerian Cycle & Eulerian Path
 - Topological Sort
 - Strongly Connected Components
 - Maximum Flow (later)
 - Maximum Bipartite Matching (later)

All other stuff regarding Graph will be placed here.

Graph Transpose

Graph Transpose problem
Input: directed graph G = (V,E)
Output: graph G^T = (V,E^T), where E^T = {(v,u) in VxV : (u,v) in E}.
            i.e. G^T is G with all its edges reversed.

Describe efficient algorithms for computing G^T from G, for both the adjacency-list and adjacency-matrix representations of G. Analyze the running times of your algorithms.

==>

Using Adjacency List representation, array B is the new array of Adjacency List G^T

for (i=1;i<=p;i++)
  B[i] = nil;

for (i=1;i<=p;i++)
  repeat {
    append i to the end of linked list B[A[i]];
    get next A[i];
  } until A[i] = nil;

Total Time = O(V+E)

Using Adjacency Matrix representation, D[][] is the new adj matrix for G^T

for (i=1;i<=p;i++)
  for (j=1;j<=p;j++)
    D[j][i] = C[i][j];

Total time = O(V²)

Eulerian Cycle & Eulerian Path

Euler Cycle
Input: Connected, directed graph G = (V,E)
Output: A cycle that traverses every edge of G exactly once, although it may visit a vertex more than once.

Theorem: A directed graph possesses an Eulerian cycle iff
1) It is connected
2) For all {v} in {V} indegree(v) = outdegree(v)

Euler Path
Input: Connected, directed graph G = (V,E)
Output: A path from v1 to v2, that traverses every edge of G exactly once, although it may visit a vertex more than once.

Theorem: A directed graph possesses an Eulerian path iff
1) It is connected
2) For all {v} in {V} indegree(v) = outdegree(v) with the possible exception of two vertices v1,v2 in which case,
a) indegree(v1) = outdegree(v2) + 1
b) indegree(v2) = outdegree(v1) - 1

Not yet known: Finding O(E)-time algorithm to find an Euler tour of G if exist, using merging of edge-disjoint cycles (CLR chapter 23 problem 23-3)

Topological Sort

Topological Sort problem
Input: A directed acyclic graph (DAG) G = (V,E)
Output: A linear ordering of all vertices in V such that if G contains an edge (u,v), then u appears before v in the ordering.

If drawn on a diagram, Topological Sort can be seen as a vertices along horizontal line, where all directed edges go from left to right.

Note: A directed graph G is acylic if and only if a DFS of G yields no back edge.

Topological-Sort(G)
1. call DFS(G) to compute finishing times f[v] for each vertex v
2. as each vertex is finished, insert it onto the front of a linked list
3. return the linked list of vertices

Topological-Sort runs in O(V+E) ~~ due to DFS

Strongly Connected Components

Strongly Connected Components problem
Input: A directed graph G = (V,E)
Output: All strongly connected components of G, where in strongly connected component, all pair of vertices u and v in that component, we have u ~~> v and v ~~> u, i.e. u and v are reachable from each other.

Strongly-Connected-Components(G)
1. call DFS(G) to compute finishing times f[u] for each vertex u ~~ O(V+E)
2. compute GT, inversing all edges in G ~~ O(V+E) using adjacency list
3. call DFS(GT), but in the main loop of DFS, consider the vertices in order of decreasing
    f[u] as computed in step 1 ~~ O(V+E)
4. output the vertices of each tree in the depth-first forest of step 3 as a separate
    strongly connected component

Strongly-Connected-Components runs in O(3(V+E)) ~~ O(V+E)

Theorems for SCC:
1. if two vertices are in the same SCC, the no path between them ever leaves the SCC.
2. in any DFS, all vertices in the same SCC are placed in the same depth-first tree.
3. other lemmas in CLR is still unclear for me... will be added later

More will be added here LATER !!!

PREVIOUS - NEXT