前向星与链式前向星

前向星

前向星是以存储边的方式来存储图，先将边读入并存储在连续的数组中，然后按照边的起点进行排序，这样数组中起点相同的边就能够在数组中进行连续访问了。
其有点在于实现简单，易于理解。缺点是在读入边后需要对所有边进行一次排序，带来了时间开销，实用性也较差。因此只适合离线算法。

链式前向星（实质为数组模拟链表）

链式前向星和邻接表类似，也是链式结构的结合，每个节点i均有一个链表，此链表内的数据均为以节点i为起点的所有边的集合（对比邻接表存的是顶点的集合），边的表示为一个四元组(to,w,next)，其中to代表该条边的有向点对(w,v)，w代表边上的权值，next指向下一条边。
调用的时候只要通过head[i]就能访问到由节点i出发的第一条边的编号，通过编号到edge数组进行索引可以得到边的具体信息，然后根据这条边的next域可以得到第二条边的编号，以此类推，直到next域为INF（这里的INF即head数组初始化的值，一般取-1即可）

链式前向星基本原理

链式前向星是以边为主的存图方式，因此我们需要利用结构体来规划边，这会使图变得更加清晰。

结构

这里注意下面两个必要的数组：

Edge edge[edgenumber];    //结构体数组edge存边，edge[i]表示编号为i的边  
int head[vexnumber];    //head[i]存以节点i为起点的第一条边（在edge中的编号）

这里实现的是

struct Edge{
	int next;   //下一条边的存储下标(默认0) 
	int to;     //某个节点u的邻接点
	int w;      //权值 
}; 
Edge edge[500010];

Edge结构体不用记录顶点u

如上所述，前向星存储的是每个顶点的邻接边。可以知道，在每个顶点后面连接一个链表，不过链表的节点表示的是邻接边而非邻接点。而用数组实现这个链表，就是前向星。
无论采用哪种结构存图，都应该是每读入一条边的信息，就更新一次图的结构。读入一条边u—>v，那么我们在存储图的时候，对于顶点u,该边就是u的一条邻接边，我们就把这条边“挂”在u后面即可。等读入所有的边，建图完成。
顶点u后“挂”的边就全是顶点u的邻接边，因此只需要记录这些邻接边的另一个顶点，而不需要存储顶点u。
由于边是按顺序一条一条读入，我们就很自然的想到对边进行编号，然后将这些边读入edge数组。对于Edge结构体中的next，其实就相当于链表中的next指针。不过此处的next是int型变量，存储的是下一条邻接边的编号。

head数组的用处

head数组相当于邻接链表中的表头数据，head[u]就表示顶点u的某一条邻接边（其编号）。根据这条边的next，就能找出顶点u所有的邻接边。

增边

若以点i为起点的边新增了一条，在edge中的下标为j。那么edge[j].next = head[i]，此后head[i] = j
即每次新加的边作为第一条边，最后倒序遍历

void Add(int u, int v, int w) {  //起点u, 终点v, 权值w 
	//cnt为边的计数，从1开始计 
	edge[++cnt].next = head[u];
	edge[cnt].w = w;
	edge[cnt].to = v;
	head[u] = cnt;    //第一条边为当前边 
} 

遍历

遍历以st为起点的边
for(int i = head[st]; i != -1; i = edge[i].next)
i为开始的第一条边，每次指向下一条，以初始化的-1为结束标志

简单案例

#include <iostream>
using namespace std;
 
#define MAXM 500000 + 10
#define MAXN 10000 + 10
 
struct Edge{
	int next;   //下一条边的存储下标 
	int to;     //这条边的终点 
	int w;      //权值 
}; 
Edge edge[MAXM];
 
int n, m, cnt;
int head[MAXN];  //head[i]表示以i为起点的第一条边 
 
void add(int u, int v, int w) {  //起点u, 终点v, 权值w 
	edge[++cnt].next = head[u];
	edge[cnt].w = w;
	edge[cnt].to = v;
	head[u] = cnt;    //第一条边为当前边 
} 
 
void print() {
	int st;
	cout << "Begin with[Please Input]: \n";
	cin >> st;
	for(int i = head[st]; i != 0; i = edge[i].next) {
		//i开始为第一条边，每次指向下一条(以0为结束标志)若下标从0开始，next应初始化-1 
		cout << "Start: " << st << endl;
		cout << "End: " << edge[i].to << endl;
		cout << "W: " << edge[i].w << endl << endl; 
	}
}
 
int main() {
	int s, t, w;
	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		cin >> s >> t >> w;
		add(s, t, w);
	}
	print(); 
	return 0;
}

链式前向星实现SPFA

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;

#define MAXM 50000 + 10
#define MAXN 10000 + 10
#define INF 0x3f3f3f3f3f

struct Edge {
	int next;
	int to;
	int w;
};
Edge edge[MAXM];

int n, m, st, cnt;
int head[MAXN];

int d[MAXN];
bool inq[MAXN];

inline int Read() {
	char c;
	int ans = 0;
	bool sign = false;
	while (!isdigit(c = getchar()) && c != '-');
	if (c == '-') {
		sign = true;
		c = getchar();
	}
	do {
		ans = (ans << 3) + (ans << 1) + (c ^ '0');
	} while (isdigit(c = getchar()));
	return sign ? -ans : ans;
}

void add(int u, int v, int w) {
	edge[++cnt].next = head[u];
	edge[cnt].to = v;
	edge[cnt].w = w;
	head[u] = cnt;
}

void read() {
	int x, y, w;
	n = Read();
	m = Read();
	st = Read();
	for (int i = 1; i < m; i++) {
		x = Read();
		y = Read();
		w = Read();
		add(x, y, w);
	}
}

void SPFA(int x) {
	d[x] = 0;
	for (int i = 1; i < n; i++)
		d[i] = INF;
	queue<int> q;
	q.push(x);
	inq[x] = true;
	while (!q.empty()) {
		int k = q.front;
		q.pop();
		inq[k] = false;
		for (int i = head[k]; i != 0; i = edge[i].next) {
			int j = edge[i].to;
			if (d[j] > d[k] + edge[i].w) {
				d[j] = d[k] + edge[i].w;
				if (!inq[j]) {
					q.push(j);
					inq[j] = true
				}
			}
		}
	}
	for (int i = 1; i <= n; i++)
		printf("%d ", d[i]);
	printf("\n");
}

int main() {
	read();
	SPFA(st);
	return 0;
}

关于SPFA算法的详解可见SPFA算法详解

打赏