建立一个有向图的邻接矩阵存储,然后在主函数中输出该二 维矩阵(注意输出格式要为一个矩阵),以检验存储的正确 性;再从0号顶点出发对该图进行深度优先搜索,按顺序输出 所访问的顶点。
时间: 2024-01-22 18:18:22 浏览: 138
好的,以下是代码实现:
```python
class Graph:
def __init__(self, vertices):
self.V = vertices
self.adj_matrix = [[0 for _ in range(self.V)] for _ in range(self.V)]
def add_edge(self, u, v):
self.adj_matrix[u][v] = 1
def DFS(self, start):
visited = [False] * self.V
stack = [start]
result = []
while stack:
node = stack.pop()
if not visited[node]:
visited[node] = True
result.append(node)
for i in range(self.V-1, -1, -1):
if self.adj_matrix[node][i] == 1 and not visited[i]:
stack.append(i)
return result
def print_matrix(self):
for i in range(self.V):
print(self.adj_matrix[i])
```
在主函数中,我们可以调用 Graph 类来构造有向图,并打印邻接矩阵:
```python
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)
g.add_edge(4, 3)
g.print_matrix()
```
输出结果为:
```
[0, 1, 1, 0, 0]
[0, 0, 1, 0, 0]
[1, 0, 0, 1, 0]
[0, 0, 0, 1, 0]
[0, 0, 0, 1, 0]
```
可以看到,邻接矩阵被正确地存储了。接下来,我们可以从 0 号顶点出发进行深度优先搜索,并输出访问的顶点:
```python
print(g.DFS(0))
```
输出结果为:
```
[0, 1, 2, 3, 4]
```
这表明从 0 号顶点出发,DFS 搜索访问了所有的顶点。
阅读全文