构造无向图的邻接矩阵
时间: 2023-07-23 22:10:35 浏览: 41
构造无向图的邻接矩阵需要进行以下步骤:
1. 确定图中顶点的数量。
2. 创建一个 n x n 的矩阵,其中 n 为顶点的数量。
3. 对于每条边 (i, j),将矩阵中第 i 行第 j 列和第 j 行第 i 列的值都设为 1,表示顶点 i 和顶点 j 之间有一条边。
4. 对于没有边相连的顶点,矩阵中对应的位置为 0。
例如,假设有以下无向图:
```
+-- 2
|
1 -- + -- 3
|
+-- 4
```
该图有 4 个顶点,因此邻接矩阵为 4 x 4 的矩阵。对于每条边,我们将矩阵中对应的位置的值设为 1,没有边相连的顶点对应的位置设为 0,得到如下邻接矩阵:
```
1 2 3 4
1 0 1 0 0
2 1 0 1 0
3 0 1 0 1
4 0 0 1 0
```
其中第 i 行第 j 列和第 j 行第 i 列的值都为 1,表示顶点 i 和顶点 j 之间有一条边。
相关问题
创建无向图邻接矩阵算法
在C++中,可以使用邻接矩阵来表示无向图。邻接矩阵是一个二维数组,其中的元素表示图中两个顶点之间的边的存在与否。
下面是一个简单的示例代码,展示了如何创建一个无向图的邻接矩阵:
```cpp
#include <iostream>
#include <vector>
using namespace std;
class Graph {
private:
int numVertices; // 图中顶点的数量
vector<vector<int>> adjMatrix; // 邻接矩阵
public:
// 构造函数
Graph(int num) {
numVertices = num;
adjMatrix.resize(numVertices, vector<int>(numVertices, 0));
}
// 添加边
void addEdge(int src, int dest) {
adjMatrix[src][dest] = 1;
adjMatrix[dest][src] = 1;
}
// 打印邻接矩阵
void printMatrix() {
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
cout << adjMatrix[i][j] << " ";
}
cout << endl;
}
}
};
int main() {
// 创建一个包含5个顶点的无向图
Graph graph(5);
// 添加边
graph.addEdge(0, 1);
graph.addEdge(0, 4);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
// 打印邻接矩阵
graph.printMatrix();
return 0;
}
```
在上面的代码中,我们首先定义了一个`Graph`类,其中包含了私有成员变量`numVertices`表示图中顶点的数量,以及`adjMatrix`表示邻接矩阵。构造函数用于初始化邻接矩阵的大小。
然后,我们定义了`addEdge`函数用于添加边,这里我们使用1表示两个顶点之间存在边。注意,由于是无向图,所以我们需要同时在两个顶点之间设置边。
最后,我们定义了`printMatrix`函数用于打印邻接矩阵。
在`main`函数中,我们创建了一个包含5个顶点的无向图,并添加了一些边。然后,我们调用`printMatrix`函数打印邻接矩阵。
希望这个示例能够帮助你理解如何使用邻接矩阵来表示无向图。如果你有任何问题,请随时提问。
构造无向图的邻接矩阵c语言代码
以下是构造无向图邻接矩阵的 C 语言代码示例:
```c
#include <stdio.h>
#define MAX_VERTICES 100
int main() {
int num_vertices; // 顶点数量
int adj_matrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
int i, j;
// 输入顶点数量
printf("Enter the number of vertices: ");
scanf("%d", &num_vertices);
// 初始化邻接矩阵
for (i = 0; i < num_vertices; i++) {
for (j = 0; j < num_vertices; j++) {
adj_matrix[i][j] = 0; // 初始化为 0
}
}
// 输入边信息并更新邻接矩阵
int num_edges;
printf("Enter the number of edges: ");
scanf("%d", &num_edges);
for (i = 0; i < num_edges; i++) {
int u, v;
printf("Enter edge %d (u v): ", i + 1);
scanf("%d %d", &u, &v);
adj_matrix[u][v] = 1;
adj_matrix[v][u] = 1; // 无向图需更新对称位置
}
// 输出邻接矩阵
printf("Adjacency Matrix:\n");
for (i = 0; i < num_vertices; i++) {
for (j = 0; j < num_vertices; j++) {
printf("%d ", adj_matrix[i][j]);
}
printf("\n");
}
return 0;
}
```
该程序首先输入顶点数量和边数量,然后根据输入的边信息更新邻接矩阵,并最终输出邻接矩阵。