第六章學習小結

? ? ? 本章學習了圖的結構及應用，

? ? ? 首先是圖的分類，圖分為無向圖、有向圖、完全圖、連通圖、強連通圖、帶權圖、稀疏圖、稠密圖等等。

? ? ? 圖的存儲方式有兩大類，以邊集合方式的表示法和以鏈接方式的表示法。其中，以邊集合方式表示的為鄰接矩陣（借助二維數組來表示元素之間的關系，實現較為簡單），以鏈接方式表示的包括鄰接表、十字鏈表和鄰接多重表（屬于鏈式存儲結構，實現較為復雜）。

? ? ? 接下來是圖的遍歷算法，圖的遍歷算法有兩種，包括深度優先搜索遍歷和廣度優先搜索遍歷。

? ? ? 深度優先搜索遍歷類似于樹的先序遍歷，借助于棧結構來實現。

void DFS(Graph a,int b) //深度優先搜索 
  {visited[b]=true;    //令頂點對應的visited數組為true，表示該頂點已被訪問過 cout<<b<<" ";   //輸出頂點編號及空格 for(int i=0;i<a.vexnum;i++){if(a.arcs[b][i]==1 && visited[i]==false)DFS(a,i);   //若頂點對應的鄰接點未被訪問，則遞歸調用DFS函數 
      }}

? ? ? 廣度優先搜索遍歷類似于樹的層次遍歷，借助隊列結構來實現。

void BFS(Graph a,int b) //廣度優先搜索 
 {int temp;   //定義參數 while(!q.empty())   //若隊列不為空 
      {temp=q.front(); //取隊頭元素值為temp q.pop();    //隊頭元素出隊 
               cout<<temp<<" ";    //輸出temp值及空格 for(int i=0;i<a.vexnum;i++){if(a.arcs[temp][i]==1 && visited[i]==false) //若頂點對應的鄰接點未被訪問，則鄰接點入隊 
             {q.push(i);  //鄰接點入隊 visited[i]=true;    //鄰接點對應的visited數組取true，表示已被訪問 
             }}visited[b]=true;    //第一次入隊的頂點對應的visited數組值取true，表示已被訪問
     }}

? ? ? 然后是圖的應用，比較常用的包括構造最小生成樹算法、求解最短路徑算法

? ? ? 構造最小生成樹的算法有普里姆算法和克魯卡斯算法，其中

? ? ? 普里姆算法的核心是歸并點，時間復雜度是O(n²)，適用于稠密網

? ? ? 克魯斯卡爾算法是歸并變，時間復雜度是O(elog₂e），適用于稀疏網。

? ? ? 最短路徑算法包括迪杰斯特拉算法和弗洛伊德算法，其中

? ? ? 迪杰斯拉特算法是求從某個源點到其余各頂點的最短路徑，按路徑長度遞增的次序產生最短路徑，時間復雜度為O(n²)

? ? ? 弗洛伊德算法是求每一對頂點之間的最短路徑，時間復雜度為O(n³)

? ? ? 個人感覺圖這一章概念很多，算法也很多，要多花時間看書，弄懂書上的概念和算法。

?