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

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

链式前向星存储包括两种结构：

1. 边集数组：edge[ ]，edge[i]表示第i条边；
2. 头结点数组：head[ ]，head[i]存以i为起点的第一条边的下标(在edge[]中的下标)

struct node{
    int to,next,w;
}edge[maxe];//边集数组，边数一般要设置比maxn*maxn大的数，如果题目有要求除外

int head[maxn];//头结点数组

每一条边的结构，如图所示。

例如，一个无向图，如图所示。

按以下顺序输入每条边的两个端点，建立的链式前向星，过程如下。

1. 输入 1 2 5

创建一条边1—2，权值为5，创建第一条边edge[0]，如图所示。

然后将该边链接到1号结点的头结点中。（初始时head[]数组全部初始化为-1）

即edge[0].next=head[1]; head[1]=0; 表示1号结点关联的第一个条边为0号边，如图所示。图中的虚线箭头仅表示他们之间的链接关系，不是指针。

因为是无向图，还需要添加它的反向边，2—1，权值为5。创建第二条边edge[1]，如图所示。

然后将该边链接到2号结点的头结点中。

即edge[1].next=head[2]; head[2]=1; 表示2号结点关联的第一个条边为1号边，如图所示。

1. 输入 1 4 3

创建一条边1—4，权值为3，创建第3条边edge[2]，如图所示。

然后将该边链接到1号结点的头结点中（头插法）。

即edge[2].next=head[1]; head[1]=2; 表示1号结点关联的第一个条边为2号边，如图所示。

因为是无向图，还需要添加它的反向边，4—1，权值为3。创建第4条边edge[3]，如图所示。

然后将该边链接到4号结点的头结点中。

即edge[3].next=head[4]; head[4]=3; 表示4号结点关联的第一个条边为3号边，如图所示。

1. 依次输入以下三条边，创建的链式前向星，如图所示。

2 3 8

2 4 12

3 4 9

添加一条边u v w的代码如下：

void add(int u,int v,int w){//添加一条边
    edge[cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}

如果是有向图，每输入一条边，执行一次add(u,v,w)即可；如果是无向图，则需要执行两次add(u,v,w); add(v,u,w)。

如何使用链式前向星访问一个结点u的所有邻接点呢？

for(int i=head[u];i!=-1;i=edge[i].next){
    int v=edge[i].to; //u的邻接点
    int w=edge[i].w; //u—v的权值
       …
}

链式前向星的特性：

1. 和邻接表一样，因为采用头插法进行链接，所以边输入顺序不同，创建的链式前向星也不同。
2. 对于无向图，每输入一条边，需要添加两条边，互为反向边。例如，输入第一条边1 2 5，实际上添加了两条边，如图所示。

这两条边可以通过互为反向边，可以通过与1的异或运算得到其反向边，0^1=1，1^1=0。也就是说如果一条边的下标为i，则其反向边为i^1。这个特性应用在网络流中非常方便。

3.链式前向星具有边集数组和邻接表的功能，属于静态链表，不需要频繁地创建结点，应用十分灵活。

总代码：

#include<iostream>//创建无向网的链式前向星 
#include<cstring>
using namespace std;
const int maxn=100000+5;
int maxx[maxn],head[maxn];
int n,m,x,y,w,cnt;

struct Edge{
	int to,w,next;
}e[maxn];

void add(int u,int v,int w){//添加一条边u--v 
 	e[cnt].to=v;
 	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt++;
} 

void printg(){//输出链式前向星
	cout<<"----------链式前向星如下：----------"<<endl;
	for(int v=1;v<=n;v++){
		cout<<v<<"：  ";
		for(int i=head[v];~i;i=e[i].next){
			int v1=e[i].to,w1=e[i].w;
			cout<<"["<<v1<<" "<<w1<<"]\t";
		}
		cout<<endl;
	}
}

int main(){
	cin>>n>>m;
	memset(head,-1,sizeof(head));
	cnt=0;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>w;
		add(x,y,w);//添加边
		add(y,x,w);//添加反向边 
	}
	printg();
	return 0;
}
/*输入样例
4 5
1 2 5
1 4 3
2 3 8
2 4 12
3 4 9
*/