1.4 图搜索

1.4.1 概述

图数据结构非常强大，是目前应用最广泛的数据结构之一，几乎任何事物都可以用图进行建模表示，比如道路网络、计算机网络、社交网络、用户身份解析图。

事实上，计算机的文件系统和互联网本身都是以图为模型构建的。可以将互联网根据不同的应用场景表示为不同的图，比如，用户通过互联网连接彼此；用户在社交网络（例如微信）互相发送实时消息，互相关注对方并加为好友。

广度优先搜索（Breadth First Search，BFS）和深度优先搜索（Depth First Search，DFS）代表对图进行遍历（即搜索）的算法。程序化广告中用户身份图通过链接不同来源的数据来创建用户标识，广告商利用用户身份图进行目标受众定位并提供个性化广告。如果说用户身份图中的节点代表着某个用户，那么BFS和DFS算法可以用来识别节点之间的关系。

本节涉及许多图论算法，包括DFS在树与图结构搜索算法中的异同、无向图连通分量、最短路径、环检测、二分图检测、染色问题、拓扑排序等。

1.4.2 图建模中，邻接矩阵和邻接表哪种结构更好？

图存在两种表达方式——邻接矩阵与邻接表，它们用于记录图中任意两个节点之间的连通关系。邻接矩阵使用二维数组进行存储，而邻接表采用链表方式实现，具体来说图中每个节点都有一个独立链表，使用链表来存储当前节点关联的所有邻接节点以及权值。究竟怎么选择？下面分析两个场景。

假设一个图有3000个节点，有2999条边。图中节点的“度”是指与该节点相关联的边的数量。

场景1：存储空间分析。

● 使用邻接表需要3000 + 2999 = 5999 个数据节点来表达这个图。

● 使用邻接矩阵需要3000 × 3000 = 900万个数据节点来表达这个图。

结论：使用邻接矩阵占用的资源约为使用邻接表所占用的资源的1500倍。具体来说，如果原本邻接表只需要1KB的信息来存储图信息，那么对应的邻接矩阵则需要约1.5MB；如果本来邻接表需要使用1MB存储信息，那么对应的邻接矩阵则需要约1.5GB。

两种数据结构的存储空间差距是如此之大！1500倍的差距意味着，原本单机可以处理的场景，现在需要分布式处理。

场景2：求一个节点的相邻节点。

● 使用邻接表，此节点的“度”就说明需要遍历的时间复杂度。

● 使用邻接矩阵，不管当前节点的“度”是多少，我们都需要通过矩阵的对应行来遍历判断图中所有节点是否与当前节点相邻。其时间复杂度是O(V)。

接下来讨论稀疏图和稠密图的概念，边的多少是二者本质上的差异。如图1-73所示，稠密图是指边数接近于最大边数的图。如图1-74所示，稀疏图是一种边数接近于最小边数的图。

图1-73

图1-74

图1-75中，左图是稀疏图，尽管它的节点特别多，但是每个节点的度为5或6；右图是稠密图，尽管它的节点数看起来特别少，但是每个节点都与其他所有节点相连并形成了边，最终使得整个图的边数非常多。

图1-75

假设一个图有3000个节点，使用邻接表来存储。下面分析两个场景。

场景1：稀疏图

对于这3000个节点，如果每个节点的度都是3，则意味着有(3000×3)/2=4500条边。

场景2：稠密图

对于这3000个节点，如果每个节点的度都是2999，则意味着有(3000×2999)/2≈450万条边。

结论很明显：对于同样拥有3000个节点的稀疏图和稠密图，如果节点的度分别是3和2999，则二者存储的边的比例相差约1000倍。如果应用场景是一个稀疏图，采用邻接矩阵存储的成本以及时间复杂度都比邻接表要高。

图1-76所示为北京城市轨道交通线网图，看似特别复杂，但是图中每个节点（地铁站）都只与其附近的2～3个节点相连接，也就是说城市轨道交通线网图中节点的“度”并不大，其本质还是一个稀疏图，用邻接表来建模足够了。

图1-76

对生活中的问题进行建模得到的大多是稀疏图，因此建议使用邻接表数据结构来存储数据。

1.4.3 DFS在图搜索和树搜索中的应用

为了方便理解本小节内容，先想象一棵向下生长的树，树根在上，叶子在下。

树的深度优先搜索（又称Tree-DFS）意味着遍历从树根开始，在某个方向上尽可能地深入搜索，直到遇到叶子节点，然后回溯到上一层次，进入另一个方向深入搜索。Tree-DFS遍历的主要方向是垂直的。

与之相对，树的广度优先搜索（又称Tree-BFS）意味着遍历从树根开始，然后访问根节点的所有子节点，接着访问孙子节点，以此类推。对于每个深度，搜索所有的兄弟节点。

