圖的基本性質
頂點（vertex）
上圖中黑色的帶數字的點就是頂點，表示某個事物或物件，由于圖的術語沒有標準化，因此，稱頂點為點、節點、結點、端點等都是可以的，叫什么無所謂，理解是什么才是關鍵，
邊（edge）
上圖中頂點之間藍色的線條就是邊，表示事物與事物之間的關系，需要注意的是邊表示的是頂點之間的邏輯關系，粗細長短都無所謂的，包括上面的頂點也一樣，表示邏輯事物或物件，畫的時候大小形狀都無所謂，
有向/無向圖（Directed Graph/ Undirected Graph）
有向圖和無向圖，兩者的區別在于，有向圖中的邊是有方向性的，（可以把無向圖視為“雙向”的有向圖，構造無向圖用的就是這種方法）
一般到底是有向圖還是無向圖要根據實際情況判斷，比如在A、B兩點之間的一條路，那一定是個無向圖，
權重（weight）
邊的權重（或者稱為權值、開銷、長度等），即每條邊都有與之對應的值，例如當頂點代表某些地點時，兩個頂點間邊的權重可以為兩點的距離，
連通圖/連通分量（connected graph/connected component）
如果在圖G中，任意2個頂點之間都存在路徑，那么稱G為連通圖（注意是任意2頂點），如果把下圖看為兩個圖，就是兩個連通圖，
連通分量也叫最（極）大連通子圖，把上圖看為一個整體，它不是一個連通圖，但它有多個連通子圖，0,1,2,3,4頂點構成的子圖就是該圖的最大連通子圖，
注意：對于連通圖來說，它的最大連通子圖就是其本身，
圖的表示
鄰接矩陣
用二維陣列直接存盤，
鄰接矩陣非常好寫，只需要開一個二維陣列，但頂點數目太大會超記憶體（一般不大于1000），用到的情況比較少，
鄰接表
存盤示意圖：
可理解看做是多條單鏈表，結構體定義如下：
struct ENode { int dis, to;//權重、指向 ENode* next = NULL; void push(int to, int dis) { ENode* p = new ENode; p->to = to; p->dis = dis; p->next = next; next = p; } }head[100];
完整測驗：
#include <iostream> #include <fstream> using namespace std; typedef long long LL; struct ENode { int dis, to;//權重、指向 ENode* next = NULL; void push(int to, int dis) { ENode* p = new ENode; p->to = to; p->dis = dis; p->next = next; next = p; } }*head; int main() { #ifdef LOCAL fstream cin("data.in"); #endif // LOCAL /* 5 8 1 3 4 2 4 3 4 5 6 1 5 7 3 5 4 3 4 3 2 5 6 4 1 7 */ int n, m; //n個定點，m條邊 cin >> n >> m; head = new ENode[n + 1]; for (int i = 0; i < m; i++) { int from, to, dis; cin >> from >> to >> dis; head[from].push(to, dis); } for (int i = 1; i <= n; i++) { cout << i; ENode* p = head[i].next; while (p) { if (p)cout << "-->"; cout << p->to; p = p->next; } cout << endl; } return 0; }
其他一些術語
關節點
也叫重連通分量，在連通圖 G 中，如果洗掉頂點 u 及從 u 出發的所有邊后所得的子圖不連通，我們就稱頂點 u 為圖 G 的關節點或連接點，
生成樹
樹（Tree）：如果一個無向連通圖中不存在回路，則這種圖稱為樹，
生成樹 （Spanning Tree）：無向連通圖G的一個子圖如果是一顆包含G的所有頂點的樹，則該子圖稱為G的生成樹，
生成樹是連通圖的極小連通子圖，這里所謂極小是指：若在樹中任意增加一條邊，則將出現一潭訓路；若去掉一條邊，將會使之變成非連通圖，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/137721.html
標籤：其他