【数据结构】 链式前向星

大家好，欢迎来到IT知识分享网。

目录

一. 背景概述 

二. 实现思路

1. 头节点数组

2. 边结构体

3. 加边函数

4. 图的遍历

三. 例题分析

1. HDU – 6386  Age of Moyu   

一. 背景概述 

        图的存储方式主要有链接矩阵、邻接表两种，邻接矩阵的好处是写建图简单方便但占内存较大，节点数量稍微大点的题目就开不下数组了（适合稠密图）；而邻接表虽然节省空间，但其指针形式难写易错，且vector形式的读取太慢易导致大数据下的TLE。针对上述问题，这里就产生了一种比较中庸的方式：链式前向星。

        简单来说，链式前向星就是把数据以链表形式连接在一起，那么连接的条件是什么呢？我们回想一下图里面邻接表里存的是每个点的连接点。那么这里的链式前向星存的就是以每个点为起点的所有边。

二. 实现思路

1. 头节点数组

        建立head[maxn]数组，其中head[id]表示以 id 节点为起点的第一条边的编号，也就是查询以该节点为起点的所有边的开始边，也就是链表头部。

2. 边结构体

//Node结构体，存储每条边的终点to , 连在同一起点上的下一条边的编号next ， 边权值v struct Node { int to,next,v; };

3. 加边函数

//加边操作：这段代码是核心，也很好理解就是不断把边的编号连在链表上（tot表示边的编号） void AddEdge(int a,int b,int c) { //加边函数，连一条以a为起点到达b权值为c的边 node[tot].next = head[a];node[tot].to = b;node[tot].flag = c;head[a] = tot++; }

        注意 head 数组一般初始化为-1，表示无边可连。

4. 图的遍历

        很明显，head[i]保存的是以i为起点的所有边中编号最大的那个，而把这个当作顶点i的第一条起始边的位置。这样在遍历时是倒着遍历的，也就是说与输入顺序是相反的，不过这样不影响结果的正确性。

        比如以上图为例，以节点1为起点的边有3条，它们的编号分别是0,3,5；而head[1] = 5，我们在遍历以u节点为起始位置的所有边的时候是这样的:

for(int i=head[u];~i;i=edge[i].next) { //do... }

        那么就是说先遍历编号为5的边，也就是head[1]，然后就是edge[5].next，也就是编号3的边，然后继续edge[3].next，也就是编号0的边，可以看出是逆序的。直到head[i]==-1为止。

三. 例题分析

1. HDU – 6386  Age of Moyu   

给你n个港口,m个路线。接下来m行给你a,b,c代表从a港口到b港口是航线c。题目规定在一条航线上行驶花费始终为1，但是如果改变一次航线，则花费就增加1。问你从初始1港口到达n港口所需要的最小花费.

        在做的时候第一想法是用并查集维护一条航线上的点，把同一条航线之间全部两两连线，长度都归为1。然后再跑一遍最短路。但是在两两连线的时候就涉及到了怎么连能减少时间开销，然后超时；

        后来发现其实不用并查集，用一个结构体记录一下到该港口的目前花费，然后从该港口p出发去其他港口q时，要判断pq之间航线和到达p的航线是否相同相同的话cost + 0.否则cost + 1；然后更新dis存入队列。（越想越觉得像个优先队列做的BFS）所以还要记录的是到达港口p的航线是什么。这样搜下去就能找到最优答案了。在实现方面时直接用vector邻接表会超时，因此需要用链式前向星来解决。其代码如下：

#include <iostream> #include<cstring> #include<cstdio> #include<string> #include<algorithm> #include<queue> #include<vector> using namespace std; #define INF 0x3f3f3f3f const int maxn =  + 10; typedef pair<int,int> P; struct Node//结构体进行链式前向星存图 { int to,next,flag;//终点 + 下个边编号 + 当前航线 }; Node node[2*maxn]; int dis[maxn],head[maxn]; bool judge[maxn]; int n,m,tot; void AddEdge(int a,int b,int c)//加边函数（分配编号） { node[tot].next = head[a];node[tot].to = b;node[tot].flag = c;head[a] = tot++; } struct Arrive//在跑最短路时记录前导航线 + 目前花费 + 当前港口 { int flagin,val,portid; bool operator <(const Arrive &another)const{//按照花费由小到大排序 return val>another.val; } Arrive(int a,int b,int c):flagin(a),val(b),portid(c) {} }; void Dijkstra(int a) { priority_queue<Arrive>que; que.push(Arrive(0,0,a)); while(!que.empty()){ Arrive p = que.top(); que.pop(); int id = p.portid; if(judge[id])continue; judge[id] = 1; for(int i = head[id];~i;i = node[i].next){//遍历链式前向星 int cost = p.val + (p.flagin==node[i].flag?0:1);//估测花费（判断航线是否一致） if(dis[node[i].to]>cost&&!judge[node[i].to]){//更新 dis[node[i].to] = cost; que.push(Arrive(node[i].flag,cost,node[i].to)); } } } } int main() { while(scanf("%d%d",&n,&m)!=EOF){ tot = 0;//初始化 memset(dis,INF,sizeof(dis));//这个地方用mem A了而且时间很短，用循环超时QAQ //for(int i = 0;i<=n;i++)dis[i] = INF; memset(judge,0,sizeof(judge)); memset(head,-1,sizeof(head)); for(int i = 0;i<m;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); AddEdge(a,b,c);//无向图双向建边 AddEdge(b,a,c); } dis[1] = 0; Dijkstra(1); printf("%d\n",dis[n]==INF?-1:dis[n]); } return 0; }