图结构中可能存在环，因此图的深度优先搜索（又称Graph-DFS）中遍历到一个节点时，需要查看这个节点是否已经被遍历过。为了确定每一个节点是否被遍历过，需要为每个节点创建一个visited[]标记。当遍历一个节点后，需要标记当前节点为已访问状态。

Tree-DFS使用递归遍历中的前序遍历。算法流程分为两步：第一步是遍历当前节点；第二步是递归遍历并访问所有的子树。

代码清单1-15 Tree-DFS的算法实现

type TreeNode struct {
    value string
    left  *TreeNode
    right *TreeNode
}
　
func insert(n *TreeNode, v string) *TreeNode {
    if n == nil {
        return &TreeNode{v, nil, nil}
    } else if v <= n.value {
        n.left = insert(n.left, v)
    } else {
        n.right = insert(n.right, v)
    }
    return n
}
　
func preorder(n *TreeNode) {
    if n != nil {
        fmt.Printf(n.value + " ")  //遍历 
        preorder(n.left)           //访问子树
        preorder(n.right)          //访问子树
    }
}

Graph-DFS与Tree-DFS在逻辑结构上是完全一致的。对于图数据结构来说，没有3-Node这样的节点类型，而是通常使用一个数字序号来表达一个节点，其中每一个节点与其他节点的相邻关系可以用邻接表或者邻接矩阵来存储。

代码清单1-16 Graph-DFS的算法实现

type Graph struct {
   adj map[string][]string
}
　
func (g *Graph) DFS(start string) {
   visited := g.createVisited()
   g.dfs(start, visited)
}
　
func (g *Graph) dfs(start string, visited map[string]bool) {
   visited[start] = true
   fmt.Println("DFS", start)               //遍历 
   for _, node := range g.adj[start] {
      if !visited[node] {
         g.dfs(node, visited)              //访问子树
      }
   }
}

对于树结构和图结构的深度优先搜索，通过抽象它们的底层逻辑，发现二者的本质是相同的。对比树的深度优先搜索和图的深度优先搜索逻辑如下。

● 第一步：对于树来说是遍历当前节点；对于图来说是从某个节点V开始进行遍历。

● 第二步：对于树来说是遍历所有子树，先遍历左子树，然后遍历右子树，由于树中每个节点至多只有左子节点和右子节点，所以只需要递归遍历左右子树就完成了递归遍历所有子树；对于图来说也是遍历所有子节点，但与当前节点V相邻的节点可能不止两个，而是多个。因此，需要通过for循环和邻接表来找出与当前节点V相邻的所有图节点。需要注意的是，递归遍历相邻节点前需要判断相邻节点是否已被访问过，即visited[V]。

❏ 在树中进行深度优先搜索，不需要判断当前节点是否被访问过。树中没有环，一个节点只可能被遍历访问一次，没有第二次被访问的机会。

❏ 图数据结构中可能存在环，一个节点可能会从多个遍历路径被访问，需要引入visited[]数组来保证图递归遍历过程中每个节点有且只有一次机会被访问。所以，在递归函数访问某个节点时，需要将当前正在访问的图节点V对应的visited[V]进行置位操作，即visited[V]=true。这样在后续的递归调用中，如果再次遇到节点V，就不会遍历节点V。

树中通过if node != nil来判断递归遍历终止条件；图的深度优先搜索从表面上看没有终止条件，实际上隐含在代码中。那么，图的递归遍历终止条件是什么呢？有两种情况。

● 当前节点V没有相邻的节点。

● 当前节点V的相邻节点都已经被访问过了。

这两种情况下都不需要继续递归下去，当前层递归可以返回到上一层递归。换句话说，上面两层逻辑都已经定义在for循环与if(visited[V])的判断逻辑当中。比如，若当前节点V没有相邻节点，此时for循环根本不会执行；若当前节点V的所有相邻节点已经被访问过，此时进入for循环后无法通过if(visited[V])的逻辑判断。因此，在这两种情况下都不会触发DFS递归遍历。

实际上，树的深度优先搜索与图的深度优先搜索的底层逻辑框架是相通的。图1-77给出了对此情况的概述。

图1-77

1．图的深度优先搜索的时间复杂度

在图的深度优先搜索过程中，每个节点以及每条边都会被访问一次，所以时间复杂度是O(v + e)，其中v表示节点数，e表示边数。如果考察的图是连通图，时间复杂度可以写成O(e)。如果图中所有节点之间不相连，时间复杂度可以写成O(v)。

2．图的深度优先搜索的应用场景

深度优先搜索在图搜索中的典型应用场景举例如下：

● 检测一张图是否整体连通，即求解图的连通分量；

● 二分图的检测；

● 寻找图中的桥与割点；

● 哈密顿路径；

● 拓扑排序。

1.4.4 DFS无向图连通分量问题

很多场景下我们会对无向图的连通分量感兴趣，比如在一个城市公路图模型中，每个节点代表一个城市，每条边代表城市之间的道路。求解公路系统图的连通分量，相当于求解公路系统中有多少独立的区域。我们可以据此计算最多可以关闭多少道路或者十字路口，但仍保持其他的街道网络是紧密连通的。

