检测循环依赖？

Question

/*
问题：* 假设实际代码依赖链路： a.js -> b.js -> c.js -> d.js -> b.js

• 请实现一个方法，来检测循环依赖，并打印出闭环的依赖链（如上所示，循环依赖链）
• 下面给出了样例数据，注意方法要适用任意的数据输入
  */

let deps = {
  "a.js": {
    deps: ["b.js", "e.js"],
  },
  "b.js": {
    deps: ["c.js"],
  },
  "c.js": {
    deps: ["d.js"]
  },
  "d.js": {
    deps: ["a.js"]
  }
}

function checkCyclicRequire(deps) {
  
}

Answer 1

在线演示

ts 代码如下:

let deps = {
  "a.js": {
    deps: ["b.js", "e.js"],
  },
  "b.js": {
    deps: ["c.js"],
  },
  "c.js": {
    deps: ["d.js"]
  },
  "d.js": {
    deps: ["a.js"]
  }
}
enum Flag {
  cyclic = "cyclic",
  noCyclic = "noCyclic"
}

function checkCyclicRequire(deps: Record<string, { deps: string[] }>) {
  return Object.entries(deps).map(([jsPath]) => {
    return checkCyclic(jsPath, [], deps)
  }).flat(1).filter(([flag]) => flag === Flag.cyclic).map(([flag, ...path]) => path.join("->")).join('\n')

  function checkCyclic(jsPath: string, depsChains: string[], deps: Record<string, { deps: string[] }>): string[][] {
    if (depsChains.includes(jsPath)) {
      return [[Flag.cyclic, ...depsChains, jsPath]]
    } else if (jsPath in deps) {
      return deps[jsPath].deps.map(path => checkCyclic(path, [...depsChains, jsPath], deps)).flat(1)
    } else {
      return [[Flag.noCyclic, ...depsChains, jsPath]]
    }
  }
}
console.log(checkCyclicRequire(deps))

输出如下：

a.js->b.js->c.js->d.js->a.js
b.js->c.js->d.js->a.js->b.js
c.js->d.js->a.js->b.js->c.js
d.js->a.js->b.js->c.js->d.js

最后：这个问题似乎是一个作业？如果是的话希望你不要再这样提问了而应该自己去学习

Answer 2

经典的有向图环检测问题，思路：用dfs遍历整个图如果存在环则会存在有一条路径会回到已经访问过的节点

class Digraph {
  private _vertices: number
  private _edges: number
  private _adjacent: Set<number>[]

  constructor(vertices: number) {
    this._vertices = vertices
    this._edges = 0

    this._adjacent = []

    for (let vertex = 0; vertex < vertices; vertex++) {
      this._adjacent[vertex] = new Set()
    }
  }

  public vertices(): number {
    return this._vertices
  }

  public edges(): number {
    return this._edges
  }

  public addEdge(vertex1: number, vertex2: number): void {
    this._adjacent[vertex1].add(vertex2)
    this._edges++
  }

  public getAdjacencyList(): Set<number>[] {
    return this._adjacent
  }

  public adjacent(vertex: number): Set<number> {
    return this._adjacent[vertex]
  }
}

class DirectedCycle {
  private visited: boolean[]
  private edgeTo: number[]
  private _cycle: Array<number> | null = null // vertices on  a cycle (if one exists)
  private onStack: boolean[] // vertices on recursive call stack

  constructor(digraph: Digraph) {
    this.onStack = []
    this.edgeTo = []
    this.visited = []

    for (let vertex = 0; vertex < digraph.vertices(); vertex++) {
      if (!this.visited[vertex]) {
        this.dfs(digraph, vertex)
      }
    }
  }

  private dfs(digraph: Digraph, vertex: number): void {
    this.onStack[vertex] = true
    this.visited[vertex] = true

    for (const neighbor of digraph.adjacent(vertex)) {
      if (this.hasCycle()) {
        return
      } else if (!this.visited[neighbor]) {
        this.edgeTo[neighbor] = vertex
        this.dfs(digraph, neighbor)
      } else if (this.onStack[neighbor]) {
        this._cycle = []

        for (
          let currentVertex = vertex;
          currentVertex != neighbor;
          currentVertex = this.edgeTo[currentVertex]
        ) {
          this._cycle.push(currentVertex)
        }

        this._cycle.push(neighbor)
        this._cycle.push(vertex)
      }
    }

    this.onStack[vertex] = false
  }

  public hasCycle(): boolean {
    return this._cycle != null
  }

  public cycle(): Array<number> | null {
    return this._cycle
  }
}

type Dependencies = Record<
  string,
  {
    deps: string[]
  }
>

let deps = {
  'a.js': {
    deps: ['b.js', 'e.js'],
  },
  'b.js': {
    deps: ['c.js'],
  },
  'c.js': {
    deps: ['d.js'],
  },
  'd.js': {
    deps: ['a.js'],
  },
}

const buildGraph = (
  deps: Dependencies
): [Digraph, Map<string, number>, Map<number, string>] => {
  let id = 0
  const depNameToIdMap: Map<string, number> = new Map()
  const allDeps = new Set<string>()
  const idToDepNameMap: Map<number, string> = new Map()

  for (const name of Object.keys(deps)) {
    allDeps.add(name)
    for (const subDep of deps[name].deps) {
      allDeps.add(subDep)
    }
  }

  const graph = new Digraph(allDeps.size)
  for (const name of allDeps) {
    idToDepNameMap.set(id, name)
    depNameToIdMap.set(name, id++)
  }

  for (const name of Object.keys(deps)) {
    for (const subDep of deps[name].deps) {
      graph.addEdge(depNameToIdMap.get(name)!, depNameToIdMap.get(subDep)!)
    }
  }

  return [graph, depNameToIdMap, idToDepNameMap]
}

const [graph, depNameToIdMap, idToDepNameMap] = buildGraph(deps)
const detectCycle = new DirectedCycle(graph)

console.log(
  detectCycle
    .cycle()
    ?.map((v) => idToDepNameMap.get(v))
    .reverse()
    .join('-->')
)