无向图的创建邻接矩阵
时间: 2023-12-23 21:27:28 浏览: 50
创建无向图的邻接矩阵可以使用二维数组来表示。邻接矩阵是一个正方形矩阵,其中行和列分别代表图中的顶点,矩阵中的元素表示两个顶点之间是否存在边。如果两个顶点之间存在边,则对应位置的元素为1,否则为0。
下面是一个示例代码,演示了如何创建无向图的邻接矩阵:
```python
# 定义无向图的顶点数和边数
num_vertices = 4
num_edges = 5
# 创建一个空的邻接矩阵
adj_matrix = [[0] * num_vertices for _ in range(num_vertices)]
# 添加边到邻接矩阵
edges = [(0, 1), (0, 2), (1, 2), (2, 3), (3, 0)]
for edge in edges:
vertex1, vertex2 = edge
adj_matrix[vertex1][vertex2] = 1
adj_matrix[vertex2][vertex1] = 1
# 打印邻接矩阵
for row in adj_matrix:
print(row)
```
运行以上代码,将输出以下邻接矩阵:
```
[0, 1, 1, 0]
[1, 0, 1, 0]
[1, 1, 0, 1]
[0, 0, 1, 0]
```
这个邻接矩阵表示了一个有4个顶点和5条边的无向图。你可以根据需要修改顶点数和边数,并添加适当的边来创建不同的无向图。
相关问题
无向图创建邻接矩阵、广度优先遍历
无向图创建邻接矩阵的步骤如下:
1. 定义一个结构体来存储无向图的邻接矩阵,包括顶点表和邻接矩阵。
2. 在顶点表中存储每个顶点的信息。
3. 在邻接矩阵中,对于每个顶点,用0或1表示与其他顶点是否相邻,其中0表示不相邻,1表示相邻。
4. 根据需要,可以在结构体中添加顶点数和边数等信息。
下面是一个示例代码:
```c++
#define MVNum 100 //最大顶点数
//定义无向图邻接矩阵
struct AMGraph {
string vexs[MVNum]; //顶点表
int arcs[MVNum][MVNum]; //邻接矩阵
int vexnum, arcnum; //图的当前定点数和边数
};
//创建无向图邻接矩阵
void CreateUDN(AMGraph &G) {
cout << "请输入顶点数和边数:" << endl;
cin >> G.vexnum >> G.arcnum;
cout << "请输入顶点信息:" << endl;
for (int i = 0; i < G.vexnum; i++) {
cin >> G.vexs[i];
}
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
G.arcs[i][j] = 0;
}
}
cout << "请输入每条边的两个顶点:" << endl;
for (int k = 0; k < G.arcnum; k++) {
int i, j;
cin >> i >> j;
G.arcs[i][j] = 1;
G.arcs[j][i] = 1;
}
}
```
广度优先遍历是一种图的遍历算法,它从图的某个顶点开始,依次访问该顶点的所有邻接点,然后再依次访问这些邻接点的邻接点,直到遍历完整个图。广度优先遍历需要借助队列来实现。
下面是一个示例代码:
```c++
//广度优先遍历
void BFS(AMGraph G, int v) {
queue<int> Q;
bool visited[MVNum] = {false};
cout << G.vexs[v] << " ";
visited[v] = true;
Q.push(v);
while (!Q.empty()) {
int i = Q.front();
Q.pop();
for (int j = 0; j < G.vexnum; j++) {
if (G.arcs[i][j] == 1 && !visited[j]) {
cout << G.vexs[j] << " ";
visited[j] = true;
Q.push(j);
}
}
}
}
```
创建无向图的邻接矩阵
创建无向图的邻接矩阵可以通过使用二维数组来表示图中的节点之间的连接关系。邻接矩阵是一个正方形矩阵,其中行和列分别表示图中的节点,矩阵中的元素表示节点之间的连接关系。
下面是一个示例代码,演示了如何创建无向图的邻接矩阵:
```python
# 定义图的节点数量
num_nodes = 5
# 创建一个空的邻接矩阵
adj_matrix = [[0] * num_nodes for _ in range(num_nodes)]
# 添加边的连接关系
edges = [(0, 1), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (3, 4)]
for edge in edges:
node1, node2 = edge
# 在邻接矩阵中标记节点之间的连接关系
adj_matrix[node1][node2] = 1
adj_matrix[node2][node1] = 1
# 打印邻接矩阵
for row in adj_matrix:
print(row)
```
运行上述代码,将会输出以下邻接矩阵:
```
[0, 1, 0, 0, 1]
[1, 0, 1, 1, 1]
[0, 1, 0, 1, 0]
[0, 1, 1, 0, 1]
[1, 1, 0, 1, 0]
```
这个邻接矩阵表示了一个包含5个节点的无向图,其中1表示节点之间有连接,0表示节点之间没有连接。