类似地，图1-78表示一个社交网络，其中每个节点代表每个人，节点之间相通的边代表这两个人是相识的，那么求解社交网络图的连通分量，相当于求解社交网络中有多少个独立的团体。

假如从节点A开始遍历，只会对与节点A直接或间接相邻的所有节点进行遍历，与此同时会把这些节点在对应的visited[]数组中标记为true。

图1-78

一旦节点A退出了当前的深度优先搜索递归调用，可以通过for循环继续寻找下一个没有被访问的节点，此节点肯定是另一个连通分量的一部分，对应图1-78中就是节点H。代码中for循环会找到节点H并继续进行深度优先搜索调用，此时找到了一个新的连通分量，将connectedComCnt变量进行自增操作。

代码清单1-17 图结构连通分量判断算法

type Graph struct {
    adj             map[string][]string
    results         []string
    connectedComCnt int
}
　
func NewGraph() Graph {
    return Graph{
        adj:             make(map[string][]string),
        results:         make([]string, 0),
        connectedComCnt: 0,
    }
}
　
func (g *Graph) DFS() {
    visited := g.newVisited()
　
    for key := range g.adj {
        if visited[key] == false {
            g.dfs(key, visited)
            g.connectedComCnt++
        }
    }
    fmt.Println("connected component count:", g.connectedComCnt)
　
}
　
func (g *Graph) dfs(start string, visited map[string]bool) {
    visited[start] = true
    fmt.Println("DFS", start)
    g.results = append(g.results, start)
    for _, node := range g.adj[start] {
        if !visited[node] {
            g.dfs(node, visited)
        }
    }
}

如果想进一步求解每个连通分量具体包含哪些节点，应该怎么做？有两个思路：思路一是向深度优先搜索递归函数中引入List[i]容器，将一组连通分量中的所有节点全部放入这个List[i]容器中；思路二是将boolean[] visited 重构成 int[] visited。

● 连通分量中的节点被遍历后，visited[]数组会从全为0变成全为1。

● visited[]数组的元素类型是布尔类型，所以它只能传递一个信息，即visited[i]代表节点i是否已经被访问过。如果我们换一个思路，将boolean visited[]数组扩展成 int visited[]，则可以让 visited[]数组承载更多的信息。

代码清单1-18 visited[]数组元素为布尔类型

func (g *Graph) newVisited() map[string]bool {
   visited := make(map[string]bool, len(g.adj))
   for key := range g.adj {
      visited[key] = false
   }
   return visited
}

我们将visited[]定义成整型，将数组中每个元素的值初始化为−1。在遍历 过程中会将visited[]设置成非负值。非负值有很多可以选择，不同的非负值代表不同的连通分量。

● for V := 0; V < len(v); V++ { dfs(v) }

● 第一次遍历dfs(0)的时候，将所有与节点0相连通的节点对应的visited[]统一赋值为0，表示所有值为0的visited[]节点属于同一个连通分量，可以将0看成连通分量的ID。

● 之后，for循环继续，它会找到未访问的节点H，从节点H出发再次按照深度优先搜索算法来递归遍历图，将所有与节点H相连通的节点对应的visited[]值设置为1。

● 利用visited[]数组，既完成了图的深度优先搜索过程中节点是否被访问过的逻辑判断，也实现了对图中属于不同连通分量的节点集的划分。visited[]中不同的值用来说明不同节点分别所属的连通图ID，如下所示。

connected component count: 2
connected components: map [A:0  B:0  C:0  D:0  E:0  F:0  G:0  H:1  I:1  J:1]

代码清单1-19 求解图结构的连通分量

func (g *Graph) DFS() {
    visited := g.newVisited()
　
    for key := range g.adj {
        if visited[key] == -1 {
            g.dfs(key, g.connectedComCnt, visited)
            g.connectedComCnt++
        }
    }
    fmt.Println("connected component count:", g.connectedComCnt)
    fmt.Println("connected components:", visited)
　
}
　
func (g *Graph) dfs(start string, ccID int, visited map[string]int) {
    visited[start] = ccID
    fmt.Println("DFS", start)
    g.results = append(g.results, start)
    for _, node := range g.adj[start] {
        if visited[node] == -1 {
            g.dfs(node, ccID, visited)
        }
    }
}
　
func (g *Graph) newVisited() map[string]int {
    visited := make(map[string]int, len(g.adj))
    for key := range g.adj {
        visited[key] = -1
    }
    return visited
}

1.4.5 DFS单源路径问题

单源路径问题求解的是从一个节点到另一个节点之间是否存在路径。图论问题中解决问题的一个基本思路是，在图的深度优先搜索过程中，可以辅助地记录一些信息来帮助我们完成对问题的求解。以图1-79为例。

