邻接矩阵的构造
第一种存储结构- 邻接矩阵。需要注意的事， 我们接下来针对的是有向图。 今后如果遇到无向图的情况，将每条无向图看成有向图中的正反两条有向边即可。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N 500
typedef struct Graph {
int mat[MAX_N][MAX_N];
int n;
} Graph;
// 首先来实现结构体 Graph 的初始化函数init 吧。函数有两个参数，一个是Grap类型的指针变量g; 另一个是 int 类型的变量n, 表示图中顶点个数。
void init(Graph *g, int n) {
g->n = n;
// 接下来， 就要初始化 mat 二位数组，也就邻接矩阵g 中使用的矩阵，我们可以用memset 将 其中的元素 置为0.
memset(g->mat, 0, sizeof(g->mat));
}
int main() {
Graph *graph = (Graph *)malloc(sizeof(Graph));
init(graph, 100);
return 0;
}
邻接矩阵的使用
有向图中得到一条从x 连向y 的有向边，对应邻接矩阵第x 行 y 列元素的值为1。 我们现在不考虑有重复边的情况， 如果有多条边从 x 连到 y 的边， 我们就认为其中只有一条边是有意义的。
在插入之前， 我们需要先判断一下输入是否合法； 如果x 不在区间 【0， n】或者 y 不在区间【0，n】 内，则直接结束函数即可. 注意这里的 n 是指邻接矩阵的维度 n.
-
如果插入数据合法，我们在插入从x 连向 y 的边时 只需要将矩阵 第 x 行 y 列的值 设为 1 即可。
-
在实现 insert 函数之后， 我们就是实现 output 的具体逻辑了。
output 函数要实现的功能是将邻接矩阵的所有元素值遍历输出，每行n 个 元素， 一共你行。 首先 ，我们来实现最外层的循环。让循环变量i 从 0 循环到不小于 邻接矩阵 g 的 维度 n 时 退出， 记得加上一对大括号。 -
接下来要实现内存的循环了， 让循环变量 j 从 0 循环到不小于邻接矩阵 g 的维度 n 时退出，并且输出矩阵第i 行 j 列 的值。 每输出一个元素之后要输出一个空格。
-
邻接矩阵的输出还差最后一步，在每一行输出n 个元素之后 输出一个换行。
-
首先输入两个值n 和 m, 分别表示 图中顶点个数 和 图中 有向边的数量。之后输入m 条 有向边，每次读入两个变量 x 和 y, 表示插入一条 从 x 连向 y 的边。 注意 x 和 y 的 取值 范围时 0 到 n -1. m 条 边 输入完成后，程序会将邻接矩阵完成输出。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N 500
typedef struct Graph {
int mat[MAX_N][MAX_N];
int n;
} Graph;
void init(Graph *g, int n) {
g->n = n;
memset(g->mat, 0, sizeof(g->mat));
}
void insert(Graph *g, int x, int y) {
if(x < 0 || x >= g->n || y < 0 || y>= g->n ) {
return ;
}
g->mat[x][y] = 1;
}
void output(Graph *g) {
for(int i = 0; i < g->n; ++i) {
for(int j =0; j < g->n; ++j) {
printf("%d ", g->mat[i][j]);
}
printf("\n");
}
}
int main() {
int n, m, x, y;
scanf("%d %d", &n, &m);
Graph *graph = (Graph *)malloc(sizeof(Graph));
init(graph, n);
for (int i = 0; i < m; ++i) {
scanf("%d %d", &x, &y);
insert(graph, x, y);
}
output(graph);
free(graph);
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/76965.html
