數據結構學習筆記＜7＞圖

一、圖#

1. 什麼是圖#

表示 “多對多” 的關係，包含了：

一組頂點：通常用 V (Vertex) 表示頂點集合
一組邊：通常用 E (Edge) 表示邊的集合
無向邊是頂點對：(v，w) ∈ E，其中 v，w∈V
有向邊 <v,w> 表示從 v 指向 w 的邊 (單行線)
不考慮重邊和自回路

抽象數據類型定義#

類型名稱：圖 (Graph)
數據對象集：G (V,E) 由一個非空的有限頂點集合 V 和一個有限邊集合 E 組成。
操作集：對於任意圖 G ∈ Graph, 以及 v ∈ V，e ∈ E

Graph Create (): 建立並返回空圖；
Graph InsertVertex (Graph G, Vertex v)：將 v 頂點插入圖 G
Graph InsertEdge (Graph G, Edge e): 將邊 e 插入圖 G
void DFS (Graph G, Vertex v): 從頂點 v 出發深度優先遍歷圖 G；
void BFS (Graph G, Vertex v): 從頂點 v 出發廣度優先遍歷圖 G；
void ShortestPath (Graph G, Vertex v, int Dist []): 計算圖 G 中頂點 v 到其他任意頂點的最短距離；
void MST (Graph G): 計算圖 G 的最小生成樹
常用術語：
無向圖、有向圖、網絡等……

怎樣在程序中表示圖#

鄰接矩陣#

在這裡插入圖片描述

鄰接矩陣的好處

直觀、簡單、好理解
方便檢查任意一對頂點間是否存在邊
方便找任一頂點的所有 “鄰接點”(有邊直接相連的頂點)
方便計算任一頂點的 “度”(從該點發出的邊數為 “出度”，指向該點的邊數為 “入度”)
- 無向圖為對應行 (或列) 非 0 元素的個數
- 有向圖：對應行非 0 元素的個數是出度，對應列非 0 元素的個數是入度

鄰接表#

指針數組 + 鏈表，點很稀疏的時候很合算
在這裡插入圖片描述
鄰接表的好處：

方便找任一頂點的所有 “鄰接點”(有邊直接相連的頂點)
節約稀疏圖的空間
- 需要 N 個頭指針 + 2E 個結點（每個結點至少 2 個域）
方便計算無向圖任一頂點的 “度”，但對有向圖只能計算出度。

2. 圖的遍歷#

DFS 深度優先搜索#

深度優先搜索 (Depth First Search,DFS), 對每一個可能的分支路徑深入到不能再深入為止，而且每個節點只能訪問一次.
偽代碼描述：

void DFS(Vertex V) {
	visited[V] = true;
	for(v的每個鄰接點W)
		if (!visited[W])
			DFS(W);
}

BFS 廣度優先搜索#

廣度優先搜索 (Breadth First Search,BFS), 借助隊列 (先進先出) 來實現
偽代碼描述：

void BFS(Vertex V) {
	visited[V] = true;
	Enqueue(V, Q);//將該頂點放入隊列中
	while(!IsEmpty(Q)) {//當隊列為空時結束搜索
		V = Dequeue(Q);//V為隊首元素
		for(V的每個鄰接點W) {
			if ( !visited[W] ) {
				visited[W] = true;//標記該點已訪問
				Enqueue(W, Q);//將該點壓入隊列中
			}
		}
	}
}

圖不連通怎麼辦？#

路徑：V 到 W 的路徑是一些列頂點 {V，V1，V2，……，Vn，W} 的集合，其中任一對相鄰的頂點間都有圖中的邊。路徑的長度是路徑中的邊數 (若帶權，則是所有邊的權重和)。若 V 到 W 之間的所有頂點都不同，則稱為簡單路徑
連通：若 V 到 W 存在一條 (無向)路徑，則稱 V 和 W 是連通的
回路：起點等於終點的路徑
連通圖：圖中任意兩頂點均連通
連通分量：無向圖的極大連通子圖
- 極大頂點數：再加 1 個頂點就不連通了
- 極大邊數：包含子圖中所有頂點相連的所有邊
強連通：有向圖中頂點 V 和 W 之間存在雙向路徑，則稱 V 和 W 是強連通的
強連通圖：有向圖中任意兩頂點均強連通
強連通分量：有向圖的極大強連通子圖

每調用一次 DFS，其實就是把 V 所在的連通分量遍歷了一遍。BFS 也一樣。

void ListComponents ( Graph G ) {//遍歷連通分量
	for (each V in G)
		if ( !visited[V] ) {
			DFS( V );
		}
}

3. 如何建立圖#

(1) 鄰接矩陣表示的圖的建立#

定義#

const int MaxVertexNum = 100;
typedef int DataType;
typedef bool WeightType;
typedef struct GNode *PtrToGNode;
struct GNode {
    int Nv;//頂點數
    int Ne;//邊數
    WeightType G[MaxVertexNum][MaxVertexNum];
    DataType Data[MaxVertexNum];//存頂點的數據
};
typedef PtrToGNode MGraph;//以鄰接矩陣存儲的圖類型