图1-79

模拟单源路径算法的过程如下。

● 从节点A开始深度优先遍历它的相邻节点。先找到邻接点B。

● 遍历到节点B的时候，因为节点B是从节点A走来的，所以记录下B<-A这个信息。

● 继续从节点B开始进行深度优先遍历，找到它有A、D、E这3个相邻节点，因为节点A已经遍历过了，所以选择节点D。

● 遍历到节点D的时候，因为节点D是从节点B走来的，所以记录下D<-B这个信息。

● 继续从节点D开始进行深度优先遍历，找到它有B、C这两个相邻节点。因为节点B已经遍历过了，所以选择节点C。

● 遍历到节点C的时候，因为节点C是从节点D走来的，所以记录下C<-D这个信息。

● 继续从节点C开始进行深度优先遍历，找到它有A、G这两个相邻节点。因为节点A已经遍历过了，所以选择节点G。

● 遍历到节点G的时候，因为节点G是从节点C走来的，所以记录下G<-C这个信息。

● 继续从节点D开始进行深度优先遍历，找到它有C、F这两个相邻节点。因为节点C已经遍历过了，所以选择节点F。

● 遍历到节点F的时候，因为节点F是从节点G走来的，所以记录下F<-G这个信息。

● 继续从节点F开始进行深度优先遍历，所有相邻节点已经标记为访问，所以返回到上一层节点G。

● 继续从节点G开始进行深度优先遍历，所有相邻节点已经标记为访问，所以返回到上一层节点C。

● 继续从节点C开始进行深度优先遍历，所有相邻节点已经标记为访问，所以返回到上一层节点D。

● 继续从节点D开始进行深度优先遍历，所有相邻节点已经标记为访问，所以返回到上一层节点B。

● 继续从节点B开始进行深度优先遍历，找到它有A、D、E这3个相邻节点。因为节点A和D已经遍历过了，所以选择节点E。

● 遍历到节点E的时候，因为节点E是从节点B走来的，所以记录下E<-B这个信息。

● 继续从节点E开始进行深度优先遍历，所有相邻节点已经标记为访问，所以返回到上一层节点B。

● 继续从节点B开始进行深度优先遍历，所有相邻节点已经标记为访问，所以返回到上一层节点A。

● 继续从节点A开始进行深度优先遍历，所有相邻节点已经标记为访问，所以当前的连通分量遍历完毕，得到如下信息。

       B <- A
       D <- B
       C <- D
       G <- C
       F <- G
E <- B

● 当前连通分量的每个节点我们都记录下来了。使用previous[]数组记录当前节点是从哪一个节点走来的。接下来，如果想找到节点A到节点G的路径，可以从目标节点通过previous[]数组进行反向推导，一直找到源节点。具体步骤如下。

❏ 查询previous[]数组，询问节点G是从哪儿来的？得到previous[G] =C。

❏ 查询previous[]数组，询问节点C是从哪儿来的？得到previous[C] =D。

❏ 查询previous[]数组，询问节点D是从哪儿来的？得到previous[D] =B。

❏ 查询previous[]数组，询问节点B是从哪儿来的？得到previous[B] =A，其中，A即我们查询的源节点。

● 因此，找到一条从节点A到节点G的路径，即A -> B -> D -> C -> G。

结论：求解路径问题还是使用图的深度优先搜索算法作为框架，只是在做深度优先搜索的同时引入了previous[]数组来记录一些信息，以帮助我们完成对路径问题的求解。

新的问题：如何求解节点E到节点B的路径？

● 上面的方法是无法求解节点E到节点B的路径的，因为目前previous[]记录的所有信息都是从节点A出发进行深度优先搜索过程中记录并存储的信息。

● 比如，我们使用目前记录的信息查找从节点E到节点B经历的路径。

❏ 查询previous []数组，询问节点E是从哪来儿的？得到previous [E] = B。

❏ 查询previous []数组，询问节点B是从哪来儿的？得到previous [B] = A。

❏ 查询previous []数组，询问节点A是从哪儿来的？得到previous [A]的值是什么？然而previous [A]是没有值的，原因在于深度优先搜索算法的初始节点是A。

● 结论：我们无法基于现有的previous []数组信息找到从节点E到节点B是否存在路径。

● 如果希望求解出从节点E到节点B是否存在路径，那么整个深度优先搜索算法需要从节点E开始重新执行，并在执行过程中记录新的previous []数组信息。

当前算法可以求解从某个节点出发到图中剩余任意节点的路径问题，但是起始节点是固定的，因此该算法被命名为“单源路径算法”。

代码清单1-20 深度优先搜索的单源路径算法

