图有三种常见的存储方式。分别为:邻接矩阵、邻接表、链式前向星。
从逻辑上理解链式前向星可以认为是邻接表的一种变体,只不过这回存的不是节点,而是边的信息。
原理解释:
- 用一个结构体数组来存储边集,每条边有三个信息:
- 这条边的终点(e)
- 这条边的权值(v)
- 和这条边同起点的下一条边的编号(next)。 本质是用一个指针域模拟一个链表。
- 还需要一个head数组:用来保存某一个点为起点的所有边当中最后一条边的编号。
代码实现:
#include<iostream>
#include<cstring>
using namespace std;
struct edge {
int e, v, next;
};
edge edg[1005];
int n, m, head[1005];
int main() {
memset(head, -1, sizeof(head));
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
edg[i].e = b;
edg[i].v = c;
// 头插法
edg[i].next = head[a];
head[a] = i;
}
for (int i = 1; i <= n; i++) {
cout << i << " : ";
for (int j = head[i]; j != -1; j = edg[j].next) {
cout << "{" << i << "-->" << edg[j].e << ", " << edg[j].v << "} ";
}
cout << endl;
}
return 0;
}
输入样例:
5 6
1 3 7
3 5 9
5 2 10
1 4 3
5 4 1
1 2 5
输出结果:
1 : {1-->2, 5} {1-->4, 3} {1-->3, 7}
2 :
3 : {3-->5, 9}
4 :
5 : {5-->4, 1} {5-->2, 10}