IsAcyclic uses depth-first search to find cycles in a generic graph represented by graph interface. If a cycle is found, it returns a list of nodes that are in the cyclic path, identified by their orders.
(g graph)
| 41 | // If a cycle is found, it returns a list of nodes that |
| 42 | // are in the cyclic path, identified by their orders. |
| 43 | func IsAcyclic(g graph) (bool, []int) { |
| 44 | // cycleStart is a node that introduces a cycle in |
| 45 | // the graph. Values in the range [1, g.order()) mean |
| 46 | // that there exists a cycle in g. |
| 47 | info := newCycleInfo(g.order()) |
| 48 | |
| 49 | for i := 0; i < g.order(); i++ { |
| 50 | info.Reset() |
| 51 | |
| 52 | cycle := isAcyclic(g, i, info, nil /* cycle path */) |
| 53 | if len(cycle) > 0 { |
| 54 | return false, cycle |
| 55 | } |
| 56 | } |
| 57 | |
| 58 | return true, nil |
| 59 | } |
| 60 | |
| 61 | // isAcyclic traverses the given graph starting from a specific node |
| 62 | // using depth-first search using recursion. If a cycle is detected, |