func (g *Graph) SingleSourcePathDFS(src, dst string) {
    visited := g.newVisited()
    g.previous = make(map[string]string)
    isConnected := g.dfs(src, dst, src, visited)
　
    results := make([]string, 0)
    if isConnected {
        results = append(results, dst)
        parent := g.previous[dst]
        for parent != src {
            results = append(results, parent)
            parent = g.previous[parent]
        }
        results = append(results, src)
        fmt.Println("Paths from %s to %s node:", src, dst, reverse(results))
    }
}
　
func (g *Graph) dfs(start, dst, parent string, visited map[string]bool) bool {
    visited[start] = true
    g.previous[start] = parent
　
    if start == dst {
        return true
    }
　
    for _, ver := range g.adj[start] {
        if !visited[ver] {
            if g.dfs(ver, dst, start, visited) {
                return true
            }
        }
    }
　
    return false
}
　
func (g *Graph) newVisited() map[string]bool {
    visited := make(map[string]bool, len(g.adj))
    for key := range g.adj {
        visited[key] = false
    }
    return visited
}
　
func reverse(slice []string) []string {
    reverseResults := make([]string, 0)
    for i := len(slice) - 1; i >= 0; i-- {
        reverseResults = append(reverseResults, slice[i])
    }
　
    return reverseResults
}

自然地，所有点的路径问题都可以在单源路径问题的基础上解决，也就是对图中每个节点都执行一次单源路径算法。

1.4.6 BFS单源（最短）路径问题

同样是解决单源路径问题，广度优先搜索算法使用队列，只要队列不为空，while循环就不停。取出队列中的第一个元素，即节点V，然后找到所有与节点V相邻的节点，并将其压入队列。使用一个for循环来遍历所有与节点V相邻的节点。

确认相邻节点W是否已经访问过，即判断visited[W]= =false？如果没有，可以将其压入队列。visited[]数组确保一个节点只会被访问一次，即入队一次、出队一次。这样可避免重复入队、重复访问同一个节点。

代码清单1-21 广度优先搜索的单源（最短）路径算法

func (g *Graph) SingleSourcePathBFS(src, dst string) {
   isConnected := g.BFS(src, dst)
   if isConnected {
      g.outputSingleSourcePath(src, dst)
   }
}
　
func (g *Graph) BFS(src, dst string) bool {
   visited := g.newVisited()
   g.previous = make(map[string]string)
　
   visited[src] = true
   g.previous[src] = src
   var q []string
   q = append(q, src)
   for len(q) > 0 {
      var current string
      current, q = q[0], q[1:]
      g.results = append(g.results, current)
      for _, adj := range g.adj[current] {
         if !visited[adj] {
            q = append(q, adj)
            visited[adj] = true
            g.previous[adj] = current
            if adj == dst {
               return true
            }
         }
      }
   }
　
   return false
}

对于广度优先搜索的单源（最短）路径算法的总结如下。

● 在广度优先搜索的代码框架上做一点修改，就可以解决广度优先搜索的单源路径问题。

● 首先，对于每个连通分量的起始点，它的previous[]值对应它自己，即previous[src]=src。

● 其次，对节点V的所有相邻节点进行广度优先搜索，如果相邻节点W没有被访问过，即visited[W]=false，则将节点W压入队列。与此同时，说明V-W构成了一条边，节点W的上一个节点是V，即previous [W]=V。

下面介绍广度优先搜索与深度优先搜索的区别与联系。

如图1-80所示，对于同一个图，想要找到从节点A到节点G的路径，深度优先搜索算法的过程是A -> B -> D -> C -> G，广度优先搜索算法的过程是A -> C -> G ，故广度优先搜索算法实现的是最短路径，这是广度优先搜索的性质。

图1-80

为了理解这个性质，可以简单回顾一下树的广度优先搜索算法，如图1-81所示。

● 从根节点A开始使用广度优先搜索算法进行遍历。

● 找到节点B和节点C，它们与根节点的距离是1。

● 继续遍历节点B和节点C，找到D、E、F、G这4个节点，它们与根节点的距离是2。

图1-81

树的广度优先搜索算法被称为层序遍历，本质是按照与根节点距离的远近来遍历的，先遍历与根节点距离小的节点，后遍历与根节点距离大的节点，依此类推。换句话说，在树的广度优先搜索算法中，后遍历的节点到根节点的距离一定大于或者等于先遍历的节点到根节点的距离。

同理，图的广度优先搜索算法也是按照与起始点A距离的远近来遍历的，即后遍历的节点肯定比先遍历的节点与根节点之间的距离大或者二者相等。最后，广度优先搜索能保证找到从开始到目标节点的最短路径，而深度优先搜索却不能。

1.4.7 DFS检测无向图中的环

检测无向图中是否有环，整体思路与单源路径问题非常相似，二者的区别在于：单源路径问题是检索从一个节点到另一个节点是否有路径；而检测无向图中是否有环是检索从一个节点到该节点本身是否有路径。单源路径问题中的起始节点与终止节点是不同的，而无向图中是否有环问题中的起始节点与终止节点是相同的。

在图1-82中寻找从节点A起始的图中是否有环的思想如下。

