面试官：判断图是否有环

• 
  
• 面试官让我写一个判断图是否有环，我没写出来，心想又是“面试造火箭，入职拧螺丝”。我把面试官pass了。没想到开发中真的遇到了判断有向图是否有环。
  
• 图是一种常见的数据结构，分为有向图和无向图。图是由边和节点组成的。
  
• 在前端开发中，接触到图的场景不算多。常见的有流程、图形可视化等场景。
  
• 我们在配置题目流程时遇到了需要判断图是否有环的需求。
  

背景

• 
  
• 简单介绍需求，通过可视化流程配置答题流程，题目与题目之间用线连接，箭头的方向代表下一个题目。回答完当前题目，根据不同的条件，跳到下一题；如果题目流程中有循环，会导致答题流程无法结束，所以需要校验题目的流程中不能有循环。
  
• 下面的是有循环，不符合条件
  

• 
  
• 下面的是无循环，符合条件
  

技术方案

• 
  
• 根据需求，我们把题目的流程配置抽象成有向图，题目是节点，题目之间的连线是边。
  
• 需求里的有无循环，最终可以转换成图是否有环的问题。从图的某个节点作为起点，根据边的方向出发跳到下一个节点，最终是否回到起点。如果回到起点，就是有循环、有环，否则是无循环、无环。
  
• 去除题目和各种条件等无关的结构，数据结构如下。
  

//边
export interface Edge {
id: string;
source: {
cell: string;   //这条边的起点的id

        [x: string]: any;

    };
target: {
cell: string;   //这条边的终点的id

        [x: string]: any;

    };
data: {
type: 'EDGE',

        [x: string]: any;

    }

    [x: string]: any;

};
//节点
export interface Node {
id: string;
data: {
type: 'NODE';
name: string;

        [x: string]: any;

    };

    [x: string]: any;

};
export type Data = Node | Edge;

• 
  
• 测试数据如下
  

const data: Data[] = [

    {
id: '1',
data: {
type: 'NODE',
name: '节点1'

        }

    },

    {
id: '2',
data: {
type: 'NODE',
name: '节点2'

        }

    },

    {
id: '3',
data: {
type: 'NODE',
name: '节点3'

        }

    },

    {
id: '4',
source: {
cell: '1'

        },
target: {
cell: '2'

        },
data: {
type: 'EDGE'

        }

    },

    {
id: '5',
source: {
cell: '1'

        },
target: {
cell: '3'

        },
data: {
type: 'EDGE'

        }

    }

];

• 
  
• 根据数据结构和测试数据data:Data[]，分为以下几个步骤：
  
  1. 
     
  2. 获得边的集合和节点的集合。
     
  3. 根据边的集合和节点的集合，获得每个节点的有向邻居节点的集合。即以每个节点的为起点，通过边连接的下一个节点的集合。例如测试数据节点1，通过边id4和边id5，可以连接节点2和节点3，所以节点1的邻居节点是节点2和节点3，而节点2和节点3无有向邻居节点。
     
  4. 最后根据有向邻居节点的集合，判断是否有环。
     
  
  
  

具体实现

• 
  
• 获得边的集合和节点的集合
  

const edges: Map<string, Edge> = new Map(), nodes: Map<string, Node> = new Map();
const idMapTargetNodes: Map<string, Node[]> = new Map();
const initGraph = () => {
for (const item of data) {
const { id } = item;
if (item.data.type === 'EDGE') {

            edges.set(id, item as Edge);

        } else {

            nodes.set(id, item as Node);

        }

    }

};

• 
  
• 获取有向邻居节点的集合，这里的集合，可以优化成id。我为了方便处理，存储了节点
  

const idMapTargetNodes: Map<string, Node[]> = new Map();
const initTargetNodes = () => {
for (const [id, edge] of edges) {
const { source, target } = edge;
const sourceId = source.cell, targetId = target.cell;
if (nodes.has(sourceId) && nodes.has(targetId)) {   //防止有空的边，即边的起点和终点不在节点的集合里
const targetNodes = idMapTargetNodes.get(sourceId);
if (Array.isArray(targetNodes)) {

                targetNodes.push(nodes.get(targetId) as Node);

            } else {

                idMapTargetNodes.set(sourceId, [nodes.get(targetId) as Node]);

            }

        }

    }

};

• 
  
• 最后判断是否有环，有两种方式：递归和循环。都是深度优先遍历。execute是遍历所有节点，hasCycle是把图的某个节点做为起点，判断是否有环。如果以所有节点为起点，都没有环，说明这个图没有环。
  
  1. 
     
  2. 递归。hasCycle判断当前节点是否有环；checked是做优化，防止某些节点多次检查，回溯阶段，把当前节点加入checked；visited记录当前执行的hasCycle里是否访问过，如果访问过，就是有环。需要注意的是，每次执行hasCycle时，visited用的是一个变量，所以在回溯阶段需要把当前节点从visited里删除。
     
  
  

  const checked: Set<string> = new Set();
  const hasCycle = (node: Node, visited: Set<Node>) => {
  if (checked.has(node.id)) return false;
  if (visited.has(node)) return true;
  
      visited.add(node);
  const { id } = node;
  const targetNodes = idMapTargetNodes.get(id);
  if (Array.isArray(targetNodes)) {
  for (const item of targetNodes) {
  if (hasCycle(item, visited)) return true;
  
          }
  
      }
  
      checked.add(node.id);
  
      visited.delete(node);
  return false;
  
  };
  const execute = () => {
  const visited: Set<Node> = new Set();
  for (const [id, node] of nodes) {
  if (hasCycle(node, visited)) return true;
  
          checked.add(id);
  
      }
  return false;
  
  };
  

  
  
  2. 
     
  3. 循环。checked和递归时，作用一样，这里不做说明。visited是用来判断当前的节点是否遍历过，如果遍历过，就是有环。用循环实现深度优先遍历时，需要用栈来存储当前链路上的节点，即当前节点已经后代节点。并且从栈里面获取最后一个节点，作为当前遍历的节点。如果当前节点有向邻居节点不为空，就把有向邻居节点的最后一个节点拿出来压栈；如果有向邻居节点为空，就把当前的节点出栈。在压栈时，如果当前节点在visited里，就说明有环，如果没有就要把这个节点加入到visited。在出栈时，把当前节点从visited里删除掉，因为如果不删掉，当一个节点的多个邻居节点最终指向同一个节点时，会判断为有环。
     
  
  

  const checked: Set<string> = new Set();
  const hasCycle = (node: Node) => {
  const { id } = node;
  if (checked.has(id)) return false;
  const stack = [id];
  const visited: Set<string> = new Set();
  
      visited.add(id);
  while (stack.length > 0) {
  const lastId = stack[stack.length - 1];
  const targetNodes = idMapTargetNodes.get(lastId) || [];
  if (targetNodes.length > 0) {
  const { id } = targetNodes.pop() as Node;
  if (visited.has(id)) return true;
  
              stack.push(id);
  
              visited.add(id);
  
          } else {
  
              stack.pop();
  
              visited.delete(lastId);
  
          }
  
      }
  return false;
  
  };
  const execute = () => {
  for (const [id, node] of nodes) {
  if (hasCycle(node)) return true;
  
          checked.add(id);
  
      }
  return false;
  
  };
  

  
  
  

总结

• 
  
• 要掌握常见的数据结构与算法，本例中用到了图、深度优先遍历。
  

源码

• 
  
• 递归
  
• 循环
  
• 原文