# 检测循环依赖？

• 192

/*

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

}``````

##### 2个回答

``````class Digraph {
private _vertices: number
private _edges: number

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

for (let vertex = 0; vertex < vertices; vertex++) {
}
}

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

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

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

}

}
}

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)) {
for (const subDep of deps[name].deps) {
}
}

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) {
}
}

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('-->')
)
``````