图1-82

● 从节点A开始深度优先遍历它的相邻节点。先找到相邻节点B。

● 遍历到节点B的时候，找到它有A、D、E这3个相邻节点。由于节点A是节点B的上一个节点，尽管节点B可以回到节点A，但并不是一个环。

● 遍历到节点D的时候，找到它有B、C这两个相邻节点。由于节点B已经访问过，因此节点B不是要寻找的终止节点。

● 遍历到节点C的时候，找到它有A、G这两个相邻节点。由于节点A已经访问过，同时也是我们寻找的终止点，说明从节点C可以回到节点A，并且当前来到节点C的上一个节点为D而非A。因此，深度优先搜索找到了一个环。

上面例子中，整个过程是从节点A开始的，最后遍历的终止节点也是A。但也有可能从一个节点开始到最后发现一个环，环的终止节点与搜索的起始节点并不相同。例如在图1-83中，发现环的过程为A -> B -> D -> E -> B，其中起始节点是A，终止节点是B。

检测无向图中的环的算法思想是，遍历所有节点，若在遍历过程中找到了一个已经被访问的节点，并且这个节点并不是当前节点的上一个节点，说明此时找到了一个环。

图1-83

代码清单1-22 检测无向图中的环的算法

func (g *Graph) cycleDetection() bool {
   visited := g.newVisited()
   for key := range g.adj {
      if !visited[key] {
         if g.dfsCycleDetection(key, key, visited) {
            fmt.Println("Detected Cycle")
            return true
         }
      }
   }
　
   fmt.Println("No Cycle")
   return false
}
　
func (g *Graph) dfsCycleDetection(src, parent string, visited map[string]bool) bool {
   visited[src] = true
　
   for _, ver := range g.adj[src] {
      if !visited[ver] {
         if g.dfsCycleDetection(ver, src, visited) {
            return true
         }
         // Leon Bug
         //else if ver != parent {
         // return true
         //}
      } else if ver != parent {
         return true
      }
   }
　
   return false
}

DFS(V, parent)接收两个参数，一个是当前正在遍历的节点V；另一个是节点parent，它表示当前遍历节点的上一个节点。

对节点V的所有相邻节点进行深度优先遍历，即for(int W : g.adj(V))，有如下逻辑判断：

● 如果相邻节点W没有被访问过，即visited[W]=false，则会进一步触发深度优先搜索算法；

● 如果满足W!= parent，则表示当前相邻节点W已经被访问过，并且它不是当前节点V的上一个节点parent，此时说明找到了一个环。

1.4.8 二分图检测与染色算法

如果一个图中所有边的两个端点都属于不同的部分，则将这个图称为二分图。二分图的节点可以分成不相交的两个部分，如图1-84所示。图1-84中左、右图是完全等价的，左图比较容易判断出是二分图，但右图就比较难判断它的二分图性质。二分图有巨大的应用，比如选课系统，左边节点代表学生，右边节点代表课程。染色算法是典型的二分图建模算法。

图1-84

二分图检测是基于深度优先搜索的算法，但是在深度优先搜索的过程中需要进行染色的操作，即在遍历图的过程中，为每个节点指定一个颜色。比如将黑色与红色两种颜色分别赋给图中每个节点。最后看能不能实现每条边的两端节点颜色是不同的，即如果边的一个端点是红色的，那么边的另一个端点就必须是黑色的。

图1-85

以图1-85为例，深度优先搜索中的染色过程如下。

● 访问起始节点A并将其染成红色，找到相邻节点B、C。访问节点B。

● 访问节点B并将其染成黑色（与上一个节点A颜色不同）。找到相邻节点A、D、E。节点A已经标记为访问，故访问节点D。

● 访问节点D并将其染成红色（与上一个节点B颜色不同）。找到相邻节点B、C。节点B已经标记为访问，故访问节点C。

● 访问节点C并将其染成黑色（与上一个节点D颜色不同）。找到相邻节点A、D、G。节点A和D已经标记为访问，并且节点A和D与节点C的颜色不相同，故访问节点G。

● 访问节点G并将其染成红色（与上一个节点C颜色不同）。找到相邻节点C、F。节点C已经标记为访问，故访问节点F。

● 访问节点F并将其染成黑色（与上一个节点G颜色不同）。节点F已经标记为访问，且没有其他相邻节点可以遍历，故返回上一层节点G。

● 继续从节点G开始按照深度优先搜索算法来递归遍历，所有相邻节点已经被标记为访问，所以返回上一层节点C。

● 继续从节点C开始按照深度优先搜索算法来递归遍历，所有相邻节点已经被标记为访问，所以返回上一层节点D。

● 继续从节点D开始按照深度优先搜索算法来递归遍历，所有相邻节点已经被标记为访问，所以返回上一层节点B。

● 继续从节点B开始按照深度优先搜索算法来递归遍历，找到相邻节点A、D、E。节点A和D已经被标记为访问，故访问节点E。

