前言

資料結構，一門資料處理的藝術，精巧的結構在一個又一個演算法下發揮著他們無與倫比的高效和精密之美，在為資訊技術打下堅實地基的同時，也令無數開發者和探索者為之著迷，

也因如此，它作為博主大二上學期最重要的必修課出現了，由于大家對于上學期C++系列博文的支持，我打算將這門課的筆記也寫作系列博文，既用于整理、消化，也用于同各位交流、展示資料結構的美，

此系列文章，將會分成兩條主線，一條“資料結構基礎”，一條“資料結構拓展”，“資料結構基礎”主要以記錄課上內容為主，“拓展”則是以課上內容為基礎的更加高深的資料結構或相關應用知識，

歡迎關注博主，一起交流、學習、進步，往期的文章將會放在文末，

簡述

圖論，毋庸置疑是資料結構知識體系中的一顆璀璨的明星，是幾種邏輯結構中復雜性最高，最變化莫測的結構，因此在初學時眾多角度不同的問題總是會成為各式各樣的絆腳石，拓撲序列、最短路徑、最小生成樹…等等等等

而學習計算機科學專業畫風的圖論與數學專業畫風的圖論有著大相徑庭的方向，很顯然，計算機學家更注重圖論演算法的表示和實作而數學家更傾向于研究圖論高級的性質，

在眾多計算機領域需要討論的圖論內容中，圖的存盤結構及其遍歷方法無疑是一切演算法實作的起點，

俗話說：基礎不牢，地動山搖，在所有基礎圖論演算法學習程序中遇到的阻礙，都能在其中或多或少地窺到對存盤和遍歷內容掌握不牢的身影，

所以，下面就讓我們來夯實基礎，梳理一下幾種存盤結構之下的兩種遍歷方案吧~

下文的內容會與圖的存盤結構緊密相關，對于常用圖的存盤掌握不熟悉的同學們可以先觀看上一篇文章：圖的存盤結構

深度優先遍歷

深度優先遍歷，英文全稱叫做" d e e p f i r s t s e a r c h deep \ first\ search deep first search"，簡稱" D F S DFS DFS"，

所謂深度優先，就是每次向著更深層次的結點走，走到盡頭再進行回溯的遍歷方案，

這種遍歷方案具有遞回呼叫自身的顯著特征，所以在實作時，也常常是使用遞回結構，

單單堆砌概念很難精準把握其意思，我們還是抓緊上代碼開始實戰吧，哦吼，

在開始遍歷之前，還是要有一些前置約定：

• 遍歷過的點打上標記不用再遍歷，可以使用如下的一個陣列來完成這個任務

bool vis[N];
//vis[k] = true 表示結點k被遍歷過
//vis[k] = false 表示結點k未被遍歷過

• 該圖為有向無權圖

鄰接矩陣

使用鄰接矩陣存盤的圖，在尋找可遍歷的子節點時特點就是需要列舉所有結點查看是否存在邊，

我們約定鄰接矩陣定義如下：

bool am[N][N];
//am[x][y] = true 表示x到y之間存在邊

那么遍歷圖的遞回程式的基本結構實作如下：

void dfs(int k){//當前結點
	vis[k] = true;//該點被遍歷過，打上標記
	for(int i = 1;i <= n;i++){
		if(!am[k][i]){//如果k與i之間沒有邊相連，則跳過
			continue;
		}
		if(vis[i]){//如果該節點已經被遍歷過，則跳過
			continue;
		}
		dfs(i);//遍歷更深層次的結點，完成該節點遍歷后再進行其他后繼節點遍歷
	}
}

鄰接表

使用鄰接表存盤圖的一大特點就是將每個結點可到達的結點資訊分開存盤在各自的鏈表中，而非像鄰接矩陣一樣存盤在同一個二維矩陣中，

每個鏈表的鏈首被統一記錄在一個頭結點陣列中，我們給定鄰接表定義如下：

struct Edge{//邊鏈表結點
	int vertex;//邊終點
	//如果有權值可以繼續添加欄位
	Edge * next;//鏈表后繼指標
};

Edge * head[N];//鏈首陣列，存盤所有鏈表頭結點

那么遍歷程序如下：

void dfs(int k){
	vis[k] = true;//標記遍歷過
	for(Edge * edge = head[k];edge != NULL;edge = edge->next){
		if(vis[edge->vertex]){//如果終點已經被遍歷過則跳過
			continue;
		}
		dfs(edge->vertex);
	}
}

陣列鄰接表

陣列模擬的鄰接表的特點就是放棄了動態記憶體的管理，而使用已經宣告好的陣列靜態記憶體來管理邊結點的加入，他仍然是鏈表結構，但不再使用指標獲取后繼元素位置，取而代之的是使用在陣列中的下標來表示，

