?個人主頁：?熬夜學編程的小林

💗系列專欄：?【C語言詳解】?【數據結構詳解】【C++詳解】【Linux系統編程】【高階數據結構】

目錄

1、圖的存儲結構

1.1、鄰接表

1.1.1、邊的結構

1.1.2、圖的基本結構

1.1.3、圖的創建

1.1.4、獲取頂點下標

1.1.5、添加邊

1.1.6、打印

1.1.7、測試一

1.1.8、測試二

2、圖的遍歷

2.1、圖的廣度優先遍歷

2.2、圖的深度優先遍歷?

---

1、圖的存儲結構

1.1、鄰接表

鄰接表：使用數組表示頂點的集合，使用鏈表表示邊的關系。

1. 無向圖鄰接表存儲?

注意：無向圖中同一條邊在鄰接表中出現了兩次。如果想知道頂點vi的度，只需要知道頂點vi邊鏈表集合中結點的數目即可。?

2. 有向圖鄰接表存儲

注意：有向圖中每條邊在鄰接表中只出現一次，與頂點vi對應的鄰接表所含結點的個數，就是該頂點的出度，也稱出度表，要得到vi頂點的入度，必須檢測其他所有頂點對應的邊鏈表，看有多少邊頂點的dst取值是i。?

1.1.1、邊的結構

1、鄰接表使用鏈表來存儲邊之間的關系，因此成員需要next指針，除此之外還需要起始點(此處可以省略，因為使用目標點即可實現圖)，目標點，權值。

2、此處還需要實現一個有參構造函數，參數包括目標點下標和權值。

3、權值需要使用類型模板參數。

template<class W>
struct Edge
{// int _srci; // 起始點，入邊使用int _dsti;    // 目標點下標，出邊使用W _w;        // 權值Edge<W>* _next;Edge(size_t dsti, const W& w):_dsti(dsti),_w(w),_next(nullptr){}
};

1.1.2、圖的基本結構

1、使用鄰接表存儲圖的基本結構與使用鄰接矩陣存儲圖的基本結構類似，鄰接表同樣的使用模板實現，但是無需表示無窮大的非類型模板參數，因為此處為鏈表結構，添加邊的時候才需要new新的結點。

2、成員變量包括頂點集合，頂點與下標的映射關系和領接表。

template<class V, class W, bool Direction = false>
class Graph
{typedef Edge<W> Edge;
public:// ...
private:vector<V> _vertexs;     // 頂點集合map<V, int> _vIndexMap; // 頂點映射下標vector<Edge*> _tables;  // 鄰接表
};

1.1.3、圖的創建

圖的創建與鄰接矩陣一樣，使用手動添加邊的方式創建，即實現一個有參構造(參數包含定帶你集合以及頂點個數)。

Graph(const V* a, size_t n)
{_vertexs.reserve(n);for (size_t i = 0; i < n; i++){_vertexs.push_back(a[i]);_vIndexMap[a[i]] = i;}_tables.resize(n, nullptr);
}

注意：此處的鄰接表只需開辟一層空間，因為當添加邊的時候，我們會new新的結點。

1.1.4、獲取頂點下標

頂點與下標的映射存儲在map中，獲取頂點對應的下標只需要在map中進行查找即可，找到則返回下標，沒找到則拋異常(為了編譯通過，返回-1)。

// 根據頂點獲取下標
size_t GetVertexIndex(const V& v)
{auto it = _vIndexMap.find(v);if (it != _vIndexMap.end()){return it->second;}else{throw invalid_argument("頂點不存在");return -1;}
}

1.1.5、添加邊

1、參數為起始頂點，結束頂點和權值，還需注意有向與無向圖。

2、添加邊的思想，先獲取頂點對應的下標，然后將新的結點頭插到鄰接表中，如果是無向圖則需雙向存儲。

void AddEdge(const V& src, const V& dst, const W& w)
{size_t srci = GetVertexIndex(src);size_t dsti = GetVertexIndex(dst);// 1 -> 2 Edge* eg = new Edge(dsti, w);// 將Edge頭插到鄰接表eg->_next = _tables[srci];_tables[srci] = eg;// 無向圖 2 -> 1if (Direction == false){Edge* eg = new Edge(srci, w);// 將Edge頭插到鄰接表eg->_next = _tables[dsti];_tables[dsti] = eg;}
}

1.1.6、打印

打印的方式可以根據自己需求打印，此處打印下標與頂點的映射關系和鄰接表，為了讓打印更美觀，將鄰接表打印成? ?頂點[下標]->[頂點，下標，權值]...? 的形式。

void Print()
{// 頂點 下標 -> 頂點值for (size_t i = 0; i < _vertexs.size(); i++){cout << "[" << i << "]->" << _vertexs[i] << endl;}cout << endl;// 鄰接表for (size_t i = 0; i < _tables.size(); i++){// 頂點[下標]->[頂點，下標，權值]...cout << _vertexs[i] << "[" << i << "]->";Edge* cur = _tables[i];while (cur){cout << "[" << _vertexs[cur->_dsti] << "," << cur->_dsti << "," << cur->_w << "]->";cur = cur->_next;}cout << "nullptr" << endl;}
}

1.1.7、測試一

