首页 > 代码库 > 图存储-前向星
图存储-前向星
//前向星是将所有的边进行编号,每个节点u的边集合通过head[u]来找到u的第一条边,
//再通过next[head[u]]依次遍历节点u的所有边。
int head[maxn]; int to[maxn*2];int next[maxn*2];int cnt = 0;//边的编号 memset(head, -1, sizeof(head)); inline void add(int x,int y){to[cnt]=y,next[cnt]=head[x],head[x]=cnt++;to[cnt]=x,next[cnt]=head[y],head[y]=cnt++;} inline void dfs(int u){ int i; //从节点u的第一条边开始,遍历与u相连的所有边 for(i=head[u];i!=-1;i=next[i]) { dfs(to[i]); }}/*head[i]: 以i为节点的边集的第一条边编号next[i]:编号为i的边集中的下一条边编号,特定节点u的边的编号连成一个链表to[i]:编号为i的边的终点*/
//另一种实现
#include <iostream>#include <cstdio>using namespace std;const int maxn = 100;const int maxm = 100000;typedef struct edgenode { int to; //边的终点 int next; //当前下一条边的编号 int w; //边的权值}edgenode;int head[maxn]; //head[i]存放已i为起点的第一条边edgenode edge[maxm];int edgenum = 1;int n = 0, m = 0;int init() { edgenum = 1; memset(head, 0, sizeof(head));//chu shi hua 0; return 0;}int outputmap(){ for (int i = 1; i <= n; i++) { for (int k = head[i]; k != 0; k = edge[k].next) { printf("(%d --- > %d) == %d\n", i, edge[k].to, edge[k].w); } } return 0;}int main() { init(); int a = 0, b = 0, c = 0; while (scanf("%d%d", &n, &m) == 2) { for (int i = 0; i < m; i++) { scanf("%d%d%d", &a, &b, &c); edge[edgenum].to = b; edge[edgenum].w = c; edge[edgenum].next = head[a]; head[a] = edgenum; edgenum++; edge[edgenum].to = a; edge[edgenum].w = c; edge[edgenum].next = head[b]; head[b] = edgenum; edgenum++; } outputmap(); init(); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。