在做图有关的题目,在一些情况下邻接矩阵耗费空间较大、动态开辟的邻接表又耗时耗内存,这时候你可能需要一个静态邻接表!
静态邻接表在各种图的算法当中也是有一席之地的,比如利用堆优化的Dij算法求最短路、SPFA等等
下面给出我的静态邻接表模板
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10; ///定义点集的数量
struct EDGE{ int v, nxt, w; }; /// v为边终点、nxt为同起点的下一条边、w为边权
int Head[maxn]; /// 邻接表表头
EDGE Edge[maxn*maxn]; /// 定义边集
int cnt; /// 每一条边的编号、记得初始化
int N, M; /// N个顶点、M条边
inline void init()
{
memset(Head, -1, sizeof(Head));
cnt = 0;
}
inline void ADD(int from, int to, int weight)/// 插入边
{
Edge[cnt].w=weight, Edge[cnt].v=to, Edge[cnt].nxt=Head[from], Head[from]=cnt++;
Edge[cnt].w=weight, Edge[cnt].v=from, Edge[cnt].nxt=Head[to], Head[to]=cnt++;/// 如果为无向图,需要建双向边
}
inline void Debug()/// 输出这个邻接表
{
for(int i=1; i<=N; i++){/// N代表顶点的编号、从1~N共N个定点,根据题意自己调整
printf("%d ", i);
for(int j=Head[i]; j!=-1; j=Edge[j].nxt){/// 用一条 for 循环就能找出所有定点 i 的出度
printf("-> %d ", Edge[j].v);
}puts("");
}puts("");
}
int main(void)
{
while(~scanf("%d %d", &N, &M)){
init();
for(int i=0; i<M; i++){
int from, to, weight;
scanf("%d %d %d", &from, &to, &weight);
ADD(from, to, weight);
}
Debug();
}
return 0;
}
原文链接: https://www.cnblogs.com/qwertiLH/p/7681124.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/261436
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!