以下无向图,请使用邻接矩阵表示出该图。 并使用程序验证。
时间: 2024-10-22 09:13:29 浏览: 25
假设我们有一个无向图,它由5个顶点A、B、C、D和E组成,并有如下边连接:
- A与B相连
- B与C相连
- C与D相连
- D与E相连
- E与A相连
我们可以用一个二维数组(邻接矩阵)来表示这个图,其中行代表起点,列表示终点,值为1表示两点之间有边,值为0表示没有边。以下是邻接矩阵的表示:
```
| | A | B | C | D | E |
|---|---|---|---|---|---|
| A | 0 | 1 | 0 | 0 | 0 |
| B | 1 | 0 | 1 | 0 | 0 |
| C | 0 | 1 | 0 | 1 | 0 |
| D | 0 | 0 | 1 | 0 | 1 |
| E | 0 | 0 | 0 | 1 | 0 |
```
为了验证这个邻接矩阵,我们可以编写一个简单的程序,例如用Python:
```python
def is_connected(graph, start, end):
visited = set()
stack = [start]
while stack:
vertex = stack.pop()
if vertex == end:
return True
visited.add(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
stack.append(neighbor)
return False
# 示例用法
graph = {
'A': ['B'],
'B': ['A', 'C'],
'C': ['B', 'D'],
'D': ['C', 'E'],
'E': ['D', 'A']
}
print(is_connected(graph, 'A', 'E')) # 输出:True
```
这个程序会检查从节点'A'到节点'E'是否可以通过连续的边到达。如果邻接矩阵表示正确,上述函数将返回True,表明图是连通的。
阅读全文