初始化#

初始化一個有 VertexNum 個頂點但沒有邊的圖

typedef int Vertex;
MGraph CreateGraph(int VertexNum) {
    Vertex V, W;
    MGraph Graph;
    Graph = (MGraph) malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    //頂點編號從0開始，到Graph->Nv-1
    for (V = 0; V < Graph->Nv; V++) {
        for(W = 0; W < Graph->Nv; W++) {
            Graph->G[V][W] = 0; //有向圖中可改0為INF等
        }
    }
    return Graph;
}

向圖中插入邊#

邊的定義

typedef struct ENode *PtrToENode;
struct ENode {
    Vertex V1, V2;//有向邊<V1,V2>
    WeightType Weight;//權重
};
typedef PtrToENode Edge;

插入操作

void InsertEdge(MGraph Graph, Edge E) {
    //插入邊<V1,V2>
    Graph->G[E->V1][E->V2] = E->Weight;
    //若為無向圖，則還要插入邊<V2,V1>
    Graph->G[E->V2][E->V1] = E->Weight;
}

完整的建立一個 MGraph#

輸入格式

Nv Ne
V1 V2 Weight
……

MGraph BuildGraph() {
    MGraph Graph;
    Edge E;
    Vertex V;
    int Nv;
    cin >> Nv;
    Graph = CreateGraph(Nv);//建立有Nv個頂點的圖
    cin >> Graph->Ne;//邊數Ne
    if(Graph->Ne != 0) {
        E = (Edge)malloc(sizeof(struct ENode));
        for (int i = 0; i < Graph->Ne; i++) {
            cin >> E->V1 >> E->V2 >> E->Weight;
            InsertEdge(Graph, E);
        }
    }
    //如果頂點有數據的話，讀入數據
    for(V = 0; V < Graph->Nv; V++) {
        cin >> Graph->Data[V];
    }
    return Graph;
}

(2) 鄰接表表示的圖的建立#

可在鄰接矩陣的基礎上進行修改

定義#

const int MaxVertexNum = 100;
typedef int DataType;
typedef int Vertex;
typedef bool WeightType;
//鄰接表定義
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode {
    Vertex AdjV;//鄰接點下標
    WeightType Weight;//邊權重
    PtrToAdjVNode Next;
};

typedef struct VNode {
    PtrToAdjVNode FirstEdge;
    DataType Data;//存頂點的數據
}AdjList;

typedef struct GNode *PtrToGNode;
struct GNode {
    int Nv;//頂點數
    int Ne;//邊數
    AdjList G;//鄰接表
};
typedef PtrToGNode LGraph;//以鄰接表存儲的圖類型

LGraph 初始化#

