拓扑排序在检测成环与图连通中的应用

背景

在项目中遇到了一些关于图的问题，主要是是下面的两个问题。

1. 决策流中不能出现环，否则会出现死循环问题。

2. 不能存在游离节点，所有的图都是连通的。

简单的说就是用户配置的图，应该是符合有向无环的，并且子图之间是相互连通的。

什么是拓扑排序

拓扑排序(Topological Sorting)是一个有向无环图(DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

• 每个顶点出现且只出现一次。

• 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

有向无环图（DAG）才会有拓扑排序，非DAG图没有拓扑排序。

例如，下面这个图就是一个DAG图：

如何写出它的拓扑排序呢？这里说一种比较常用的方法：

1. 从图中选择一个没有前驱(即入度为0)的顶点输出。

2. 从图中删除该顶点和所有以它为起点的有向边。

3. 重复 1 和 2 直到当前的图为空或当前图中不存在无前驱的顶点为止。

通常，一个有向无环图可以有一个或多个拓扑排序序列。这是因为可能同时存在多个入度为0的结点，这时，先处理哪个都是可以的。

拓扑排序用来干什么？

• 判断是否有环

• 求DAG中的最长链

JS中实现拓扑排序思路

梳理上面的思路：

1. 每一个顶点都有入度和出度，入度为0说明没有指向他的，那么就从他开始往下找。

2. 把这个入度为0的push进队列（还要注意保存入度为0的点），同时把与这个点相连的所有点的入度 减1。

3. 然后再看看有没有入度为0的，有的话继续push，循环上面的操作，直到没有入度为0的点。

例如我要实现一个下面图的拓扑排序

根据上述算法步骤，设计存储节点的数据结构如下

interface NodeDepend {
  id: string 
  afters: Array<string>
  indegree: number
}

id: 节点ID

afters: 当前节点的后续节点

indegree: 节点入度

const topSort = (edges: Array<[string, string]>) => {
  const EdgeNode = (id: string ) => {
    return {
      id,
      afters: [],
      indegree: 0
    }
  }

  const nodes: { [key: string]: NodeDepend } = {},
    result = [],
    queue: string[] = []

  edges.forEach((edge) => {
    const fromEdge = edge[0]
    let fromNode: NodeDepend

    if (!(fromNode = nodes[fromEdge])) {
      fromNode = nodes[fromEdge] = EdgeNode(fromEdge)
    }

    edge.forEach((toEdge) => {
      if (toEdge == fromEdge) {
        // 无论是自己跟自己链，或者就是自己就都会返回
        return
      }

      const toEdgeStr = toEdge.toString()
      if (!nodes[toEdgeStr]) {
        nodes[toEdgeStr] = EdgeNode(toEdge)
      }
      nodes[toEdgeStr].indegree++
      fromNode.afters.push(toEdge)
    })
  })

  // topsort
  const keys = Object.keys(nodes)
  keys.forEach((key) => {
    if (nodes[key].indegree === 0) {
      queue.push(key)
    }
  })
  while (queue.length !== 0) {
    const vertex = queue.shift()
    if (!vertex) {
      break
    }
    result.push(nodes[vertex].id)
    nodes[vertex].afters.forEach((after) => {
      const afterStr = after.toString()
      nodes[afterStr].indegree--
      if (nodes[afterStr].indegree === 0) {
        queue.push(afterStr)
      }
    })
  }
  return { nodes, result }
}
// 判断DAG图是否有环（检查拓扑排序结束后的）
export const hasCricle = (edges: Array<[string, string]>) => {
  const { nodes } = topSort(edges)
  const keys = Object.keys(nodes)
  for (let i = 0; i < keys.length; i++) {
    if (nodes[keys[i]].indegree) { // 检查是否有入度不为0的节点，如果有，则存在环。
      return true
      break
    }
  }
  return false
}

// 判断是否有游离节点问题【不能有环，环节点可能不在】
export const hasDetached = (
  nodes: Array<string>,
  edges: Array<[string, string]>
) => {
  if (nodes.length == 1 && edges.length == 0) {
    return false
  }
  const { result } = topSort(edges)
  const diff = nodes.filter((v) => { // 判断拓扑排序最长链结果 和 实际节点的差集 来判断是否游离
    return result.indexOf(v) == -1
  })
  return Boolean(diff.length)
}

测试数据如下:

const edges = [
  ['two', 'three'],
  ['four', 'six'],
  ['one', 'three'],
  ['two', 'four'],
  ['six', 'nine'],
  ['five', 'seven'],
  ['five', 'eight'],
  ['five', 'nine'],
  ['seven', 'eight'],
  ['eight', 'nine'],
  ['one', 'two'],
  ['four', 'five'],
  ['four', 'six'],
  ['three', 'six'],
  ['six', 'seven'],
  ['three', 'four']
]