wordpress伪静态结构,衡水seo培训,私人网站免费观看,discuz建网站链式前向新#xff1a;用于存储图的 边集 数组
前言
当我们存储图的时候#xff0c;往往会使用 邻接矩阵 或是 邻接表。
邻接矩阵 好写#xff0c;但太浪费空间#xff0c;节点一多就存不下#xff1b;
邻接表 效率高#xff0c;但涉及指 #xff0c;不好写容易出错…链式前向新用于存储图的 边集 数组
前言
当我们存储图的时候往往会使用 邻接矩阵 或是 邻接表。
邻接矩阵 好写但太浪费空间节点一多就存不下
邻接表 效率高但涉及指 不好写容易出错用 vector 又可能超时。
链式前向星 就是一个相对中庸的存储方式虽然说链式前向星 使用并不广泛但在需要使用复杂 邻接表 时这就是一个较好的选择。
链式前向星 其实就是 静态建立的邻接表时间复杂度为O(m)空间复杂度也为O(m)。 思想
对于下图
图1 输入为 5 7 1 2 3 2 3 1 1 3 4 1 5 3 4 1 5 4 5 1 3 4 2 我们将起点都是 from 的边串在一起用 head[from] 存储头节点见图2下图为最终形式 图2
具体插入操作与链表相似 见图3
图3 代码与运行结果
里有注释慢慢理解
#include iostream
#include cstringusing namespace std;const int N 2e2 5, M 1e3 5;int n, m, cnt; //n个点m条边
struct Edge {int to, value, next;//终点边权同起点的上一条边的编号
} edge[M]; //边集
int head[N]; //head[i] 表示以 i 为起点的第一条边在边集数组的位置编号void add_edge(int from, int to, int value) { //u起点v终点w边权edge[ cnt] {to, value, head[from]}, head[from] cnt;// 赋终点权值 并且将新的节点赋在头上 更新头
}int main() {cin n m;/* 初始化 */cnt 0;memset(head, -1, sizeof head);/* 加边 */for (int i 1; i m; i ) { //输入m条边int a, b, c;cin a b c;add_edge(a, b, c);}/* 遍历 */for (int i 1; i n; i ) {cout i \n;bool hase false;for (int j head[i]; j ! -1; j edge[j].next) //遍历以i为起点的边cout i edge[j].to edge[j].value \n, hase true;if (!hase)cout nothing\n; //第i个节点没有出去的边}return 0;
}
/*
5 7
1 2 3
2 3 1
1 3 4
1 5 3
4 1 5
4 5 1
3 4 2
*/
可以注意到 head 的初始值为 -1
这使得 head[i] 中第一个边的 next 为 -1这正作为链的结尾见图3
所以当 访问指针 ( j ) 为 -1 时就代表访问结束了 运行结果参考
图4
从 图2~4 和 代码中我们都可以发现 链式前向星 是按输入倒着存的 结语
个人觉得 链式前向星 和 邻接表 是几乎一样的只不过 前者 是静态的后者 是动态的
