首页 > 代码库 > 图的存储结构——前向星
图的存储结构——前向星
前向星也是一种通过存储边信息的方式存储图的数据结构。他的构造方式非常简单，读入每条边的信息，将边存放在数组当中，把数组中的按照起点顺序排序，前向星就构造完成了。为了查询方便，经常会有一个数组存储起点为vi的第一条边的位置。
所需的数据结构如下：
1 int head[maxn];2 3 struct NODE{4 int from;5 int to;6 int w;7 }; 8 NODE edge[maxm];
将所有边的信息读入，按照边的起点排序，如果起点相同，对于相同起点，如果仍有相同，按权值排序。在下面的样例中，使用C++ STL中的排序函数。
信息存储的主要代码如下。
比较函数：
1 inline bool cmp(NODE a , NODE b){2 if(a.from == b.from && a.to == b.to)3 return a.w < b.w;4 if(a.from == b.from) 5 return a.to < b.to;6 return a.from < b.from;7 }
读入数据：
1 inline int read(){ //读入优化 2 int x = 0, f = 1; 3 char ch = getchar(); 4 while(ch < ‘0‘ || ch > ‘9‘){ 5 if(ch == ‘-‘) f = -1; 6 ch = getchar(); 7 } 8 while(ch >= ‘0‘ && ch <= ‘9‘){ 9 x = x * 10 + ch - ‘0‘;10 ch = getchar();11 }12 return x * f;13 }14 int PutIn(){15 n = read();16 m = read();17 for(i = 0 ; i < m ; i ++){18 edge[i].from = read();19 edge[i].to = read();20 edge[i].w = read();21 }22 sort(edge, edge + m , cmp);23 memset(head , -1 , sizeof(head)); //排序 24 head[edge[0].from] = 0;25 for(i = 1 ; i < m ; i ++)26 if(edge[i].from != egde[i - 1].from) head[edge[i].from] = i;27 //确定起点为vi的第一条边的位置 28 }
?遍历代码
1 inline int Traversal(){2 for(i = 1 ; i <= n ; i ++){3 for(k = head[i] ; edge[k].from == i && k < m ; k ++){4 cout << edge[k].from <<‘ ‘<<edge[k].to <<‘ ‘<< edge[k].to << endl5 }6 }7 }
由于涉及排序，前向星的构造时间复杂度与排序算法有关，一般情况下时间复杂度为O(m log m)。空间上，需要两个数组， 所以空间复杂度为O(m + n)。前向星的优点在于可以应对点非常多的情况，可以存储重边，但是不能直接判断任意两个顶点（vi和vj）之间是否右边，而且排序需要浪费一些时间。
我敢说某人一定看不懂——（翻译）
图的存储结构——前向星
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。