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

╰+攻爆jí腚メ 2023-01-22 07:53 12阅读 0赞

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

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

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

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

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

![20210518222709885.png][]

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

![20210518222610936.png][]

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

1.  输入 1 2 5

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

![20210518222656495.png][]

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

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

![20210518222733582.png][]

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

![20210518222746168.png][]

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

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

![20210518222758754.png][]

1.  输入 1 4 3

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

![20210518222810732.png][]

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70][]

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

![20210518222837829.png][]

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70 1][]

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

2 3 8

2 4 12

3 4 9

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70 2][]

添加一条边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，实际上添加了两条边，如图所示。

![20210518222941306.png][]

这两条边可以通过互为反向边，可以通过与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
    */

[20210518222709885.png]: /images/20221020/901f117b2aef49898a3de02b77502ad7.png
[20210518222610936.png]: /images/20221020/cdb5cda5af104b29bd70998437f67d12.png
[20210518222656495.png]: /images/20221020/ab3b69679e0e47289a56677babd11b58.png
[20210518222733582.png]: /images/20221020/be5352ab459b488092cf164a8c638b9d.png
[20210518222746168.png]: /images/20221020/00cd45fb667e4d76bbd1673fdb672054.png
[20210518222758754.png]: /images/20221020/f17f5418e3ae45bfa977b941f47a4ac6.png
[20210518222810732.png]: /images/20221020/75754fdc63bd4c358a1ab10e9b14edb3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70]: /images/20221020/6dd479c9868549bea0cd9670af372a55.png
[20210518222837829.png]: /images/20221020/5813bd7235724c2fbd5342e26dfde102.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70 1]: /images/20221020/67baf818355c45dc87e03530d3a86536.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW5jaHh5_size_16_color_FFFFFF_t_70 2]: /images/20221020/bf5d31c86c824d0fb1c555b65c1d28be.png
[20210518222941306.png]: /images/20221020/b2635c43428d4ca1a15192ef04b3213f.png