• Graph
  • start
  • BFS
  • DFS
    • depth-first forest
  • TopologicalSort
  • StrongConnectedComponents

Graph

Use golang to implement some interesting graph algorithms

start

go get github.com/letterbeezps/graph

BFS

func TestBFS(t *testing.T) {
  graphAdj := graph.NewGraphAdj[string, int]()

  e1 := graph.Edge[string, int]{
    U:         "r",
    V:         "v",
    W:         0,
    notDirect: true,
  }
  graphAdj.AddEdge(&e1)

  e2 := graph.Edge[string, int]{
    U:         "r",
    V:         "s",
    W:         0,
    notDirect: true,
  }
  graphAdj.AddEdge(&e2)
  ...
  visitFunc := func(u string) bool {
    fmt.Println("BFS-TEST: ", u)
    return true
  }

  ans := graphAdj.Bfs("s", visitFunc)
}

BFS-TEST:  s
BFS-TEST:  r
BFS-TEST:  w
BFS-TEST:  v
BFS-TEST:  t
BFS-TEST:  x
BFS-TEST:  u
BFS-TEST:  y
[s r w v t x u y]

DFS

Dfs not only returns the results of traversal, but also includes two important features, discovery time and completion time. We can use these two time points to draw the depth-first forest of this dfs

func TestDFS(t *testing.T) {
  graphAdj := graph.NewGraphAdj[string, int]()

  e3 := graph.Edge[string, int]{
    U:         "x",
    V:         "v",
    W:         0,
    notDirect: false,
  }
  graphAdj.AddEdge(&e3)
  ... ...
  ans := graphAdj.Dfs(nil)

  fmt.Println(ans)

  dfsForest := graphAdj.DepthFirstForest()
  fmt.Println(dfsForest)
}

[{v 3 4} {x 2 5} {y 1 6} {u 7 8} {z 10 11} {w 9 12}]

[[{x 1 6} {v 2 5} {y 3 4}] [{u 7 8}] [{w 9 12} {z 10 11}]]

depth-first forest

TopologicalSort

only DAG can call method TopologicalSort

func TestTopologicalSort(t *testing.T) {
  graphAdj := graph.NewGraphAdj[string, int]()

  e3 := graph.Edge[string, int]{
    U:         "shirt",
    V:         "tie",
    W:         0,
    notDirect: false,
  }
  graphAdj.AddEdge(&e3)
  ... ...

  graphAdj.AddVertex("watch")

  fmt.Println(graphAdj)

  ret := graphAdj.TopologicalSort()

  fmt.Println(ret)
}

[{panties 15 18} {pants 16 17} {shirt 7 14} {belt 12 13} {tie 8 11} {jacket 9 10} {watch 5 6} {socks 1 4} {shoe 2 3}]

StrongConnectedComponents

func TestStrongConnectedComponents(t *testing.T) {
  graphAdj := graph.NewGraphAdj[string, int]()

  e3 := graph.Edge[string, int]{
    U:         "a",
    V:         "b",
    W:         0,
    notDirect: false,
  }
  graphAdj.AddEdge(&e3)
  ... ... 
  ans := graphAdj.StrongConnectedComponents()

  fmt.Println(ans)
}

[[e b a] [c d] [g f] [h]]