基于深度优先搜索,设计算法,判断一个无向图是否为一棵树 ,并给出完整代码
时间: 2023-08-22 12:05:17 浏览: 66
判断一个无向图是否为一棵树,可以通过检查是否存在环来实现。如果一个无向图没有环,那么它就是一棵树。
而深度优先搜索可以用来遍历整个图,并通过检查是否存在已经访问过的节点来判断是否存在环。
下面是基于深度优先搜索的算法,用于判断一个无向图是否为一棵树。
```python
from collections import defaultdict
class Graph:
def __init__(self, vertices):
self.graph = defaultdict(list)
self.V = vertices
def addEdge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
def isTree(self):
visited = [False] * self.V
# Check if there is a cycle in the graph
if self.isCyclic(0, visited, -1):
return False
# Check if all vertices are visited (i.e. connected graph)
for i in range(self.V):
if not visited[i]:
return False
return True
def isCyclic(self, v, visited, parent):
visited[v] = True
for i in self.graph[v]:
if not visited[i]:
if self.isCyclic(i, visited, v):
return True
elif i != parent:
return True
return False
# Example usage
g = Graph(5)
g.addEdge(1, 0)
g.addEdge(0, 2)
g.addEdge(2, 1)
g.addEdge(0, 3)
g.addEdge(3, 4)
if g.isTree():
print("Graph is a tree")
else:
print("Graph is not a tree")
```
这里使用了 `defaultdict` 来创建一个邻接表来存储图。`isCyclic()` 方法用来检查从节点 `v` 开始是否存在环,`isTree()` 方法则用来检查整个图是否是一棵树。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)