LC 207

LC 210

### Detect Cycles in Directed Graph 1

Steps:

- Keep two lists
`visited`

and`completed`

same length of number of nodes and initialised to*false* - define a function(
`haveCycle`

) to solve for node:`visited[node]`

=*true*- for each children of node:
- if
`visited[children]`

, but not`completed[children]`

:**HAVE CYCLE**

- else:
- if children
`haveCycle`

:**HAVE CYCLE**

- if children

- if
`completed[node]`

=*true*

- for each
`node`

:- if not
`visited`

and`haveCycle(node)`

:**HAVE CYCLE**

- if not

### Detect Cycles in Directed Graph 2

Steps:

- Keep a lists
`indegree`

initialised to number of child point into that node. - Keep a
`queue`

to queue that contains the nodes that do not have child - while
`queue`

is not empty:`node`

=`queue.pop()`

- for each
`parent`

of`node`

:- detected dependency and we remove this dependency
`indegree[parent]`

-= 1 - if
`indegree[parent]`

is 0: there is no child anymore- push
`parent`

into`queue`

- push

- detected dependency and we remove this dependency

- if all
`indegree`

is not 0: there is still some dependencies**HAVE CYCLE**

How this works? If the node is not a leaf, we the dependencies of parent by reducing the number of dependencies of parent. If the parent have no more dependencies the parent become the leaf and we can do this continuously. If the parent still have dependencies and its child dependent on something its depend on the child will never be pushed into the list, because child was never resolved. Therefore parent will never be solved too (indegree more than 1).

### Flatten a tree with dependencies

Resolve the tree by solving the leaf first then the parent. This algorithm is the similar to the one above.

Steps:

- Keep two lists
`visited`

and`completed`

same length of number of nodes and initialised to*false* - A list of
`solution`

= []; - define a function
`solve`

to solve for`node`

:`visited[node]`

=*true*- for each
`children`

of`node`

:- if
`visited[children]`

, but not`completed[children]`

:**HAVE CYCLE**

- else:
- if children
`haveCycle`

:**HAVE CYCLE**

- if children

- if
`completed[node]`

=*true*- push
`node`

to`solution`

- for each
`node`

:- if not
`visited`

and`solve`

for`node`

:**HAVE CYCLE**

- if not
- print
`solution`

### Code

Method 1

```
def haveCycle(node, graph, visited, completed):
visited[node] = True
for out_node in graph[node]:
if not visited[out_node] and \
haveCycle(out_node, graph, visited, completed):
return True
else if not completed[out_node]:
return True
completed[node] = True
return False
numNodes = 3
graph = [
0: [1,2], # 0 to 1 and 0 to 2
1: [0],
2: [2]
]
visited = [False] * numNodes
completed = [False] * numNodes
for node in range(numNodes):
if not visited[node] and haveCycle(node, graph, visited, completed):
print('Cycle found')
```

Method 2

```
from collections import deque
numNodes = 3
graph = [
0: [1,2], # 0 to 1 and 0 to 2
1: [0],
2: [2]
]
indegree = [0] * numNodes
queue = deque()
for node in graph:
for out_node in graph[node]:
indegree[out_node] += 1
for node, indeg in enumerate(indegree):
if indeg == 0:
queue.append(node)
while queue:
node = queue.popleft()
for out_node in graph[node]:
indegree[out_node] -= 1
if indegree[out_node] == 0: # no more indegree all of them are solved
queue.append(out_node)
if sum(indegree) != 0:
print('Cycle found')
```