Topological sort

Description

Topological sort只可以用在DAG (directed acyclic graph)上面，而graph節點之間為partial order。可以適用於任務排程等工作。

Pseudo code

TOPOLOGICAL SORT(G)
1. call DFS(G) to compute finish times v.f for each vertex v
2. as each vertex is finished, insert it onto the fronend of a linked list
return the linked list of verticies

Time complexity

$\Theta$($V + E$)。

因為DFS走訪過所有的vertices和edges，然後linked list的長度為$V$。

Proofs

Lemma 1

Statement: A directed graph $G$ is acyclic if and only if a depth-first search of $G$ yields no back edges

Proof:

利用反證法可以證明此$lemma$，存在edge $(u, v)$是一個back edge，代表v是u的祖先(ancestor)，因此存在一個路徑$P$，使得$v$ -> $u$ ，但又已知存在一個back edge $(u, v)$行程迴圈，因此與假設矛盾，故不存在 back edge $(u, v)$。

反過來證明如果 $DFS$($G$)不產生back edge，則$G$ is acyclic。因為$G$不存在back edge，如果$u.finish$ > $v.finish$，則$u$ 必定在$v$ 之前被探訪，在$v$之後完成，因此不產生cycle。

Theorm 1

Statement: TOPOLOGICAL-SORT produces a topological sort of the directed acyclic graph provided as its input

Proof:

根據lemma 1，acyclic graph $G$不產生back edge，所以如果$v.finish$ > $u.finish$，代表$v$在 $u$之前被探訪，並在$u$之後完成探訪，因此它在linked list的位置在$u$之前，滿足topological sort的要求。

Golang implementation

topologicalsort.go

import "fmt"

type Vertex struct {
  finished    bool
}

type Graph struct {
  edges map[int][]int
  vertices []Vertex
}

func dfsUtil(g Graph, vIdx int, result []Vertex) []Vertex {
  edges := g.edges[vIdx]

  // visit all 
  for _, idx := range edges {
    if !g.vertices[idx].finished {
      result = dfsUtil(g, idx, result)
    }
  }

  g.vertices[vIdx].finished = True
  result = append([]Vertex{g.vertices[vIdx], result...})

  return result
}

func TopologicalSort(g Graph) []Vertex {
  result := []Vertex{}

  for i, v := range vertices {
    if !v.finished {
      result = dfsUtil(g, i, result)
    }
  }

  return result
}