頂點值為char類型。

void TestGraph1()
{Graph<char, int, 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();
}

構造函數?

添加邊

打印結果

1.1.8、測試二

頂點值為string類型。

測試代碼?

void TestGraph2()
{string a[] = { "張三", "李四", "王五", "趙六" };Graph<string, int, true> g1(a, 4);g1.AddEdge("張三", "李四", 100);g1.AddEdge("張三", "王五", 200);g1.AddEdge("王五", "趙六", 30);g1.Print();
}

打印結果?

2、圖的遍歷

注意：此處的遍歷操作都是基于鄰接矩陣進行遍歷的。

給定一個圖G和其中任意一個頂點v0，從v0出發，沿著圖中各邊訪問圖中的所有頂點，且每個頂點僅被遍歷一次。"遍歷"即對結點進行某種操作的意思。

2.1、圖的廣度優先遍歷

如何防止節點被重復遍歷？

我們可以創建一個標記容器，成員類型為bool類型，訪問過則將值設置為true，默認為false。?

廣度優先遍歷思想：

與二叉樹的層序遍歷類似，需要借助隊列，先將第一個值入隊列，出隊列的同時把鄰接頂點入隊，直到隊列為空則遍歷結束，具體步驟如下：

• 1、獲取頂點對應的下標
• 2、創建隊列和標記容器
• 3、入隊
• 4、隊列不為空則遍歷
  • 4.1、打印隊頭
  • 4.2、將front的鄰接頂點入隊
    • 有效邊且標志位為false則入隊

遍歷代碼?

// 根據頂點進行廣度優先遍歷，使用隊列+標記容器
void BFS(const V& src)
{// 1.獲取頂點對應的下標size_t srci = GetVertexIndex(src);// 2.創建隊列和標記容器queue<int> q;vector<bool> visited(_vertexs.size(),false); // 默認false可以訪問// 3.入隊q.push(srci);visited[srci] = true; // 不能訪問size_t n = _vertexs.size();// 4.隊列不為空則遍歷while (!q.empty()){// 打印隊頭int front = q.front();q.pop();cout << front << ":" << _vertexs[front] << endl;// 將front的鄰接頂點入隊for (size_t i = 0; i < n; i++){// 有效邊且標志位為false則入隊if (_matrix[front][i] != MAX_W && !visited[i]){q.push(i);visited[i] = true;}}}cout << endl;
}

測試代碼

void TestBDFS()
{string a[] = { "張三", "李四", "王五", "趙六", "周七" };Graph<string, int> g1(a, sizeof(a) / sizeof(string));g1.AddEdge("張三", "李四", 100);g1.AddEdge("張三", "王五", 200);g1.AddEdge("王五", "趙六", 30);g1.AddEdge("王五", "周七", 30);g1.Print();g1.BFS("張三");
}

結構及打印結果

遍歷結果

上面確實實現了廣度優先遍歷，但是能不能像二叉樹的層序遍歷一樣，打印每一層呢？

可以的。

與二叉樹打印每一層類型，我們可以創建一個記錄隊列元素個數的變量，一次打印隊列元素個數個，打印完一層之后更新這個值。

一層層打印?

// 廣度優先遍歷(一層層打印)
void BFS(const V& src)
{// 1.獲取頂點對應的下標size_t srci = GetVertexIndex(src);// 2.創建隊列和標記容器queue<int> q;vector<bool> visited(_vertexs.size(), false); // 默認false可以訪問// 3.入隊q.push(srci);visited[srci] = true; // 不能訪問int levelSize = 1;size_t n = _vertexs.size();// 4.隊列不為空則遍歷while (!q.empty()){// 一層層打印，一次打印隊列個數個for (int i = 0; i < levelSize; i++){// 打印隊頭int front = q.front();q.pop();cout << front << ":" << _vertexs[front] << endl;// 將front的鄰接頂點入隊for (size_t i = 0; i < n; i++){// 有效邊且標志位為false則入隊if (_matrix[front][i] != MAX_W && !visited[i]){q.push(i);visited[i] = true;}}}cout << endl;levelSize = q.size();}
}

遍歷結果?

2.2、圖的深度優先遍歷?

深度優先遍歷思想：?

與二叉樹的前序遍歷類似，但是此處需要使用標記容器，因此需要實現一個子函數，具體步驟如下：

• 1、獲取頂點對應的下標
• 2、創建標記容器
• 3、調用子函數

子函數思想：

• 1、打印該位置的值并將該位置的標記位設置為true(不能再訪問)
• 2、找一個該位置相鄰的且沒有訪問過的點深度遍歷

代碼實現?

void _DFS(size_t srci, vector<bool>& visited)
{// 下標:頂點值cout << srci << ":" << _vertexs[srci] << endl;visited[srci] = true; // 不能再訪問// 找一個scri相鄰的且沒有訪問過的點，深度遍歷for (size_t i = 0; i < _vertexs.size(); i++){if (_matrix[srci][i] != MAX_W && !visited[i]){_DFS(i, visited);}}
}
void DFS(const V& src)
{size_t srci = GetVertexIndex(src);vector<bool> visited(_vertexs.size(), false);_DFS(srci, visited);
}

運行結果