我們今天來看圖的遍歷，其實都是之前在二叉樹中提過的方法，深度和廣度遍歷。

在這之前，我們先用一個鄰接矩陣來表示一個圖：

#pragma once
#include<iostream>
#include<vector>
#include<map>
using namespace std;//圖的模板化
namespace matrix
{template<class V, class W, W MAX_W, bool Direction = false>class Graph{public:Graph(const V* vertex, size_t n){//開辟空間_vertex.reserve(n);for (int i = 0; i < n; i++){_vertex.push_back(vertex[i]);_index[vertex[i]] = i;}//初始化矩陣_matrix.resize(n);for (auto& e : _matrix){e.resize(n, MAX_W);}}//尋找圖中的點size_t FindSrci(const V& vertex){auto ret = _index.find(vertex);if (ret != _index.end()){return ret->second;}else{throw invalid_argument("不存在的頂點");return -1;}}void _AddEdge(size_t srci, size_t desi, W w){_matrix[srci][desi] = w;if (Direction == false){_matrix[desi][srci] = w;}}//加邊void AddEdge(const V& srci, const V& desi, W w){size_t srcIndex = FindSrci(srci);size_t desIndex = FindSrci(desi);_AddEdge(srcIndex, desIndex, w);}void Print(){//打印標題行cout << "      ";for (int i = 0; i < _vertex.size(); i++){cout << _vertex[i] << " ";}cout << endl;//打印矩陣for (int i = 0; i < _vertex.size(); i++){cout << _vertex[i] << " ";for (int j = 0; j < _matrix[i].size(); j++){if (_matrix[i][j] != MAX_W){printf("%5d", _matrix[i][j]);}else{printf("%5c", '#');}}cout << endl;}}private://存放頂點vector<V> _vertex;//映射關系map<V, size_t> _index;//矩陣，圖的表示vector<vector<W>> _matrix;};void TestGraph(){Graph<char, int, INT_MAX, true> g("0123", 4);g.AddEdge('0', '1', 1);g.AddEdge('0', '3', 4);g.AddEdge('1', '3', 2);g.AddEdge('1', '2', 9);g.AddEdge('2', '3', 8);g.AddEdge('2', '1', 5);g.AddEdge('2', '0', 3);g.AddEdge('3', '2', 6);g.Print();}void TestGraph2(){string a[] = {"海皇","高斯","小傲","小潮","胖迪","小楊","皖皖"};Graph<string, int,INT_MAX, false> g1(a, sizeof(a)/sizeof(a[0]));g1.AddEdge("小潮", "小傲", 30);g1.AddEdge("小潮", "高斯", 83);g1.AddEdge("小潮", "海皇", 34);g1.AddEdge("胖迪", "海皇", 78);g1.AddEdge("胖迪", "小傲", 76);g1.AddEdge("小楊", "皖皖", 54);g1.AddEdge("小楊", "高斯", 48);g1.Print();}
}

BFS（廣度遍歷）

廣度優先遍歷和之前二叉樹的廣度優先遍歷一樣，我們需要隊列來輔助：
我們邏輯上是這張圖，但是我們實際遍歷的時候，我們遍歷的是一個矩陣（二維數組）
因為這個圖是聯通圖，我們從任意一個頂點出發都可以遍歷完所有頂點，假設我們從小潮開始：
我們仿照二叉樹那里的思路，把相連的節點入隊列，把小傲，高斯，海皇入隊列：
在矩陣上的表現就是把小潮這一行，不為#的數值的結點入隊列：
好，現在有一個問題，假設我現在遍歷到了海皇，海皇和小潮相連，按照上面的規則，我們應該把小潮入隊列，但是我們一開始就是從小潮開始的，就會造成重復訪問，這該則么辦呢？

所以在圖這里，我們要引入一個數組，標記我們已經訪問過的結點，標記過的結點在之后的訪問過程中不再入隊：

我們來實現一下：

	void BFS(const V& vertex){int vertexIndex = FindSrci(vertex);//隊列和標記數組int n = _vertex.size();queue<size_t> q;vector<bool> visited(n, false);//先入最先訪問節點q.push(vertexIndex);//標記visited[vertexIndex] = true;while (!q.empty()){//出隊size_t front = q.front();q.pop();cout << _vertex[front] << " ";//遍歷該行for (int i = 0; i < _vertex.size(); i++){if (_matrix[front][i] != MAX_W){if (visited[i] == false){q.push(i);visited[i] = true;}}}cout << endl;}}

一道美團題

讀了題之后，這里讓我們計算幾度好友，其實我們在BFS已經按照一度二度的順序打印了，但是我們沒有區分，我們區分一下就可以了

void BFS(const V& vertex)
{// 獲取目標頂點的索引int vertexIndex = FindSrci(vertex);// 初始化隊列和標記數組int n = _vertex.size();queue<size_t> q; // 創建一個隊列用于存儲待訪問的頂點vector<bool> visited(n, false); // 創建一個布爾數組，用于標記頂點是否已被訪問// 將起始頂點添加到隊列中，并標記為已訪問q.push(vertexIndex);visited[vertexIndex] = true;int levelSize = 1; // 初始化當前層級的頂點數量，初始時只有起始頂點int degree = 0; // 初始化度數（即好友的層次）// 當隊列非空時，繼續廣度優先搜索while (!q.empty()){// 輸出當前度數的好友cout << "[" << degree << "]" << "度好友 ";// 對當前層級的所有頂點進行處理for (int j = 0; j < levelSize; j++){// 從隊列中取出一個頂點size_t front = q.front();q.pop();// 輸出當前頂點的信息cout << _vertex[front] << " ";// 遍歷與當前頂點相鄰的所有頂點for (int i = 0; i < _vertex.size(); i++){// 如果存在一條邊連接當前頂點和下一個頂點if (_matrix[front][i] != MAX_W){// 如果下一個頂點未被訪問過if (!visited[i]){// 將下一個頂點添加到隊列中，以便后續訪問q.push(i);// 標記下一個頂點為已訪問visited[i] = true;}}}}// 更新下一層級的頂點數量levelSize = q.size();// 換行輸出，準備進入下一度數的好友輸出cout << endl;// 增加度數計數器degree++;}// 最終換行，使輸出更清晰cout << endl;
}

DFS（深度遍歷）

深度遍歷是一條道走到黑：

// 深度優先搜索的私有輔助函數
void _DFS(size_t vertexIndex, vector<bool>& visited)
{// 如果當前頂點尚未訪問過if (!visited[vertexIndex]){// 輸出當前頂點的值cout << _vertex[vertexIndex] << endl;// 將當前頂點標記為已訪問visited[vertexIndex] = true;// 遍歷所有頂點for (size_t i = 0; i < _vertex.size(); i++){// 如果當前頂點和遍歷到的下一個頂點之間存在邊，// 表示為權重不是最大可能權重（MAX_W），// 則對下一個頂點進行深度優先搜索if (_matrix[vertexIndex][i] != MAX_W)_DFS(i, visited);}}
}// 公開的深度優先搜索函數，從給定的頂點開始
void DFS(const V& vertex)
{// 查找給定頂點在頂點列表中的索引size_t vertexIndex = FindSrci(vertex);// 初始化一個布爾向量來跟蹤每個頂點是否已被訪問vector<bool> visited(_vertex.size(), false);// 調用私有輔助函數進行深度優先搜索_DFS(vertexIndex, visited);
}

（注：本人是小潮院長粉絲，該文章中舉的例子不代表真實好友關系，無意挑撥小潮院長內部成員關系，如有冒犯，請不要打我…）