陣列的鄰接表定義如下：

struct Edge{
	int vertex;//終點
	int next;//后繼邊結點在陣列中的下標,0為空
};
Edge nxt[M];//存放邊結點的陣列
int head[N];//存放各節點邊鏈表頭結點的陣列
int tot;//邊結點計數

那么dfs的實作如下：

void dfs(int k){
	vis[k] = true;//節點被遍歷過，打上標記
	for(int i = head[k];i != 0;i++){
		if(vis[nxt[i].vertex]){
			continue;
		}
		dfs(nxt[i].vertex);
	}
}

經典應用：有向圖判定環

有向圖找環其實是個老生常談的問題，他非常的常見，也有很多的變體，包括尋找最大環，負環等等，

使用深度優先遍歷的一大特點就是每次只能遍歷一條線路上的結點，路線上結點的先后次序呈現堆疊的結構，

根據這一特點，如果某個結點的后繼在當前堆疊中則可以說明遍歷程序中尋找到了一個環，

所以只需要將上文的遍歷方案稍加改造，加入一個全域的判定陣列用以標記結點是否在堆疊中，當遍歷到結點時將其入堆疊，遍歷結束后將其出堆疊，

這里還需要注意區分堆疊的標記陣列和是否遍歷的標記陣列，他們的功能并不相同，

同時需要函式增加一個回傳值，表示有沒有尋找到環

存盤結構采用鄰接表：

bool stack[N];//標記結點是否位于堆疊中
bool dfs(int k){
	vis[k] = true;//標記該節點遍歷過
	stack[k] = true;//結點入堆疊

	for(Node * node = head[k];node != NULL;node = node->next){
		if(stack[node->vertex]){//判斷后繼節點是否在堆疊中，如果在，則找到一個環
			return true;
		}
		if(vis[node->vertex]){//如果該節點已經被遍歷，則跳過
			continue;
		}
		if(dfs(node->vertex)){//遍歷后繼節點，如果后繼節點找到環，則直接放回true
			return true;
		}
	}	

	stack[k] = false;//結點出堆疊
	return false;//沒有找到環
}

廣度優先遍歷

廣度優先遍歷，英文全稱為" b r e a d t h f i r s t s e a r c h breadth\ first\ search breadth first search",簡稱 B F S BFS BFS

寬度優先的意思是優先遍歷同一層次的結點，當一個層次的結點遍歷完了，再遍歷下一層次的結點，這與深度優先遍歷的方案恰好相對，

有意思的是，不僅是邏輯結構上相對，在結點次序對應的資料結構上，他們也分別對應兩個特殊的線性結構——堆疊和佇列，

在上文中我們說深度優先遍歷對應的結點次序結構是一種堆疊，現在的廣度優先遍歷結點次序對應的就是佇列了，準確說，這個佇列是預遍歷序列，他們只是按照順序等待被遍歷，

如下圖：

之所以說這個結構是一個佇列，一個重要的原因是這些結點不是預先放置在線性表中的，而是在遍歷程序中添加進去的，當遍歷第k層結點時，將其子節點加入隊尾，當遍歷完整個第k層時，后方的所有結點就都是k+1層的結點了，

鄰接矩陣

我們說，實作廣度優先遍歷的關鍵是實作佇列，那么為了方便演示，佇列就是用陣列和兩個動態下標表示：

int queue[N];//佇列陣列
int l = 1;//隊首
int r = 0;//隊尾

k = queue[l++];//獲取出隊元素
queue[++r] = k;//入隊元素

同時為了防止結點被多次加入佇列而多次被遍歷，我們還要加入一個陣列，用以標記結點已經進入佇列，

bool inQueue[N];//標記結點是否已經入隊

那么，使用鄰接矩陣存盤的圖，使用廣度優先遍歷的方式如下：

int k;
while(l <= r){//佇列不為空條件
	k = queue[l++];
	for(int i = 1;i <= n;i++){
		if(!dis[k][i]){//如果沒有邊，跳過
			continue;
		}
		if(inQueue[i]){//如果該節點已經加入佇列，跳過
			continue;
		}
		//結點i入堆疊
		inQueue[i] = true;
		queue[++r] = i;
	}
}

鄰接表

我們應該清楚，在目前的遍歷規則下，結點佇列和圖的存盤結構是兩個不同的維度，相互之間的影響非常有限，因此改變的圖的存盤結構，從鄰接矩陣改變為鄰接表對于遍歷實作的影響也非常小，只需要改變訪問子節點的方式即可：

int k;
while(l <= r){
	k = queue[l++];
	for(Edge * edge = head[k];edge != NULL;edge = edge->next){
		if(inQueue[edge->vertex]){
			continue;
		}

		inQueue[i] = true;
		queue[++r] = edge->vertex;
	}
}

