不知上期各位讀者思考得怎么樣了，這期的文章是接上一期的，
本文的主要內容為：圖的C++代碼實作 (鄰接矩陣法)，主要為各個類的具體實作
圖的抽象基類
1 // FilenName: Graph.cpp 2 3 #include "Graph.h" 4 5 const int CGraph::UNVISITED = 0; 6 const int CGraph::VISITED = 1; 7 8 CGraph::CGraph(int numVertex) { 9 this->numVertex = numVertex; 10 this->numEdge = 0; 11 this->mark = new int[this->numVertex]; 12 this->inDegree = new int[this->numVertex]; 13 14 for(int i = 0; i < this->numVertex; i++){ 15 this->mark[i] = CGraph::UNVISITED; 16 this->inDegree[i] = 0; 17 } 18 } 19 20 CGraph::~CGraph() { 21 delete[] this->mark; 22 delete[] this->inDegree; 23 } 24 25 int CGraph::GetVerticesNum() { 26 return this->numVertex; 27 } 28 29 int CGraph::GetEdgesNum() { 30 return this->numEdge; 31 } 32 33 int CGraph::GetFromVertex(CEdge oneEdge) { 34 return oneEdge.from; 35 } 36 37 int CGraph::GetToVertex(CEdge oneEdge) { 38 return oneEdge.to; 39 } 40 41 int CGraph::GetWeight(CEdge oneEdge) { 42 return oneEdge.weight; 43 } 44 45 bool CGraph::IsEdge(CEdge oneEdge) { 46 return (oneEdge.from >= 0 && oneEdge.to >=0 && oneEdge.weight >= 0); 47 } 48 49 void CGraph::ResetMark() { 50 for(int i = 0; i < this->numVertex; i++){ 51 this->mark[i] = CGraph::UNVISITED; 52 } 53 }
圖的鄰接矩陣實作類
1 // FileName: GraphAdjacentMatrix.cpp 2 // Author: SihanLin 3 4 #include "GraphAdjacentMatrix.h" 5 #include <queue> 6 using namespace std; 7 8 /********************************************** 9 * 函式功能：建構式，動態分配鄰接矩陣二維陣列， 10 * 呼叫者無需釋放，解構式會自動釋放 11 * @param: 12 * numVertex: 圖的頂點數目 13 * @return: 14 * 無 15 *********************************************/ 16 CGraphM::CGraphM(int numVertex) : CGraph(numVertex) { 17 this->matrix = (int**) new int*[this->numVertex]; 18 for(int i = 0; i < numVertex; i++){ 19 this->matrix[i] = new int[this->numVertex]; 20 } 21 22 for(int i = 0; i < numVertex; i++){ 23 for(int j = 0; j < numVertex; j++){ 24 this->matrix[i][j] = 0; 25 } 26 } 27 } 28 29 30 /************************************************ 31 * 函式功能：解構式，釋放動態分配的鄰接矩陣二維陣列 32 * @param: 33 * Null 34 * @return: 35 * 無 36 ***********************************************/ 37 CGraphM::~CGraphM() { 38 for(int i = 0; i < this->numVertex; i++){ 39 delete [] this->matrix[i]; 40 } 41 delete [] this->matrix; 42 } 43 44 45 /********************************************** 46 * 函式功能：洗掉邊 47 * @param: 48 * from: 邊的起點 49 * to: 邊的終點 50 * @return: 51 * void 52 *********************************************/ 53 void CGraphM::delEdge(int from, int to) { 54 if(from == to){ 55 this->matrix[from][to] = 0; 56 } 57 else{ 58 this->matrix[from][to] = -1; 59 } 60 } 61 62 /********************************************** 63 * 函式功能：設定邊 64 * @param: 65 * from: 邊的起點 66 * to: 邊的終點 67 * weight：邊的權值 68 * @return: 69 * void 70 *********************************************/ 71 void CGraphM::SetEdge(int from, int to, int weight) { 72 if(from == to){ 73 this->matrix[from][to] = 0; 74 } 75 else{ 76 this->matrix[from][to] = weight; 77 } 78 } 79 80 /********************************************** 81 * 函式功能：獲取以引數 oneVertex 為起點的第一條邊 82 * @param: 83 * oneVertex: 邊的起點 84 * @return: 85 * 邊類物件 86 *********************************************/ 87 CEdge CGraphM::FirstEdge(int oneVertex) { 88 CEdge resultEdge; // 函式回傳值 89 resultEdge.from = oneVertex; // 起點 90 91 for(int i = 0; i < this->numVertex; i++){ 92 if(this->matrix[resultEdge.from][i] > 0){ 93 resultEdge.to = i; 94 resultEdge.weight = this->matrix[resultEdge.from][i]; 95 break; 96 } 97 } 98 return resultEdge; 99 } 100 101 /********************************************** 102 * 函式功能：獲取和引數 perEdge 同起點的下一條邊 103 * @param: 104 * preEdge： 上一條邊 105 * @return: 106 * 邊類物件 107 *********************************************/ 108 CEdge CGraphM::NextEdge(CEdge preEdge) { 109 CEdge resultEdge; // 函式回傳值 110 resultEdge.from = preEdge.from; // 起點 111 if(preEdge.to < this->numVertex - 1){ // 如果上一條邊的終點 小于 頂點的個數減1 則存在下一條邊 112 for(int i = preEdge.to + 1; i < this->numVertex; i++){ 113 if(this->matrix[preEdge.from][i] > 0){ 114 resultEdge.to = i; 115 resultEdge.weight = this->matrix[preEdge.from][i]; 116 break; 117 } 118 } 119 } 120 return resultEdge; 121 } 122 123 /********************************************** 124 * 函式功能：初始化圖 125 * @param: 126 * pWArray2D: 二維鄰接矩陣的一維指標 127 * @return: 128 * void 129 *********************************************/ 130 void CGraphM::InitGraphM(int *pWArray2D) { 131 int N = this->numVertex; 132 int array_i_j = 0; 133 134 for(int i = 0; i < N; i++){ 135 for(int j = 0; j < N; j++){ 136 array_i_j = *(pWArray2D + i * N + j); // 用一維陣列的方式訪問二維陣列 *(起點地址 + 行數 * 總行數 + 列數) 137 if(array_i_j > 0){ 138 this->SetEdge(i, j, array_i_j); 139 } 140 } 141 } 142 } 143 144 /********************************************** 145 * 函式功能：深度優先搜索 146 * @param: 147 * oneVertex: 開始搜索的起點 148 * @return: 149 * void 150 *********************************************/ 151 void CGraphM::DFS(int oneVertex) { 152 this->mark[oneVertex] = CGraph::VISITED; 153 this->Visit(oneVertex); 154 155 for(CEdge edge = this->FirstEdge(oneVertex); this->IsEdge(edge); edge = this->NextEdge(edge)){ 156 if(this->mark[edge.to] == CGraph::UNVISITED){ 157 this->DFS(edge.to); 158 } 159 } 160 } 161 162 /********************************************** 163 * 函式功能：廣度優先搜索 164 * @param: 165 * oneVertex: 開始搜索的起點 166 * @return: 167 * void 168 *********************************************/ 169 void CGraphM::BFS(int oneVertex) { 170 queue<int> queueEdge; 171 this->Visit(oneVertex); 172 this->mark[oneVertex] = CGraph::VISITED; 173 queueEdge.push(oneVertex); 174 175 while(!queueEdge.empty()){ 176 int u = queueEdge.front(); 177 queueEdge.pop(); 178 for(CEdge edge = this->FirstEdge(oneVertex); this->IsEdge(edge); edge = this->NextEdge(edge)){ 179 if(this->mark[edge.to] == CGraph::UNVISITED){ 180 this->Visit(edge.to); 181 this->mark[edge.to] = CGraph::VISITED; 182 queueEdge.push(edge.to); 183 } 184 } 185 } 186 } 187 188 189 /********************************************** 190 * 函式功能：訪問頂點 191 * @param: 192 * oneVertex: 要訪問的頂點 193 * @return: 194 * void 195 *********************************************/ 196 void CGraphM::Visit(int oneVertex) { 197 cout << "C" << oneVertex << " "; 198 } 199 200 201 /********************************************** 202 * 函式功能：圖的周游介面合并 203 * @param: 204 * startVertex: 開始周游的起點 205 * travelType: 周游型別 206 * travelType = 0: DFS 207 * travelType = 1: BFS 208 * @return: 209 * void 210 *********************************************/ 211 void CGraphM::Travel(int startVertex, int travelType) { 212 for(int i = startVertex, n = 0; n < this->numVertex; i++, n++){ 213 i %= this->numVertex; 214 if(this->mark[i] == CGraph::UNVISITED){ 215 switch(travelType){ 216 case 0: 217 this->DFS(i); 218 break; 219 case 1: 220 this->BFS(i); 221 break; 222 default: 223 cout << "Error: travelType must be in [0, 1]" << endl; 224 break; 225 } 226 } 227 } 228 }
以上就是圖的鄰接矩陣的具體的實作方法，
有不懂之處，歡迎各位讀者留言評論交流，
有不足之處，希望各位讀者多多包涵，也希望讀者們能留言評論指出我的不足，十分感謝！
下期預告：利用圖實作：拓撲排序演算法，最小路徑演算法，最小生成樹演算法，敬請期待，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/232844.html
標籤：C++