⑴ 建立无向图的邻接矩阵存储; ⑵ 对建立的无向图,进行深度优先遍历;
时间: 2023-12-03 14:07:37 浏览: 111
无向图邻接矩阵存储结构 先深及先广搜索
5星 · 资源好评率100%
⑴ 建立无向图的邻接矩阵存储:
无向图的邻接矩阵是一个 $n \times n$ 的矩阵,其中 $n$ 表示图中节点的数量,矩阵中的元素 $a_{i,j}$ 表示节点 $i$ 和节点 $j$ 之间是否有边相连,如果相连则为 1,否则为 0。由于是无向图,邻接矩阵是一个对称矩阵。
以下是通过 Python 代码实现无向图邻接矩阵的构建:
```python
# 无向图邻接矩阵的构建
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = [[0]*self.V for _ in range(self.V)]
def add_edge(self, u, v):
self.graph[u][v] = 1
self.graph[v][u] = 1
```
⑵ 对建立的无向图,进行深度优先遍历:
深度优先遍历(DFS)是一种图遍历算法,它先访问一个顶点,然后再依次访问该顶点的每个未访问过的邻居节点,直到所有的邻居节点都被访问过,才开始访问下一个未访问过的顶点。DFS 可以用递归或栈来实现。
以下是通过 Python 代码实现无向图的 DFS 遍历:
```python
# 无向图的深度优先遍历
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = [[0]*self.V for _ in range(self.V)]
def add_edge(self, u, v):
self.graph[u][v] = 1
self.graph[v][u] = 1
def DFS(self, v, visited):
visited[v] = True
print(v, end=' ')
for i in range(self.V):
if not visited[i] and self.graph[v][i]:
self.DFS(i, visited)
def DFS_traversal(self, start):
visited = [False] * self.V
self.DFS(start, visited)
```
在以上代码中,DFS_traversal() 方法用于启动 DFS 遍历,start 表示遍历的起点。visited 数组用于记录每个节点是否被访问过,初始时所有节点均未被访问。DFS() 方法用于实现递归遍历,visited 数组用于标记已访问的节点,遍历到一个节点时将其标记为已访问,并输出该节点的编号。然后依次访问该节点的每个未访问过的邻居节点。
阅读全文