• 学习伪代码（这点不是硬性要求，可以直接用 Golang 实现）
  • 基本定义和相关概念
  • 数据结构的逻辑实现（邻接矩阵实现，邻接表实现）
  • 数据结构和算法的代码实现（这里使用 Golang BFS + DFS）
  • 用邻接表建立一个表，并用深度优先算法和广度优先算法来遍历途中的每个节点

Concept

图的相关基本概念来自于维基百科，从离散数学的角度解释了这些概念。图有多种变体，包括简单图、多重图、有向图、无向图等，但大体上有以下两种定义方式。

一张图 Graph - 图1 是一个二元组 Graph - 图2Graph - 图3，其中 Graph - 图4Graph - 图5称为顶点集，Graph - 图6 称为边集。它们亦可写成 Graph - 图7Graph - 图8和 Graph - 图9。Graph - 图10Graph - 图11的元素是一个二元组数对，用 Graph - 图12Graph - 图13表示，其中 Graph - 图14。

Reference

Data Structure

选择用邻接表来实现

  1. type link struct {
  2.     serial int
  3.     weight int
  4.     next   *link
  5. }
  7. // Graph -
  8. type Graph []*link

Build

  1. // Build -
  2. func Build() Graph {
  3.     var (
  4.         g    Graph
  5.         n, e int
  6.         p, q int
  7.     )
  9.     fmt.Scanf("%d%d", &n, &e)
  11.     for i := 0; i < n; i++ {
  12.         g = append(g, &link{
  13.             serial: i,
  14.             weight: defaultWeight,
  15.             next:   nil,
  16.         })
  17.     }
  19.     for i := 0; i < e; i++ {
  20.         fmt.Scanf("%d%d", &p, &q)
  22.         node := &link{
  23.             serial: q,
  24.             weight: defaultWeight,
  25.             next:   g[p].next,
  26.         }
  27.         g[p].next = node
  28.     }
  30.     return g
  31. }

这个函数只建立了单向的连接，如果是一个无向图，应该怎样修改程序。

BFS

  1. // Visited -
  2. var Visited = make([]int, 100)
  4. // DFS -
  5. func DFS(g *Graph, v int) {
  6.     fmt.Printf("[%d]", v)
  8.     Visited[v] = 1
  9.     p := (*g)[v].next
  11.     for p != nil {
  12.         if Visited[p.serial] == 0 {
  13.             DFS(g, p.serial)
  14.         }
  15.         p = p.next
  16.     }
  17. }

DFS

  1. // BFS -
  2. // Use Queue to store the sequences
  3. func BFS(g *Graph, v int) {
  4.     fmt.Printf("[%d]", v)
  6.     var (
  7.         f, r int
  8.         Q    = make([]int, 100)
  9.     )
  11.     Visited[v] = 1
  12.     p := (*g)[v].next
  14.     for (p != nil) || (f != r) {
  15.         for p != nil {
  16.             if Visited[p.serial] == 0 {
  17.                 r++
  18.                 Q[r] = p.serial
  20.                 fmt.Printf("[%d]", p.serial)
  21.                 Visited[p.serial] = 1
  22.             }
  23.             p = p.next
  24.         }
  26.         if f != r {
  27.             f++
  28.             v = Q[f]
  29.             p = (*g)[v].next
  30.         }
  31.     }
  32. }

如果图是一个连通的图，上面的算法没有问题，考虑非连通图图的情况，应该如何修改程序。提示：如果有孤立的子图，则不会被遍历到，得想个办法找到他们，然后从一个节点开始遍历。