LGraph CreateGraph(int VertexNum) {
    Vertex V, W;
    LGraph Graph;
    Graph = (LGraph) malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    //頂點編號從0開始，到Graph->Nv-1
    for (V = 0; V < Graph->Nv; V++) {
        Graph->G[V].FirstEdge = NULL;
    return Graph;
}

向 LGraph 中插入邊#

typedef struct ENode *PtrToENode;
struct ENode {
    Vertex V1, V2;//有向邊<V1,V2>
    WeightType Weight;//權重
};
typedef PtrToENode Edge;
void InsertEdge(LGraph Graph, Edge E){
    PtrToAdjVNode NewNode;
    //插入邊<V1,V2>
    //為V2建立新的鄰接點
    NewNode = (PtrToAdjVNode) malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V2;
    NewNode->Weight = E->Weight;
    //將V2鄰接點插入V1的表頭
    NewNode->Next = Graph->G[E->V1].FirstEdge;
    Graph->G[E->V1].FirstEdge = NewNode;
    
    //若為無向圖 則還要插入邊<V2,V1>
    //為V2建立新的鄰接點
    NewNode = (PtrToAdjVNode) malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V1;
    NewNode->Weight = E->Weight;
    //將V2鄰接點插入V1的表頭
    NewNode->Next = Graph->G[E->V2].FirstEdge;
    Graph->G[E->V2].FirstEdge = NewNode;
}

完整的建立一個 LGraph#

僅需將 MGraph 換成 LGraph，將存 Data 是稍作更改即可

LGraph BuildGraph() {
    LGraph Graph;
    Edge E;
    Vertex V;
    int Nv;
    cin >> Nv;
    Graph = CreateGraph(Nv);//建立有Nv個頂點的圖
    cin >> Graph->Ne;//邊數Ne
    if(Graph->Ne != 0) {
        E = (Edge)malloc(sizeof(struct ENode));
        for (int i = 0; i < Graph->Ne; i++) {
            cin >> E->V1 >> E->V2 >> E->Weight;
            InsertEdge(Graph, E);
        }
    }
    //如果頂點有數據的話，讀入數據
    for(V = 0; V < Graph->Nv; V++) {
        cin >> Graph->G[V].Data;
    }
    return Graph;
}

二、最短路徑問題#

1. 概念簡介#

在網絡中，求兩個不同頂點之間的所有路徑中，邊的權值之和最小的那一條路徑
- 這條路徑就是兩點之間的最短路徑 (Shortest Path)
- 第一個頂點叫源點 (Source)
- 最後一個頂點叫終點 (Destination)

2. 問題分類#

單源最短路徑問題：從某固定源點出發，求其到所有其他頂點的最短路徑
- (有向) 無權圖
- (有向) 有權圖
多源最短路徑問題：求任意兩頂點之間的最短路徑

2. 無權圖的單源最短路算法#

按照遞增的順序找出到各個頂點的最短路，與 BFS 思想很類似！
在這裡插入圖片描述
首先需要定義一個數組 dist,dist [W] 存儲 S 到 W 的最短距離，S 為起點，dist [S]=0，dist 需要被初始化成一個 - 1 (或無窮)，便於後來的判別是否被訪問過。
其次需要定義數組 path,path [W] 存儲 S 到 W 的路上經過的某頂點。
dist 和 path 數組都需先被初始化為 - 1~ 然後將起點的 dist [S] 設為 0，壓入隊列開始訪問
偽代碼：

void Unweighted(Vertex S) {
	Enqueue(S, Q);
	while(!IsEmpty(Q)) {
		V = Dequeue(Q);
		for (V的每個鄰接點W)
			if(dist[W] == -1) {
				dist[W] = dist[V]+1;
				path[W] = V;
				Enqueue(W, Q);
			}
	}
}

3. 有權圖的單源最短路算法#

在這裡插入圖片描述

Dijkstra 算法！#

令 s={源點 s + 已經確定了最短路徑的頂點 v~i~}
對任一未收錄的頂點 v 定義 dist [v] 為 s 到 v 的最短路徑長度，但該路徑僅經過 S 中的頂點，即路徑 {s→(v~i~∈S)→v} 的最小長度
若路徑是按照遞增的順序生成的，則
- 真正的最短路必須只經過 S 中的頂點 (反證法可證)
- 每次從未收錄的頂點中選一個 dist 最小的收錄 (貪心)
- 增加一個 v 進入 S, 可能會影響另外一個 w 的 dist 值！(所以要檢查 v 的所有鄰接點 w！)
  - dist [w] = min { dist [w]，dist [v] + <v,w > 的權重}
    dist 初始化：S 的所有鄰接點 W 的 dist 都可初始化為 s 與 w 的權重，其他則定義為正無窮。

偽代碼描述：

void Dijkstra(Vertex s) {
	while (1){
		V = 未收錄頂點中dist最小者;
		if (這樣的V不存在)
			break;
		collected[V] = true;
		for (V的每個鄰接點W)
			if(collected[W] == false)
				if(dist[V] + E<v,w> < dist[W]) {
					dist[W] = dist[V]+E<v,w>;
					path[W] = V;
				}
	}
}//不能解決有負邊的情況

偽代碼中 dist [W]=dist [V]+E~<V,W>~；並不是簡單的賦值，而是如果有了更短的距離，需要將其更新成為更短的距離
在這裡插入圖片描述

Dijkstra 核心代碼#

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1005;
const int inf  = 0x3f3f3f;
int T,N,x,y,z;
int edge[maxn][maxn];
int dist[maxn];
bool vis[maxn];
void init() {
    for(int i = 1; i <= N; ++i) {
        for(int j = 1; j <= N; ++j) {
            edge[i][j] = inf;
        }
        edge[i][i] = 0;
    }
}
void Dijstra(int u) {
    for(int i = 1; i <= N; ++i) {
        vis[i] = false;
        dist[i] = edge[u][i];
    }
    vis[u] = true;
    for(int i = 1; i <= N; ++i) {
        int t, mindis = inf;
        for(int j = 1; j <= N; ++j) {
            if(!vis[j] && dist[j] < mindis) {
                mindis = dist[j];
                t = j;
            }
        }
        vis[t] = true;
        for(int j = 1; j <= N; ++j) 
            if(!vis[j] && dist[j] > edge[t][j] + dist[t]) 
                dist[j] = edge[t][j] + dist[t];
    }
}

三、最小生成樹#

1. 什麼是最小生成樹 (Minimum Spanning Tree)#

是一棵樹
- 無回路
- |V | 個頂點一定有 | V|-1 條邊
是生成樹
- 包含全部頂點
- |V|-1 條邊都在圖裡
- 向生成樹中任加一條邊都一定構成回路
邊的權重和最小

最小生成樹與圖連通等價

2. 解決最小生成樹問題#

通常離不開貪心算法：

“貪”：每一步都要最好的
“好”：權重最小的邊
需要約束：
- 只能用圖裡有的邊
- 只能正好用掉 | V|-1 條邊
- 不能有回路

放到了另一篇博客裡。
圖論 —— 解決最小生成樹問題 (Kruskal 算法 & Prim 算法)