图论--链式前向星

短命女 2022-05-19 02:05 322阅读 0赞

我们存图的方式通常有邻接矩阵和前向星，邻接矩阵易造成空间浪费，前向星需要sort排序,复杂度是O（nlogn），所以效率不高，链式前向星是前向星的优化，它可以避免排序。

以下是边的存储结构

struct Node{
        int to;
        int w;
        int next;
    }edge[maxn];

edge\[i\].to表示的是第i条边的终点，edge\[i\].next表示的是与第i条边同起点的下一条边的存储位置，edge\[i\].w表示的是第i条边的权值

除此之外我们还需要一个head数组，它表示的是以i为起点的第一条边的存储位置，首先将head数组全部赋初值-1

下面是边的读入

void addEdge(int u,int v,int w)//每条边的起点,终点,权值
     {
        edge[cnt].to = v;
        edge[cnt].w = w;
        edge[cnt].next = head[u];//获取与它同起点的边的下一条位置
        head[u] = cnt++;//cnt的初值赋0
     }

head数组是以i为起点的第一条边的存储位置，这个以i为起点的第一条边随着cnt的增加而增加，其实这个第一条边是以该起点为边的最后一条边出现的位置，所以遍历每条边的时候其实是反向遍历的，假设我们要遍历以u为起点的所有边，当遍历到以u为起点的最后一条边的时候，因为head赋予的初值为-1，那么下一次i就等于-1了，循环就不再执行了

for(int i = head[u]; ~i; i = edge[i].next)

我们来模拟一遍，假设现在加入的边的顺序是(1,3) (2,4) (3,4) (1,2) (3,1) (1,5)

edge\[0\].to = 3；edge\[0\].next = head\[1\] = -1；head\[1\] = 0；

edge\[1\].to = 4；edge\[1\].next = head\[2\] = -1；head\[2\] = 1；

edge\[2\].to = 4；edge\[2\].next = head\[3\] = -1；head\[3\] = 2；

edge\[3\].to = 2；edge\[3\].next = head\[1\] = 0；head\[1\] = 3；

edge\[4\].to = 1；edge\[4\].next = head\[3\] = 2；head\[3\] = 4；

edge\[5\].to = 5；edge\[5\].next = head\[1\] = 3；head\[1\] = 5；

假设我们遍历的是以1为起点的所有边 i = head\[1\] = 5 ，就是(1,5)这条边，然后i = edge\[i\].next = 3,就是(1,2)这条边，最后i = edge\[i\].next = 0，即(1,3)这条边，i = edge\[0\].next=-1，然后循环结束。至此，以1为起点的所有边就被遍历完了

发表评论取消回复

表情：

评论列表（有 0 条评论，322人围观）

还没有评论，来说两句吧...

相关阅读

相关 ACM模板——链式前向星&&邻接表存图

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] 1 include<bits/stdc++.h>

雨点打透心脏的1/2处/ 2023年06月01日 08:47/ 0 赞/ 197 阅读

相关图论之图的存储邻接矩阵、邻接表和链式前向星

一、图的存储方式目前常用的图的存储方式有两种，邻接矩阵和邻接表存储。边数M相对小（远远小于n\（n-1））的图为稀疏图，反之为稠密图。稀疏图可用邻接表存储，稠密图

ゞ浴缸里的玫瑰/ 2023年02月15日 10:25/ 0 赞/ 170 阅读

相关链式前向星——最完美图解

图的存储方法很多，最常见的除了邻接矩阵、邻接表和边集数组外，还有链式前向星。链式前向星是一种静态链表存储，用边集数组和邻接表相结合，可以快速访问一个顶点的所有邻接点，在算法竞赛

╰+攻爆jí腚メ/ 2023年01月22日 07:53/ 0 赞/ 12 阅读

相关链式前向星

链式前向星模板 //前置条件 const int N=105; int hd[N],cnt=0; struct Edge {

蔚落/ 2022年12月26日 15:24/ 0 赞/ 266 阅读

相关【算法与数据结构】——链式前向星

简介链式前向星在我写的[【算法与数据结构】——离散化、拓扑排序以及最短路算法的堆优化][Link 1]这个里面有提到，但是当时描述的比较简单，现在印象有所加深，在详细描

阳光穿透心脏的1/2处/ 2022年08月30日 04:09/ 0 赞/ 203 阅读

相关吝啬的国度_链式前向星

package 搜索; import java.util.Arrays; import java.util.LinkedList; import java.util

一时失言乱红尘/ 2022年07月12日 12:12/ 0 赞/ 185 阅读

相关【树形dp+前向星】Godfather POJ - 3107

Think: 1题意：给出一棵树，询问试探删除一个结点后可使得余下两个连通子图中的最大结点子图的结点数量是所有结点试探的最小值（找到一个点,其所有的子树中最大的子树节点数最

分手后的思念是犯贱/ 2022年06月14日 10:17/ 0 赞/ 207 阅读

相关图论-有向图缩点

强连通(strongly connected)：在一个有向图G里，设两个点 a b 发现，由a有一条路可以走到b，由b又有一条路可以走到a，我们就叫这两个顶点（a，b）强连通

墨蓝/ 2022年05月26日 01:25/ 0 赞/ 208 阅读

相关图论--链式前向星

我们存图的方式通常有邻接矩阵和前向星，邻接矩阵易造成空间浪费，前向星需要sort排序,复杂度是O（nlogn），所以效率不高，链式前向星是前向星的优化，它可以避免排序。以下

短命女/ 2022年05月19日 02:05/ 0 赞/ 323 阅读

相关链式前向星代码

include<bits/stdc++.h> using namespace std; const int maxv=1000000; stru

ゝ一世哀愁。/ 2021年12月17日 13:03/ 0 赞/ 303 阅读