用链式前向星存储图

article/2025/10/16 11:57:40

图最常用的存储结构主要是邻接矩阵和邻接表。当顶点数太大时，用二维数组表示的邻接矩阵可能超内存（MLE），而用邻接表的编码工作量较大，此时，使用vector数组或链式前向星模拟邻接表是不错的选择。因vector数组容易理解，这里仅介绍链式前向星存储图。

设有向图的顶点数n=5，边数m=10，输入的边用三个整数from, to, w，分别表示一条边的起点（弧尾顶点）、终点（弧头顶点），边上的权值。输入的10条边如下：

3 4 7
4 1 3
1 3 5
2 4 8
3 2 5
2 3 6
4 2 5
1 2 9
2 1 4
3 5 7

因链式前向星存储图实际上是静态链表，即用数组模拟链表，这里先回顾邻接表存储图的知识，以便读者能更好地理解链式前向星。若读者清楚知道这部分内容，则可跳过。

邻接表包含表头结点表（一个数组，设为head）和边表（若干链表）两部分，边表的每个链表结点包含邻接点to，权值weight，指向下一条边的指针域next。每条边采用头插法插入对应链表中，则用上述的数据构建的邻接表如下（表头结点表用整型指针数组即可，1~5表示下标）：

相应的实现代码如下：

//有向图的邻接表实现 
#include <iostream>
using namespace std;
const int N=10;
struct ENode{  int to;   		//某弧所指向顶点的下标int weight;     //弧上的权重ENode* next; 	//指向下一条弧
};
ENode* head[N];
int n, m;void insertArc(int from, int to, int weight) {	// 将弧<from,to>加入图ENode *s=new ENode; s->to=to;s->weight=weight;s->next=head[from]; 				   		// 插到链表head[from]的头部        head[from]=s;
}
void output() {                                 //逐个顶点输出各边 for(int i=1;i<=n;i++) {cout<<i<<"";ENode *p=head[i];		while(p!=NULL) {cout<<"->("<<p->to<<","<<p->weight<<")";p=p->next;}cout<<endl;}
}
int main() {	cin>>n>>m;for(int i=1;i<=n;i++) head[i]=NULL;for(int i=0;i<m;i++){	int from, to, w;	cin>>from>>to>>w;insertArc(from, to, w);}output();return 0;
}

输入如下：

5 10
3 4 7
4 1 3
1 3 5
2 4 8
3 2 5
2 3 6
4 2 5
1 2 9
2 1 4
3 5 7

输出结果如下：

1->(2,9)->(3,5)
2->(1,4)->(3,6)->(4,8)
3->(5,7)->(2,5)->(4,7)
4->(2,5)->(1,3)
5

理解邻接表之后，就可以开始链式前向星了。关键是两个数组，一个是类似邻接表的表头结点表的整数数组head，其中head[i]表示以i为起点的最后（输入）那条边的序号（或称编号），对应邻接表边表中以i为起点的第一条边的编号；另一个是next（实现时next作为表示边的结构体的一个成员，用一个结构体数组表示边集，next是结构体数组元素的一个域），其中next[i]表示以第i条边的起点为起点的前一条（输入）边的编号，对应邻接表边表中的下一条边的编号。设边结构体包含的成员为邻接点to，权值weight，指向下一条边的指针（实际上是一个整数）next，则可得上述数据构建的链式前向星（图中的起点是为方便阅读，可不必存储；有时为方便起见，可在边结构体增加起点成员from）如下：

相应的实现代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N=10, M=100;
struct Edge {int to; 	//一条边的终点（弧头顶点）int weight; //边上的权值int next;	//以该条边的起点（弧尾顶点）为起点的前一条（输入）边的编号，对应邻接表边表中的下一条边的编号
};
int head[N];   //head[i]：以i为起点的最后（输入）那条边的编号；对应邻接表边表中以i为起点的第一条边的编号
Edge edges[M];
int cnt; 	//边的编号计数器
int n,m; 	//实际的顶点数和边数
void output();
void addEdge(int from, int to, int w) {cnt++;						//边数增1edges[cnt].to=to;			//终点直接赋值edges[cnt].weight=w;		//边上的权值直接赋值edges[cnt].next=head[from]; //相当于把第cnt条边链接到第from个顶点的第一条边之前head[from]=cnt; 			//把第from个顶点的head值置为当前以from为起点的最后一条边的编号，相当于把最后一条边作为边表的第一条边 
}
int main() {cin>>n>>m;cnt=0;fill(head+1,head+n+1,-1);//把head[1]~head[n]都置为1for(int i=0; i<m; i++) { //输入m条边，建立链式前向星存储结构int from,to,w;cin>>from>>to>>w;addEdge(from, to, w);}output();				//输出head、edges数组验证return 0;
}
void output() {				//输出head、edges数组的函数cout<<"head:\n";for (int i=1; i<=n; i++) {cout<<i<<": "<<head[i]<<endl;}cout<<"edges:\n";for (int i=1; i<=m; i++) {cout<<i<<": "<<edges[i].to<<" "<<edges[i].weight<<" "<<edges[i].next<<endl;}
}

输入如下：

5 10
3 4 7
4 1 3
1 3 5
2 4 8
3 2 5
2 3 6
4 2 5
1 2 9
2 1 4
3 5 7

输出结果如下：

head:
1: 8
2: 9
3: 10
4: 7
5: -1
edges:
1: 4 7 -1
2: 1 3 -1
3: 3 5 -1
4: 4 8 -1
5: 2 5 1
6: 3 6 4
7: 2 5 2
8: 2 9 3
9: 1 4 6
10: 5 7 5