c语言实现邻接矩阵
时间: 2023-07-13 21:12:36 浏览: 33
邻接矩阵是表示图的常用方法之一,C语言可以用二维数组来实现邻接矩阵。假设我们有一个无向图,有n个顶点,m条边,可以用以下代码实现邻接矩阵:
```c
#define MAXN 100 // 最大顶点数
int edge[MAXN][MAXN]; // 邻接矩阵
int n, m; // n为顶点数,m为边数
int main() {
scanf("%d%d", &n, &m);
memset(edge, 0, sizeof(edge)); // 初始化为0
for (int i = 1; i <= m; i++) {
int u, v; // u和v为一条边的两个端点
scanf("%d%d", &u, &v);
edge[u][v] = edge[v][u] = 1; // 标记有边相连
}
// 输出邻接矩阵
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
printf("%d ", edge[i][j]);
}
printf("\n");
}
return 0;
}
```
在输入时,我们先读入顶点数n和边数m。然后用memset函数将邻接矩阵全部初始化为0。接下来,我们读入每一条边的两个端点u和v,然后将edge[u][v]和edge[v][u]标记为1,表示u和v之间有边相连。最后,我们输出整个邻接矩阵。
相关问题
c语言实现邻接矩阵创建无向图
好的,下面是C语言实现邻接矩阵创建无向图的代码:
```c
#include <stdio.h>
#define MAX_VERTEX_NUM 20 // 最大顶点数
typedef struct {
int vertex[MAX_VERTEX_NUM]; // 顶点数组
int matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vertex_num; // 顶点数
int edge_num; // 边数
} Graph;
// 初始化图
void init_graph(Graph *graph, int vertex_num) {
graph->vertex_num = vertex_num;
graph->edge_num = 0;
// 初始化顶点数组
int i;
for (i = 0; i < vertex_num; i++) {
graph->vertex[i] = i + 1;
}
// 初始化邻接矩阵
int j;
for (i = 0; i < vertex_num; i++) {
for (j = 0; j < vertex_num; j++) {
graph->matrix[i][j] = 0;
}
}
}
// 添加边
void add_edge(Graph *graph, int start, int end) {
graph->matrix[start-1][end-1] = 1;
graph->matrix[end-1][start-1] = 1;
graph->edge_num++;
}
// 打印邻接矩阵
void print_matrix(Graph *graph) {
int i, j;
for (i = 0; i < graph->vertex_num; i++) {
for (j = 0; j < graph->vertex_num; j++) {
printf("%d ", graph->matrix[i][j]);
}
printf("\n");
}
}
int main() {
Graph graph;
init_graph(&graph, 5);
add_edge(&graph, 1, 2);
add_edge(&graph, 1, 4);
add_edge(&graph, 2, 3);
add_edge(&graph, 2, 4);
add_edge(&graph, 2, 5);
add_edge(&graph, 3, 5);
print_matrix(&graph);
return 0;
}
```
这个程序实现了一个邻接矩阵的无向图,可以通过调用 `init_graph` 初始化图, `add_edge` 添加边, `print_matrix` 打印邻接矩阵。
用c语言实现邻接矩阵深度优先遍历
邻接矩阵深度优先遍历是一种图遍历算法,它可以遍历一个图中所有的节点,并且保证不会重复遍历同一个节点。下面是一个用C语言实现邻接矩阵深度优先遍历的例子:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
int visited[MAX_VERTICES];
int adjacency_matrix[MAX_VERTICES][MAX_VERTICES];
int vertices_count;
void dfs(int vertex) {
int i;
printf("%d ", vertex);
visited[vertex] = 1;
for (i = 0; i < vertices_count; i++) {
if (adjacency_matrix[vertex][i] && !visited[i]) {
dfs(i);
}
}
}
int main() {
int i, j;
scanf("%d", &vertices_count);
for (i = 0; i < vertices_count; i++) {
visited[i] = 0;
for (j = 0; j < vertices_count; j++) {
adjacency_matrix[i][j] = 0;
}
}
for (i = 0; i < vertices_count; i++) {
for (j = 0; j < vertices_count; j++) {
scanf("%d", &adjacency_matrix[i][j]);
}
}
dfs(0);
return 0;
}
```
在这个程序中,我们首先定义了一个 `visited` 数组,用于记录每个节点是否被访问过。然后定义了一个邻接矩阵 `adjacency_matrix`,用于存储图的边信息。接着我们定义了一个 `dfs` 函数,用于进行深度优先遍历。最后在 `main` 函数中,我们读入了图的节点数量和邻接矩阵,然后调用 `dfs` 函数进行遍历。
在 `dfs` 函数中,我们首先输出当前节点的编号,并将其标记为已访问。然后遍历与该节点相邻的所有节点,如果该节点未被访问过,则递归调用 `dfs` 函数进行遍历。这样就可以完成邻接矩阵深度优先遍历了。