● 访问节点E并将其染成红色（与上一个节点B颜色不同）。所有相邻节点已经被标记为访问，所以返回上一层节点B。

● 继续从节点B开始按照深度优先搜索算法来递归遍历，所有相邻节点已经被标记为访问，所以返回上一层节点A。

● 继续从节点A开始按照深度优先搜索算法来递归遍历，所有相邻节点已经被标记为访问，并已经到达递归的第一层，DFS函数完成染色过程。

整个染色过程中，需要依次将图中每个节点染成红色或者黑色。声明一个整型数组colors[]，数组大小等于图中的节点数目，数组中存储每个节点的颜色。

DFS函数接受两个参数，一个是当前节点V，另一个是节点V对应的colors[]值。DFS函数的逻辑如下。

● 首先对当前节点V的访问标志与colors[]标志进行赋值。

● 然后对当前节点V的所有邻接点进行遍历。

❏ 如果相邻点W没有被访问过，即visited[W]=false，此时需要触发深度优先搜索递归调用，并且需要对节点W进行染色。节点W的colors[]值当然应该与节点V的colors[]值不同，所以记为1-color，即DFS(W, 1-color)。

❏ 如果相邻节点W已经被访问过，就说明节点W已经被染色了，需要判断节点W的颜色与上一个节点V的颜色是否相同，即colors[W]是否等于colors[V]。如果相同，说明V-W这条边的两个节点的颜色是相同的，违反了二分图的定义，进而说明当前遍历的图不是二分图。

代码清单1-23 二分图检测算法

func (g *Graph) binaryParDetection() {
   colors := g.newColor()
   visited := g.newVisited()
   for key := range g.adj {
      if !visited[key] {
         if !g.dfsBinaryParDetection(key, 0, visited, colors) {
            fmt.Println("No Binary Partition Detection:")
         }
      }
   }
　
   fmt.Println("Binary Partition Detection:", colors)
}
　
func (g *Graph) dfsBinaryParDetection(src string, color int, visited map[string]bool, colors map[string]int) bool {
   visited[src] = true
   colors[src] = color
   for _, ver := range g.adj[src] {
      if !visited[ver] {
         if !g.dfsBinaryParDetection(ver, 1-color, visited, colors) {
            return false
         }
      } else if colors[ver] == colors[src] {
         return false
      }
   }
　
   return true
}

1.4.9 拓扑排序

拓扑排序是一个有向无环图的所有节点的线性序列，并且满足两个条件：

● 每个节点仅出现一次；

● 如果存在一条从节点A到节点B的路径，那么在拓扑序列中节点A出现在节点B的前面。

图1-86中，节点A指向节点B和C，因此拓扑排序中节点A出现在它们之前。同时，节点B和C都指向节点D，因此拓扑排序中节点B、C出现在节点D之前。以此类推，拓扑排序的最终结果为[A, B, C, D, E]。

图1-86

对于有环图而言，如图1-87所示，节点B指向节点D，同时节点D也间接指向节点B，这要求拓扑排序结果中节点B必须出现在节点D之前，同时节点B又出现在节点D之后，这是矛盾的。因此有环图没有拓扑排序。

图1-87

以图1-88为例来说明拓扑排序算法的流程。首先，需要找到一个入度为0的节点，此时发现节点A的入度为0，因此将节点A添加到拓扑排序的结果中。一旦将节点A加入了拓扑排序中，则将节点A及其出边进行虚拟删除，然后重新计算图中与节点A相邻的节点的入度。接下来，重复前面的步骤，查找任何入度为0的节点，并将其添加到拓扑排序结果中。

图1-88

算法步骤归纳如下。

● 查找入度为0的节点。

● 将该节点添加到拓扑排序结果中。

● 从图中删除以该节点起始的边，并重新计算与该节点相邻的节点的入度。

● 重复上述步骤。

拓扑排序本质上是一个有向无环图，或者是一个依赖树。如果任何事件B要求在启动之前完成事件A，那么在排序中A将出现在B之前。拓扑排序在计算机中的应用非常广泛，比如用来构建相互依赖的系统、编译器系统、学校选课系统、Hadoop中的任务调度子系统等。当然，拓扑排序在生活中也有很多应用场景，比如安排家务事（洗完衣服之前不能出门）；为儿童制定疫苗接种时间表，使得某些疫苗接种必须在其他疫苗接种之前完成。

拓扑排序算法使用队列来记录当前入度为0的节点。遍历队列中入度为0的节点并将结果输出到拓扑排序结果中，同时更新该节点相邻的节点的入度（减一操作），如果更新后相邻节点的入度为0则需要将其放入队列。后续重复这个过程，不断从队列中取出入度为0的节点。

特别说明两点：第一点是拓扑排序的结果并不是唯一的；第二点是对于有向有环图，拓扑排序是无解的（换句话说，拓扑排序算法有一个附加的效果，用来检测有向图中是否有环）。

