读入数据,创建无向图的邻接矩阵
时间: 2023-08-02 08:09:27 浏览: 40
好的,邻接矩阵是一种表示图形的方法,它是一个二维数组,其中每个元素表示两个顶点之间是否存在边。如果存在边,则元素的值为1,否则为0。下面是一个简单的示例代码,用于读取图形数据并创建邻接矩阵:
```python
# 读取数据
n, m = map(int, input().split()) # n表示节点数,m表示边数
edges = [] # 存储边的列表
for i in range(m):
u, v = map(int, input().split()) # 读取一条边
edges.append((u, v))
# 创建邻接矩阵
adj_matrix = [[0] * n for i in range(n)] # 初始化邻接矩阵
for u, v in edges:
adj_matrix[u][v] = 1 # u到v有边
adj_matrix[v][u] = 1 # v到u也有边,因为是无向图
```
这段代码首先读取节点数和边数,然后读取每条边,并将它们存储在一个列表中。接下来,我们创建一个初始值为0的二维数组,表示没有边。最后,我们遍历边列表,将每条边的两个端点之间的邻接矩阵元素设置为1,表示它们之间有边。由于是无向图,因此我们还需要反向设置邻接矩阵元素,以便正确表示双向关系。
相关问题
无向图邻接矩阵深度优先遍历
好的,我可以为您解答这个问题。
无向图的邻接矩阵表示法可以用一个二维数组来表示,其中矩阵的行列数都等于图的顶点数,矩阵中的元素表示两个顶点之间是否有边相连,通常用 0 或 1 来表示。
深度优先遍历(Depth First Search,DFS)是一种常用的图遍历算法,主要思想是从某个顶点开始,沿着一条路径遍历直到不能继续为止,然后返回到前一级顶点,继续沿着另一条路径遍历,直到所有的顶点都被访问过。
无向图邻接矩阵深度优先遍历的步骤如下:
1. 访问起始顶点,并将其标记为已访问;
2. 从起始顶点出发,依次遍历它的邻接点;
3. 对于每个邻接点,如果它未被访问,则递归访问它,并将其标记为已访问;
4. 重复步骤 2 和步骤 3,直到所有顶点都被访问过。
具体实现可以参考以下代码:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 100;
int n; // 顶点数
int G[MAXN][MAXN]; // 邻接矩阵
bool visited[MAXN]; // 标记数组
void dfs(int v) {
visited[v] = true; // 标记当前顶点已访问
cout << v << " "; // 输出当前顶点
for (int i = 0; i < n; i++) {
if (G[v][i] && !visited[i]) { // 如果有边相连且未访问过
dfs(i); // 递归访问邻接点
}
}
}
int main() {
memset(G, 0, sizeof(G)); // 初始化邻接矩阵
memset(visited, false, sizeof(visited)); // 初始化标记数组
// 读入无向图的顶点数和边数
int m;
cin >> n >> m;
// 读入边的信息,建立邻接矩阵
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
G[u][v] = G[v][u] = 1; // 无向图的边是双向的
}
// 从顶点 0 开始深度优先遍历
dfs(0);
return 0;
}
```
以上代码实现了无向图邻接矩阵深度优先遍历,并输出了遍历结果。
c语言实现邻接矩阵创建无向图
可以使用二维数组来表示邻接矩阵,其中数组的每个元素表示一条边的权值。以下是创建无向图的示例代码:
```c
#include <stdio.h>
#define MAX_VERTICES 100
int graph[MAX_VERTICES][MAX_VERTICES];
int main() {
int num_vertices, num_edges;
printf("Enter the number of vertices: ");
scanf("%d", &num_vertices);
printf("Enter the number of edges: ");
scanf("%d", &num_edges);
// 初始化邻接矩阵
for (int i = 0; i < num_vertices; i++) {
for (int j = 0; j < num_vertices; j++) {
graph[i][j] = 0;
}
}
// 读入每条边的起点和终点,设置邻接矩阵中相应的位置为1
for (int i = 0; i < num_edges; i++) {
int u, v;
printf("Enter edge %d (u, v): ", i+1);
scanf("%d %d", &u, &v);
graph[u][v] = 1;
graph[v][u] = 1; // 因为是无向图,所以需要设置对称位置为1
}
// 打印邻接矩阵
printf("Adjacency matrix:\n");
for (int i = 0; i < num_vertices; i++) {
for (int j = 0; j < num_vertices; j++) {
printf("%d ", graph[i][j]);
}
printf("\n");
}
return 0;
}
```
在上述代码中,我们首先读入了图的顶点数和边数,然后初始化邻接矩阵,接着读入每条边的起点和终点,并将相应的位置设置为1,最后打印邻接矩阵。