陣列鄰接表

int k;
while(l <= r){
	k = queue[l++];
	for(int i = head[k];i != 0;i = nxt[i].next){
		if(inQueue[nxt[i].vertex){
			continue;
		}
	
		inQueue[i] = true;
		queue[++r] = nxt[i].vertex;
	}
}

經典應用：最短合法路徑

寬度優先遍歷的特點就是其按照層次進行遍歷，在尋求最短路徑的問題上也有著自己獨特的優勢，尤其是我們現在要討論的問題：無權圖的最短合法路徑

這類問題非常的常見，一個經典的例子是迷宮游戲

但是這里不說這個模型，迷宮的規則總是復雜的，有權的迷宮也不在少數，所以不妨來討論一個更簡單且異曲同工的模型：

在上圖中，從點1出發，到達終點點7，最短的一條路需要走多少步，

在這個問題中，到達終點的路徑可能有很多，肉眼看去，答案顯而易見為 1 ? > 6 ? > 7 1->6->7 1?>6?>7，需要兩步，

如果使用深度優先遍歷的話，即使找到了一條通往終點的路徑，但是在沒有窮盡所有可能的前提下，無法確定其最短方案是否就是當前的一種，所以深度優先遍歷只能一點點的記錄答案最小值，不斷地迭代更新，

但使用寬度優先遍歷的方案，問題就變得不一樣了，因為無論怎么遍歷，第一次出現的終點結點的層數一定是最小的，其方案也一定是最短的，這樣就可以將解決方案優化，

對于上圖來說，這意味著如果我們將1定義為第0層的話，那么7最早在第二層出現，

下面就讓我們使用代碼來實作它吧：

輸入格式：
第一行為四個整數n,m,s,t，表示點數和邊數以及起點和終點，保證終點能夠到達
接下來m行，每行兩個整數x,y，表示結點x和y之間存在一條邊
輸出格式：
一個整數表示起點到終點的最短距離

#include<iostream>
using namespace std;
const int N = 2000;

struct Edge{
	int vertex;//終點
	Edge * next;

	Edge(int vertex,Edge * next){//建構式
		this->vertex = vertex;
		this->next = next;
	}
};
Edge * head[N];//鏈表頭結點陣列
int deep[N];//結點深度
bool inQueue[N];//是否進入過佇列
int queue[N];//佇列

void link(int x,int y){//建立雙向邊
	Edge * edge;
	edge = new Edge(y,head[x]);
	head[x] = edge;
	edge = new Edge(x,head[y]);
	head[y] = edge;
}

int main(){
	int n,m,s,t;
	cin >> n >> m >> s >> t;
	for(int i = 0,x,y;i < m;i++){//建邊
		cin >> x >> y;
		link(x,y);
	}
	
	int l = 1,r = 0;
	int k;
	
	queue[++r] = s;
	inQueue[s] = true;
	while(l <= r){//遍歷佇列
		k = queue[l++];
		if(k == t){//如果出隊元素為終點，則找到答案
			break;
		}
		for(Edge * edge = head[k];edge != NULL;edge = edge->next){//遍歷下一層結點
			if(inQueue[edge->vertex]){//如果該節點已經進入過佇列，跳過
				continue;
			}
			queue[++r] = edge->vertex;//結點入隊
			inQueue[edge->vertex] = true;
			deep[edge->vertex] = deep[k] + 1;//計算該節點深度
		}
	}
	cout << deep[t];
}

運行，結果如下：

往期博客

• 【資料結構基礎】資料結構基礎概念
• 【資料結構基礎】線性資料結構——線性表概念 及 陣列的封裝
• 【資料結構基礎】線性資料結構——三種鏈表的總結及封裝
• 【資料結構基礎】線性資料結構——堆疊和佇列的總結及封裝(C和java)
• 【演算法與資料結構基礎】模式匹配問題與KMP演算法
• 【資料結構與演算法基礎】二叉樹與其遍歷序列的互化 附代碼實作（C和java）
• 【資料結構與演算法拓展】 單調佇列原理及代碼實作
• 【資料結構基礎】圖的存盤結構
• 【資料結構與演算法基礎】并查集原理、封裝實作及例題決議（C和java）
• 【資料結構與演算法拓展】二叉堆原理、實作與例題（C和java）
• 【資料結構與演算法基礎】哈夫曼樹與哈夫曼編碼(C++)
• 【資料結構與演算法基礎】最短路徑問題
• 【資料結構與演算法基礎】堆排序原理及實作
• 【資料結構與演算法基礎】最小生成樹演算法原理及實作

參考資料：

• 《資料結構》（劉大有，楊博等編著）
• 《演算法導論》（托馬斯·科爾曼等編著）
• OI WiKi