代码清单1-24 拓扑排序算法

package toposort
　
type Graph struct {
   vertexes []string
   indegree map[string]int
   edges    map[string][]string
}
　
func NewGraph(cap int) *Graph {
   return &Graph{
      vertexes: make([]string, 0, cap),
      indegree: make(map[string]int),
      edges:    make(map[string][]string),
   }
}
　
func (g *Graph) AddNode(nodeName string) bool {
   g.vertexes = append(g.vertexes, nodeName)
　
   if _, ok := g.edges[nodeName]; ok {
      return false
   }
　
   g.edges[nodeName] = make([]string, 0)
   g.indegree[nodeName] = 0
   return true
}
　
func (g *Graph) AddNodes(nodeNames ...string) bool {
   for _, name := range nodeNames {
      if ok := g.AddNode(name); !ok {
         return false
      }
   }
   return true
}
　
func (g *Graph) AddEdge(src, dst string) bool {
   _, ok := g.edges[src]
   if !ok {
      return false
   }
　
   // Leon Bug
   //adjEdges = append(adjEdges, dst)
   g.edges[src] = append(g.edges[src], dst)
   g.indegree[dst]++
   return true
}
　
func (g *Graph) RemoveEdge(src, dst string) bool {
   if _, ok := g.edges[src]; !ok {
      return false
   }
　
   g.edges[src] = remove(g.edges[src], dst)
   g.indegree[dst]--
   return true
}
　
func remove(s []string, r string) []string {
   for i, v := range s {
      if v == r {
         return append((s)[:i], (s)[i+1:]...)
      }
   }
   return nil
}
　
func (g *Graph) Toposort() ([]string, bool) {
   queue := make([]string, 0, len(g.vertexes))
   rets := make([]string, 0, len(g.vertexes))
　
   for _, vertex := range g.vertexes {
      if g.indegree[vertex] == 0 {
         queue = append(queue, vertex)
      }
   }
　
   for len(queue) > 0 {
      var curVertex string
      curVertex, queue = queue[0], queue[1:]
      rets = append(rets, curVertex)
　
      backup := make([]string, len(g.edges[curVertex]))
      copy(backup, g.edges[curVertex])
      for _, adjVertex := range backup {
         //Leon Bug: you cann't modify  g.edges[curVertex] inside RemoveEdge when iterating g.edges[curVertex]
         g.RemoveEdge(curVertex, adjVertex)
         if g.indegree[adjVertex] == 0 {
            queue = append(queue, adjVertex)
         }
      }
   }
　
   totalDegree := 0
   for _, degree := range g.indegree {
      totalDegree += degree
   }
　
   if totalDegree > 0 {
      return rets, false
   }
　
   return rets, true
}

1.4.10 动态规划和递归之间的关系

链表、树与图的算法大量涉及递归操作。如何递归地思考？基本思想是忘记技术细节，只考虑定义，特别是函数递归定义。举例来说，检查一个字符串是否是回文串。根据定义，如果一个字符串和它的逆串相同，那么称这个字符串为回文串，如abcba。

有两种方法来检查一个字符串是否为回文串：for循环迭代和递归。

在迭代算法中，只需维护两个指针——开始（begin）和结束（end）。如果开始和结束指针指向的两个字符相同，就可以继续将开始指针向后移动，而将结束指针向前移动，再次检查两个字符，直到开始指针与结束指针交叉。

在递归算法中，第一步判断原始字符串是否构成一个回文串，判断内容如下。

● 开始字符与结束字符相同。

● 字符串的其余部分是回文串？

第二步判断字符串其余部分是否构成一个回文串，判断内容如下。

● 开始字符与结束字符相同。

● 字符串的其余部分是回文串？

第三步判断字符串其余部分是否构成一个回文串，判断内容如下。

● 开始字符与结束字符相同。

● 字符串的其余部分是回文串？

继续递归调用，直到“字符串的其余部分”为空，递归函数回溯返回，确定当前字符串是一个回文串。

本质上，递归就是用同一个子问题来表达原始问题。一般来说，原始问题可以分成子问题，子问题进一步被分解成更小的子问题，最终，这个子问题变成了基本的简单问题，可以直接给出答案。通过递归函数可以一步步回溯到调用起点，比如，求解二叉树的节点数：

if tree is not empty
size(tree) = size(tree.left) + size(tree.right) + 1

记住，递归就是一个遍历，一种for循环迭代而已。它可以用来解决子问题，比如，遍历数组、链表、树和图结构。对于动态规划（Dynamic Programming，DP）来说，它有两种类型：自顶向下和自底向上。其中自顶向下的本质就是递归，但是增加了记忆查找表的功能。我们知道，DP问题中相同的子问题会重复出现，为了避免将来重复计算相同的子问题，只需要通过搜索记忆查找表直接返回值，即可提高算法效率。