圖有三種常見的存儲(chǔ)方式确镊。分別為：鄰接矩陣愚臀、鄰接表、鏈?zhǔn)角跋蛐?/strong>辩越。
從邏輯上理解鏈?zhǔn)角跋蛐强梢哉J(rèn)為是鄰接表的一種變體嘁扼，只不過這回存的不是節(jié)點(diǎn)，而是邊的信息黔攒。
原理解釋：
- 用一個(gè)結(jié)構(gòu)體數(shù)組來存儲(chǔ)邊集趁啸，每條邊有三個(gè)信息：
- 這條邊的終點(diǎn)(e)
- 這條邊的權(quán)值(v)
- 和這條邊同起點(diǎn)的下一條邊的編號(hào)(next)强缘。 本質(zhì)是用一個(gè)指針域模擬一個(gè)鏈表。
- 還需要一個(gè)head數(shù)組：用來保存某一個(gè)點(diǎn)為起點(diǎn)的所有邊當(dāng)中最后一條邊的編號(hào)不傅。
代碼實(shí)現(xiàn)：
#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
輸出結(jié)果：
1 : {1-->2, 5} {1-->4, 3} {1-->3, 7}
2 :
3 : {3-->5, 9}
4 :
5 : {5-->4, 1} {5-->2, 10}
