文章目錄

• • 1 圖的基本概念
  • 2 圖的表示
  • • 2.1 鄰接列表
    • 2.2 鄰接矩陣
    • 2.3 鄰接列表和鄰接矩陣的對比分析
  • 3 圖的算法實現（鄰接表）
  • • 3.1 圖的初始化
    • 3.2 鄰接表的深度遍歷
    • 3.3 鄰接表的廣度遍歷
    • 3.4 圖的導航-最短路徑算法

1 圖的基本概念

在計算機科學中，一個圖就是一些頂點的集合，這些頂點通過一系列邊結對（連接）。頂點用圓圈表示，邊就是這些圓圈之間的連線。頂點之間通過邊連接。注意：頂點有時也稱為節點或者交點，邊有時也稱為鏈接。

社交網絡，每一個人就是一個頂點，互相認識的人之間通過邊聯系在一起, 邊表示彼此的關系。這種關系可以是單向的，也可以是雙向的！

同時，邊可以是雙向的，也可以是單向的！

地圖導航 - 起點、終點和分叉口（包括十字路口·、T 字路口等）都是頂點，導航經過的兩頂點的路徑就是邊！

如上圖所示，我們導航從一個點到另外一個點可以有條路徑，路徑不同，路況就不同，擁堵程度不同，所以導致不同路徑所花的時間也不一樣，這種不同我們可以使用邊的權重來表示，即根據每條邊的實際情況給每一條邊分配一個正數或者負數值。考慮如下機票圖，各個城市就是頂點，航線就是邊。那么權重就是機票價格。

我們前面講解的樹和鏈表都是圖的特例！

如果我們有一個編程問題可以通過頂點和邊表示，那么我們就可以將你的問題用圖畫出來，然后使用相應的圖算法來找到解決方案。

---

2 圖的表示

2.1 鄰接列表

在鄰接列表實現中，每一個頂點會存儲一個從它這里開始的相鄰邊的列表。比如，如果頂點 B 有一條邊到 A、C 和 E，那么 B 的列表中會有 3 條邊。

鄰接列表只描述指向外部的邊。B 有一條邊到 A，但是 A 沒有邊到 B，所以B沒有出現在 A 的鄰接列表中。查找兩個頂點之間的邊或者權重會比較費時，因為遍歷鄰接列表直到找到為止。

2.2 鄰接矩陣

由二維數組對應的行和列都表示頂點，由兩個頂點所決定的矩陣對應元素數值表示這里兩個頂點是否相連（如，0 表示不相連，非 0 表示相連和權值）、如果相連這個值表示的是相連邊的權重。例如，廣西到北京的機票，我們用鄰接矩陣表示：

往這個圖中添加頂點的成本非常昂貴，因為新的矩陣結果必須重新按照新的行/列創建，然后將已有的數據復制到新的矩陣中。

2.3 鄰接列表和鄰接矩陣的對比分析

鄰接列表和鄰接矩陣我們該如何選擇呢？

結論：大多數時候，選擇鄰接列表是正確的。（在圖比較稀疏的情況下，每一個頂點都只會和少數幾個頂點相連，這種情況下鄰接列表是最佳選擇。如果這個圖比較密集，每一個頂點都和大多數其他頂點相連，那么鄰接矩陣更合適。)

---

3 圖的算法實現（鄰接表）

3.1 圖的初始化

鄰接表結構的定義：

#define MaxSize 1024typedef struct _EdgeNode {//與節點連接的邊的定義int adjvex; //鄰接的頂點int weight; //權重struct _EdgeNode *next; //下一條邊 }EdgeNode;typedef struct _VertexNode{//頂點節點char data; //節點數據struct _EdgeNode *first;//指向鄰接第一條邊 }VertexNode, AdjList;typedef struct _AdjListGraph {AdjList *adjlist;int vex; //頂點數int edge; //邊數 }AdjListGraph;

鄰接表的初始化：

/*圖的初始化*/ void Init(AdjListGraph &G){G.adjlist = new AdjList[MaxSize];G.edge = 0;G.vex = 0; }

鄰接表的創建：

