利用“邻接矩阵”存储无向图; 2.利用DFS(深度优先搜索算法)判断无向图中是否有圈概要设计
时间: 2023-12-26 15:04:06 浏览: 97
1. 邻接矩阵存储无向图
邻接矩阵是一种非常常见的图的存储方式,对于无向图,邻接矩阵是一个对称矩阵,其中第 i 行第 j 列的元素表示顶点 i 和 j 之间是否存在一条边,如果存在则为 1,否则为 0。
以下是无向图的邻接矩阵表示:
```
1 2 3 4
1 0 1 1 0
2 1 0 1 1
3 1 1 0 1
4 0 1 1 0
```
2. 利用DFS判断无向图中是否有环
DFS算法可以用来判断无向图中是否有环。具体实现如下:
1. 从任意一个顶点开始,标记为已访问。
2. 对于每个邻接点,如果邻接点已经被访问过,并且不是当前节点的父节点,则说明有环。
3. 如果邻接点没有被访问过,则标记为已访问,并将当前节点作为邻接点的父节点,递归遍历邻接点。
4. 如果所有邻接点都被访问过,并且没有发现环,则返回 false。
以下是无向图中是否有环的实现代码:
```python
def hasCycle(graph):
n = len(graph)
visited = [False] * n
parent = [-1] * n
def dfs(node):
visited[node] = True
for neighbor in range(n):
if graph[node][neighbor]:
if visited[neighbor] and parent[node] != neighbor:
return True
elif not visited[neighbor]:
parent[neighbor] = node
if dfs(neighbor):
return True
return False
for node in range(n):
if not visited[node]:
if dfs(node):
return True
return False
```
以上是判断无向图中是否有环的概要设计,具体实现可以根据需要进行修改和优化。
阅读全文