建立任意无向图,采用邻接矩阵存储,完成以下操作:对该图进行深度优先遍历,并输出遍历结果;对该图进行广度优先遍历,并输出遍历结果。
时间: 2023-06-17 11:04:00 浏览: 187
好的,我可以给你提供一个Python的实现,首先定义一个Graph类来存储图,使用邻接矩阵表示:
```python
class Graph:
def __init__(self, vertices):
self.V = vertices
self.adj_matrix = [[0] * self.V for i in range(self.V)]
def add_edge(self, src, dest):
self.adj_matrix[src][dest] = 1
self.adj_matrix[dest][src] = 1
```
上面的代码中,我们定义了一个Graph类,并且使用邻接矩阵来存储图,其中V表示顶点数,adj_matrix是一个二维矩阵,用于存储边的关系。add_edge方法用于添加边,我们采用无向图,因此需要将两个方向都添加。
接下来我们可以使用深度优先遍历和广度优先遍历算法来遍历图。
深度优先遍历算法:
```python
def dfs_iterative(self, start):
visited = [False] * self.V
stack = []
stack.append(start)
while stack:
curr = stack.pop()
if not visited[curr]:
visited[curr] = True
print(curr, end=' ')
for i in range(self.V-1, -1, -1):
if self.adj_matrix[curr][i] == 1 and not visited[i]:
stack.append(i)
```
上面的代码中,我们使用栈来进行迭代式遍历,初始时将起始节点放入栈中,然后遍历栈中的节点,如果该节点没有被访问过,则标记为已访问,并输出。然后遍历该节点的邻居,将未访问的邻居放入栈中。
广度优先遍历算法:
```python
def bfs_iterative(self, start):
visited = [False] * self.V
queue = []
queue.append(start)
visited[start] = True
while queue:
curr = queue.pop(0)
print(curr, end=' ')
for i in range(self.V):
if self.adj_matrix[curr][i] == 1 and not visited[i]:
queue.append(i)
visited[i] = True
```
上面的代码中,我们使用队列进行迭代式遍历,初始时将起始节点放入队列中,并标记为已访问,然后遍历队列中的节点,输出该节点,并遍历该节点的邻居,将未访问的邻居放入队列中。
最后,我们可以创建一个Graph对象,添加节点和边,然后调用上面定义的深度优先遍历和广度优先遍历算法完成遍历:
```python
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
g.add_edge(3, 4)
print('DFS Traversal:')
g.dfs_iterative(0)
print('\nBFS Traversal:')
g.bfs_iterative(0)
```
完整代码如下:
阅读全文