Topological Sort

  • why we need topsort？
    AOV network
    AOE network
  • features:
    • it must be a dag if feasible
    • a precedence relation which is both transitive(i->k,k->j,i->j) and irreflexive(i->i is impossible)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//T=O(|V|^2)
// :(
void Topsort(Graph G)
{
    Vertex V,W;
    for(int cnt=0;cnt<NumVertex;cnt++)
    {
        V=findNewVertexOfDegreeZero();
        if(V is not a vertex)
        {
            Error("Graph has a cycle");
        }
        TopNum[V]=cnt; //or output V
        for(each W adjacent to V)
        {
            Indegree[W]--;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void Topsort(Graph G)
{
    Queue Q; // stack ok
    int cnt=0;
    Vertex V,W;
    Q=CreateQueue(NumVertex);
    MakeEmpty(Q);
    for(each Vertex V)
    {
        if(Indegree[V]==0)
        {
            Enqueue(V,Q);
        }
    }

    while(Q is not empty)
    {
        V=Dequeue(Q);
        TopNum[V]=cnt;
        cnt++;
        for(each vertex W adjacent to V)
        {
            Indegree[W]--;
            if(Indegree[W]==0)
            {
                Enqueue(W,Q);
            }
        }
    }
    if(cnt!=NumVertex)
    {
        Error("Graph has a cycle");
    }
    Dispose(Q);
}

Shortest Path

Unweighted Graph

BFS

1
2
3
4
5
/*
Table[i].Dist: distance from s to vi
Table[i].Path: initialized to be 0, for tracking
Table[i].Known: if checked
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//T=O(|V|^2)
// :(
void Unweighted(Table T)
{
    int curdist;
    Vertex V,W;
    for(int curdis=0;curdis<NumVertex;curdis++)
    {
        for(each Vertex V) //improvement done here
        {
            if(T[V].Known==0 && T[V].Dist==curdist)
            {
                T[V].Known=1;
                for(each Vertex W adjacent to V)
                {
                    if(T[W].Dist==Infinity)
                    {
                        T[W].Dist=T[V]+1;
                        T[W].Path=V;
                    }
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//T=O(|V|+|E|)
void Unweighted(Table T)
{
    Queue Q;
    Vertex V,W;
    Q=CreateQueue(Numvertex);
    MakeEmpty(Q);
    Enqueue(S,Q);
    while(Q is not empty)
    {
        V=Dequeue(Q);
        T[V].Known=1; //actually not need for Known
        for(each W adjacent to V)
        {
            if(T[W].Dist==Infinity)
            {
                T[W].Dist=T[V].Dist+1;
                T[W].Path=V;
                Enqueue(W,Q);
            }
        }
    }
    Dispose(Q);
}

Weighted Graph

Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//T complexity depends how to function smallest unknown distance Vertex
void Dijkstra(Table T)
{
    Vertex V,W;
    for(;;)
    {
        V=smallest unknown distance Vertex;
        if(V is not Vertex)
        {
            break;
        }
        T[V].Known=1;
        for(each W adjacent to V)
        {
            if(T[W].Known==0 && T[W].Dist>T[V].Dist+Cvw)
            {
                T[W].Dist=T[V].Dist+Cvw;
                T[W].Path=V;
            }
        }
    }
}

How to find smallest unknown distance Vertex?

  • Implementation1
    • scan the table
    • T=O(|V|^2+|E|)
  • Implementation2
    • keep distances in a priority queue and call deletemin, O(log|V|)
    • Decrease( T[W].Dist to T[V].Dist+Cvw );
      • Method 1: DecreaseKey – O(log|V|)
        T = O(|V|log|V|+|E|log|V|) = O(|E|log|V|)
      • Method 2: insert W with updated Dist into the priority queue
        T = O(|E|log|V|) but requires |E| DeleteMin with |E| space

SPFA

worst case: O(|E|)
best case: O(|E||V|)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void WeightNegtive(Table T)
{
    Queue Q=CreateQueue;
    Vertex V,W;
    Enqueue(Q,S);
    while(Q is not empty)
    {
        V=Dequeue(Q);
        for(each W adjacent to V)
        {
            if(T[V].Dist+Cvw<T[W].Dist)
            {
                T[W].Dist=T[V].Dist+Cvw;
                T[W].Path=V;
                if(W is not already in Q)
                {
                    Enqueue(Q,W);
                }
            }
        }
    }
    Dispose(Q);
}

How to determine whether a graph has a negative cycle?

  1. add an array called cnt, update cnt[W]=cnt[V]+1 during relaxation step
  2. If, at any point, there existscnt==NumVertex, it indicates the presence of a negative cycle. This is because in a graph without cycles, the maximum possible value for cnt would be NumVertex - 1.

DAG

AOE network

Example
scheduling a project

  • Dummy Node: A- - - ->B——>C
    B does not need to be done before A
    Both tasks A and B must be completed before task C can be started
  • EC time(earlist time): EC[W]=max(EC[V]+Cvw)
  • LC time(latest time): LC[V]=min(LC[W]-Cvw)
    (V is predecessor of W)
  • Critical Path: the edges that have 0 slack time

Network Flow

Ford-Fulkerson Algorithm

  1. build a residual graph; initialize the residuals to the capacities
  2. while augmenting path can be found
    a. find an augmenting path on the residual graph
    b. find the bottleneck capacity x on the augmenting path
    c. update the residuals
    d. add a backward path(allow undo)

Time complexity: O(f*m)(f is the max flow, m is |E|)
Usually, we prefer to go through the large flow first(for later convenience)

Minimum Spanning Tree

Prim

The Difference between Prim and Dijkstra
the distance to be updated

  • Prim: just pick the lowest cost(the distance between target and visited set)
  • Dij: the distance from source to target

Kruskal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Kruscal(Graph G)
{
    T={};
    while(T contains less than |V|-1 edges && E is not empty)
    {
        choose a least cost edge (v,w) from E; // Deletemin
        delete(v,w) from E;
        if((v,w) does not create a cycle in T)
        {
            add(v,w) to T; // Union Find
        }
        else
        {
            discard(v,w);
        }
    }
    if(T contains fewer than |V|-1 edges)
    {
        Error("No Spanning Tree");
    }
}

DFS

DFS is a generation of preorder traversal

1
2
3
4
5
6
7
8
9
10
11
12
// T=O(|E|+|V|) as long as adjacency lists are used 
void DFS(Vertex V)
{
    visited[V]=true;
    for(each W adjacent to V)
    {
        if(!visited[W])
        {
            DFS(W);
        }
    }
}

Application1: list components

1
2
3
4
5
6
7
8
9
10
11
12
void ListComponents ( Graph G ) 
{   
    for ( each V in G )
    { 
        if (!visited[V])
        {
	        DFS(V);
            printf("\n");
        }
    }
}

Application2: Bioconnectivity

class ZJU
the main point is to find articulation point

  1. use dfs to grow a minimum spanning tree and add back edge
    some features of Num and this tree
    • no edge connecting 2 branches of the root
    • Num gets bigger when digging down deeper on the tree
  2. the case with root and other vertex is different, you can judge manually(see ppt dfs) or use Lownum to recursively solve it(list below)

Tarjan

  1. dfs to get Num array storing the dfs number
  2. recursively calculate Low 
    1
    2
    3
    4
    5
    Low(u)=min{
        Num(u),
        min{Low(w)|w is child of u},
        min{Num(w)|(u,w) is a back edge}
    }
  3. Therefore, u is an articulation point iff
    1. u is the root and has at least 2 children; or
    2. u is not the root, and has at least 1 child such that Low( child )  Num( u ).

Application3: Euler Circuits

  1. Euler tour:
    • Draw each line exactly once without lifting your pen from the paper
    • An Euler tour is possible if there are exactly two vertices having odd degree. One must start at one of the odd-degree vertices.
  2. Euler curcuit
    • Draw each line exactly once without lifting your pen from the paper, AND finish at the starting point
    • An Euler circuit is possible only if the graph is connected and each vertex has an even degree.