/*圖的創建*/ void Create(AdjListGraph &G){cout << "請輸入該圖的頂點數以及邊數：" << endl;cin>> G.vex >> G.edge;cout<<"請輸入相關頂點："<< endl;for(int i=0; i<G.vex; i++){cin >> G.adjlist[i].data;G.adjlist[i].first = NULL;}char v1=0, v2=0;//保存輸入的頂點的字符int i1, i2; //保存頂點在數組中的下標cout<<"請輸入想關聯邊的頂點："<< endl;for(int i=0; i<G.edge; i++){cin >>v1 >>v2;i1 = Location(G, v1);i2 = Location(G, v2);if(i1!=-1 && i2!=-1){//尋找到位置EdgeNode *temp = new EdgeNode;temp->adjvex = i2;temp->next = G.adjlist[i1].first;G.adjlist[i1].first = temp;}} }/*通過頂點對應的字符尋找頂點在圖中的鄰接點*/ int Location(AdjListGraph &G, char c){for(int i=0; i<G.vex; i++){if(G.adjlist[i].data == c) {return i;}}return -1; }

3.2 鄰接表的深度遍歷

深度優先遍歷思想：

• 首先以一個未被訪問過的頂點作為起始頂點，沿當前頂點的邊走到未訪問過的頂點；
• 當沒有未訪問過的頂點時，則回到上一個頂點，繼續試探別的頂點，直到所有的頂點都被訪問過。

/*對圖上的頂點進行深度遍歷*/ void DFS(AdjListGraph &G,int v){int next = -1;if(visited[v]) return;out<<G.adjlist[v].data<<" ";visited[v] = true; //設置為已訪問EdgeNode *temp = G.adjlist[v].first;while(temp){next = temp->adjvex;temp = temp->next;if(visited[next] == false){DFS(G, next);}} }/*對所有頂點進行深度遍歷*/ void DFS_Main(AdjListGraph &G){for(int i=0; i<G.vex; i++){if(visited[i] == false){DFS(G, i);}} }int main(){AdjListGraph G;//初始化Init(G);//創建圖Create(G);//深度遍歷DFS_Main(G);system("pause"); }

3.3 鄰接表的廣度遍歷

廣度優先遍歷思想：

• 首先以一個未被訪問過的頂點作為起始頂點，訪問其所有相鄰的頂點;
• 然后對每個相鄰的頂點，再訪問它們相鄰的未被訪問過的頂點，直到所有頂點都被訪問過，遍歷結束。

/*對圖上的頂點進行廣度遍歷*/ void BFS(AdjListGraph &G,int v) {queue <int> q;int cur;int next;q.push(v);while (!q.empty()) { //隊列非空cur = q.front(); //取隊頭元素if (visited[cur] == false) { //當前頂點還沒有被訪問cout << G.adjlist[cur].data << " ";visited[cur] = true; //設置為已訪問}q.pop(); //出隊列EdgeNode *tp = G.adjlist[cur].first;while (tp != NULL) {next = tp->adjvex;tp = tp->next;q.push(next); //將第一個鄰接點入隊}} }/*對所有頂點進行廣度遍歷*/ void BFS_Main(AdjListGraph &G) {for (int i = 0; i < G.vex; i++) {if (visited[i] == false) {BFS(G,i);}} }

3.4 圖的導航-最短路徑算法

從起點開始訪問所有路徑，則到達終點節點的路徑有多條，其中路徑權值最短的一條則為最短路徑。最短路徑算法有深度優先遍歷、廣度優先遍歷、Bellman-Ford 算法、弗洛伊德算法、 SPFA(Shortest Path Faster Algorithm)算法和迪杰斯特拉算法等。

如下給出深度優先遍歷求最短路徑的算法：

int min_weights = 0x7FFFFFFF; //最大的整數 2 的 32 次方-1 int steps = 0; int path[MaxSize] = {0};//保存走過的路徑 int shortest_path[MaxSize] = {0}; //保存最短的路徑/*對圖上的頂點進行深度遍歷*/ void DFS(AdjListGraph &G,int start, int end, int weights){int cur = -1;//if(visited[start]) return;cur = start;if(cur == end){//已找到終點，不用繼續遍歷//打印所經過的所有路徑for (int i = 0; i < steps; i++) /// 輸出所有可能的路徑{cout<<G.adjlist[path[i]].data<<" "; //輸出路徑}printf("\t\t 該路徑對應的長度是：%d\n",weights);//輸出對應路徑長度if (min_weights > weights) //更新最小路徑{min_weights = weights;memcpy(shortest_path, path, steps*sizeof(int));}}visited[start] = true; //設置為已訪問EdgeNode *temp = G.adjlist[start].first;while(temp){int weight = temp->weight;cur = temp->adjvex;if(visited[cur] == false){visited[cur] = true; //標記城市 i 已經在路徑中path[steps++] = cur;//保存路徑到 path 數組中DFS(G, cur, end, weights + weight);visited[cur] = false;// 之前一步探索完畢后,取消對城市 i 的標記以便另一條路徑選擇頂點path[--steps] = 0;}temp = temp->next;} }

---

參考資料：

C/C++從入門到精通-高級程序員之路【奇牛學院】

總結

以上是生活随笔為你收集整理的图的原理及算法实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。