Python中假设有向图采用邻接表表示,设计一个算法判断有向图中是否存在回路的代码和主程序
时间: 2024-02-26 18:57:28 浏览: 110
可以使用深度优先遍历(DFS)来判断有向图中是否存在回路。具体的实现步骤如下:
1. 创建一个visited数组,记录每个节点是否已经被访问过。
2. 从每个未被访问过的节点开始进行DFS遍历。
3. 在DFS遍历过程中,对于每个节点,将visited数组中对应位置标记为True,并遍历它的所有邻居节点。
4. 如果在遍历邻居节点时,发现某个邻居节点已经被访问过(visited为True),则说明存在回路,直接返回True。
5. 如果遍历完所有邻居节点都没有发现回路,则将该节点标记为已经访问过,并返回False。
下面是Python的代码实现:
```python
def has_cycle(node, graph, visited):
visited[node] = True
for neighbor in graph[node]:
if visited[neighbor]:
return True
elif has_cycle(neighbor, graph, visited):
return True
visited[node] = False
return False
def has_cycle_in_graph(graph):
visited = [False] * len(graph)
for node in range(len(graph)):
if not visited[node]:
if has_cycle(node, graph, visited):
return True
return False
```
其中,参数graph是邻接表表示的有向图,visited是一个长度为节点数的数组,用来记录每个节点是否已经被访问过。函数has_cycle用来判断从某个节点开始是否存在回路,如果存在回路则返回True,否则返回False。函数has_cycle_in_graph则遍历每个未被访问过的节点,如果存在回路则返回True,否则返回False。
下面是一个使用示例:
```python
graph = {
0: [1],
1: [2],
2: [3],
3: [1],
4: [3],
}
has_cycle_in_graph(graph) # True
```
这个例子中,节点1、2、3形成了一个回路,因此该有向图存在回路。
阅读全文