天天看點
傳回

資料結構——圖

  • ​​圖​​
  • ​​圖的名詞和術語​​
  • ​​圖的存儲結構​​
  • ​​圖的鄰接矩陣表示​​
  • ​​無向圖的鄰接矩陣表示​​
  • ​​有向圖的鄰接矩陣表示​​
  • ​​網（即有權圖）的鄰接矩陣表示​​
  • ​​鄰接矩陣的存儲表示​​
  • ​​采用鄰接矩陣表示法構造無向網算法​​
  • ​​鄰接矩陣表示法的特點​​
  • ​​圖的鄰接表表示​​
  • ​​無向圖的鄰接表​​
  • ​​有向圖的鄰接表​​
  • ​​圖的鄰接表存儲表示​​
  • ​​采用鄰接表表示法構造有向圖​​
  • ​​采用鄰接表表示法構造無向圖​​
  • ​​鄰接表表示法的特點​​
  • ​​鄰接矩陣與鄰接表表示法的關系​​
  • ​​十字連結清單——用于有向圖​​
  • ​​無向圖的鄰接多重表存儲表示​​
  • ​​圖的周遊​​
  • ​​深度優先搜尋（DFS —— Depth_First Search）​​
  • ​​簡單分析​​
  • ​​詳細歸納​​
  • ​​圖的深度優先搜尋算法​​
  • ​​連通圖​​
  • ​​非連通圖​​
  • ​​鄰接矩陣表示圖的深度優先搜尋周遊​​
  • ​​鄰接表表示圖的深度優先搜尋周遊​​
  • ​​DFS算法效率分析​​
  • ​​廣度優先搜尋（BFS － Breadth_First Search）​​
  • ​​簡單分析​​
  • ​​算法思想​​
  • ​​圖的廣序優先搜尋周遊算法​​
  • ​​連通圖​​
  • ​​非連通圖​​
  • ​​BFS算法效率分析​​
  • ​​DFS與BFS算法效率比較​​
  • ​​圖的應用​​
  • ​​最小生成樹​​
  • ​​最短路徑​​
  • ​​拓撲排序​​
  • ​​關鍵路徑​​

圖

  • 定義：Graph=(V,E)
  • V：頂點(資料元素)的有窮非空集合
  • E：邊的有窮集合

圖的名詞和術語

  • 頂點：圖中的資料元素。
  • 邊：若<v, w>E 必有<w, v>E, 則稱 (v,w) 為頂點 v 和頂點 w 之間存在一條邊。
  • 弧：若<v, w>E 是有方向的,則稱 <v, w>為頂點 v 和頂點 w 之間存在一條有向邊，也稱為弧。
  • 無向圖：由頂點集和邊集構成的圖。每條邊都是無方向的
  • 有向圖：由于“弧”是有方向的，是以稱由頂點集和弧集構成的圖為有向圖。、
  • 完全圖
  • 頂點：n，邊：e
  • 無向完全圖：含有 **e=n(n-1)/2 **條邊的無向圖
  • 有向完全圖：含有e=n(n-1)條弧的有向圖
    • 資料結構——圖
  • 稀疏圖：e<nlogn
  • 稠密圖：e>nlogn
  • 權：某些圖的邊具有與它相關的數
  • 網：邊/弧帶權的圖
    • 資料結構——圖

  • 鄰接點：假若頂點v 和頂點w 之間存在一條邊，

    則稱頂點v 和w 互為鄰接點

  • 頂點的度：與該頂點相關聯的邊的數目，記為TD(v)
  • 入度：以 v 為終點的有向邊的條數, 記作ID(v)
  • 出度：以 v 為始點的有向邊的條數, 記作OD(v)
度(TD)=出度(OD)+入度(ID)
  • 路徑：接續的邊構成的頂點序列。
  • 路徑長度：路徑上邊或弧的數目/權值之和。
  • 簡單路徑：除路徑起點和終點可以相同外，其餘頂點均不相同的路徑。
  • 簡單回路（簡單環）：除路徑起點和終點相同外，其餘頂點均不相同的路徑。
    • 資料結構——圖
  • 連通圖
  • 無向圖
  • 圖G中任意兩個頂點之間都有路徑相通
  • 連通分量：若無向圖為非連通圖，則圖中各個極大連通子圖稱作此圖的連通分量。
極大連通子圖意思是：該子圖是 G 連通子圖，将G 的任何不在該子圖中的頂點加入，子圖不再連通。
  • 有向圖
  • 強連通圖：任意兩個頂點之間都存在一條有向路徑
  • 強連通分量：極大強連通子圖
資料結構——圖
  • 極小連通子圖： 該子圖是G 的連通子圖，在該子圖中删除任何一條邊，子圖不再連通。（n個頂點，n-1條邊）
  • 生成樹：包含無向圖G 所有頂點的極小連通子圖。
  • 生成森林：對非連通圖，由各個連通分量的生成樹的集合。
    • 資料結構——圖

圖的存儲結構

圖的鄰接矩陣表示

設圖 A = (V, E) 有 n 個頂點，則圖的鄰接矩陣是一個二維數組 A.Edge[n][n]，定義為：

資料結構——圖

無向圖的鄰接矩陣表示

資料結構——圖
  • 無向圖的鄰接矩陣是對稱的, 可壓縮存儲（上/下）三角。
  • 頂點i 的度＝第 i 行 (列) 中1的個數；
  • 矩陣中1的個數的一半為圖中邊的數目
  • 很容易判斷頂點Vi 和頂點Vj之間是否有邊相連(看矩陣中i行j列值是否為1)
  • 頂點不變，在圖中增加（删除）邊：隻需對二維數組對應分量指派1（清0）
完全圖的鄰接矩陣中，對角元素為0，其餘1。

有向圖的鄰接矩陣表示

資料結構——圖

在有向圖的鄰接矩陣中，

第i行含義：以結點vi為尾的弧(即出度邊）；

第i列含義：以結點vi為頭的弧(即入度邊）。

  • 有向圖的鄰接矩陣可能是不對稱的。
  • 頂點的出度=第i行元素之和
  • 頂點的入度=第i列元素之和
  • 頂點的度=第i行元素之和+第i列元素之和
  • 很容易判斷頂點Vi 和頂點Vj 是否有弧相連
  • 頂點不變，在圖中增加（删除）邊：隻需對二維數組對應分量指派1（清0）

網（即有權圖）的鄰接矩陣表示

資料結構——圖

鄰接矩陣的存儲表示 

#define// 定義一個無窮數
#define// 最大頂點數

// 圖類型枚舉定義{有向圖，有向網，無向圖，無向網}
typedef enum {DG, DN, UDG, UDN} GraphKind;

typedef struct ArcCell{// 邊定義
  VRType adj;  // VRType是頂點關系類型。
    // 對無權圖，用1或0表示相鄰否；
    // 對帶權圖（網絡），則為權值類型。
  InfoType* info;  // 該弧相關資訊指針
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]

typedef struct { // 圖的定義
  // 頂點資訊
  VertexType vexs[MAX_VERTEX_NUM];  // 頂點向量
  AdjMatrix arcs;  // 鄰接矩陣
  int vexnum, arcnum;  // 頂點數量和邊的數量
  GraphKind kind;  // 圖的種類标志
} MGraph;

采用鄰接矩陣表示法構造無向網算法 

/*---------------采用鄰接矩陣建立無向網絡---------------*/
// 算法思路
// 1. 輸入總頂點數和總邊數。
// 2. 依次輸入點的資訊存入頂點表中。
// 3. 初始化鄰接矩陣，使每個權值初始化為極大值。
// 4. 構造鄰接矩陣。 
void CreateUDN(MGraph &G){
  cin >> G.vexnum >> G.arcnum;  // 輸入頂點數和邊數
  for(int i = 0; i < G.vexnum; i++){
    // 建立頂點表
    G.vexs[i] = new char[10];
    cin >> G.vexs[i];  // 讀入頂點資訊
  }
  for(int i = 0; i < G.vexnum; i++)
    // 鄰接矩陣初始化
    for(j = 0; j < G.vexnum; j++){
      G.arcs[i][j].adj = INFINITY;
      G.arcs[i][j].info = NULL;
    }
  for(k = 0; k < G.arcnum; k++){
    v1 = new char[10];
    v2 = new char[10];
    cin >> v1 >> v2 >> w;  // 讀入e條邊上的權
    i = LocateVex_MG(G, v1);  // 查找頂點v1在圖中的位置
    j = LocateVex_MG(G, v2);
    G.arcs[i][j].adj = w;
    G.arcs[j][i].adj = w;
    delete v1;
    delete v2;
  }
}

int LocateVex_MG(MGraph G, VertexType x){
  // 查找頂點x在圖中的位置
  for(int k = 0; strcmp(G.vexs[k], x); k++);
  return k;
}

鄰接矩陣表示法的特點

  • 優點：容易實作圖的操作，如：求某頂點的度、判斷頂點之間是否有邊、找頂點的鄰接點等等。
  • 缺點：n個頂點需要n*n個單元存儲邊;空間效率為O(n^2)。對稀疏圖而言尤其浪費空間。

圖的鄰接表表示

  • 對每個頂點vi 建立一個單連結清單，把與vi有關聯的邊的資訊連結起來，每個結點設為3個域；
  • 一部分是單連結清單，用來存放邊/弧的資訊
  • 另一部分是數組，主要用來存放頂點本身的資料資訊
    • 資料結構——圖

無向圖的鄰接表

  • 同一個頂點發出的邊連結在同一個邊連結清單中，每一個鍊結點代表一條邊(邊結點）。
    • 資料結構——圖
鄰接表不唯一，因各個邊結點的鍊入順序是任意的
  • 空間效率為O(n+2e)，若是稀疏圖(e<<n^2), 比鄰接矩陣表示法O(n^2)省空間
  • 所有連結清單中邊結點數目的一半為圖中邊數
TD(Vi)=單連結清單中連結的結點個數

有向圖的鄰接表

資料結構——圖
  • 空間效率:O(n+e)
  • 出度：OD(Vi)＝單鍊出邊表中連結的結點數
  • 入度：ID(Vi)＝鄰接點域為Vi的弧個數
  • 度：TD(Vi) = OD( Vi ) + I D( Vi )

圖的鄰接表存儲表示 

typedef struct ArcNode{
  // 邊結點定義
  int adjvex;  // 該弧所指向的頂點的位置
  struct ArcNode* nextarc;  // 指向下一條弧的指針
  InfoType* info;  // 該弧相關資訊的指針
} ArcNode;

typedef struct VNode{
  // 頂點的結點定義
  // 表頭結點
  VertexType data;  // 頂點資訊
  ArcNode* firstarc;  // 指向第一條附屬該頂點的弧
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct{
  // 圖結構定義
  AdjList vertices;  // 圖的頂點結構數組
  int vexnum, arcnum;  // 頂點數和邊數
  int kind;
} ALGraph;

采用鄰接表表示法構造有向圖 

/*------------采用鄰接表表示法構造有向圖------------*/
void GreateDG_ALG(ALGraph &G){
  // 構造有向圖
  cin >> G.vexnum >> G.arcnum;
  for(i = 0; i < G.vexnum; i++){
    // 建立頂點表
    G.vertices[i].data = new char[10];
    cin >> G.vertices[i].data;  // 讀入頂點資訊
    G.vertices[i].firstarc = NULL;
  }
  for(k = 0; k < G.arcnum; k++){
    // 建立邊表
    v1 = new char[10]; 
    v2 = new char[10];
    cin >> v1 >> v2;
    i = LocateVex_ALG(G, v1);  // 弧尾
    j = LocateVex_ALG(G, v2);  // 弧頭
    p = new ArcNode;
    p->adjvex = j;
    p->nextarc = G.vertices[i].firstarc;
    p->info = NULL;
    G.vertices[i].firstarc = p;  // 前插
  }
}

采用鄰接表表示法構造無向圖 

/*------------采用鄰接表表示法構造無向圖------------*/
void CreateUDG(ALGraph &G){
  cin >> G.vexnum >> G.arcnum;  // 輸入總頂點數，總邊數
  for(i = 0; i < G.vexnum; i++){
    // 輸入各點，構造表頭結點表
    cin >> G.vertices[i].data;  // 輸入頂點值
    G.vertices[i].firstarc = NULL;  // 初始化表頭結點的指針域為NULL
  }
  for(k = 0; k < G.arcnum; ++k){
    // 輸入各邊，構造鄰接表
    cin >> v1 >> v2;  // 輸入一條邊依附的兩個頂點
    i = LocateVex(G, v1);
    j = LocateVex(G, v2);
    p1 = new ArcNode;  // 生成一個新的邊結點*p1 
    p1->adjvex = j;  // 鄰接點序号為j
    // 将新結點*p1插入頂點vi的邊表頭部
    p1->nextarc = G.vertices[i].firstarc;
    G.vertices[i].firstarc = p1;
    p2 = new ArcNode;  // 生成另一個對稱的新的邊結點*p2
    p2->adjvex = i;
    // 将新結點*p2插入頂點vj的邊表頭部 
    p2->nextarc = G.vertices[j].firstarc;
    G.vertices[j].firstarc = p2;
  }
}

鄰接表表示法的特點

  • 優點：空間效率高，容易尋找頂點的鄰接點
  • 缺點：判斷兩頂點間是否有邊或弧，需搜尋兩結點對應的單連結清單，沒有鄰接矩陣友善

鄰接矩陣與鄰接表表示法的關系

資料結構——圖
  • 聯系：鄰接表中每個連結清單對應于鄰接矩陣中的一行，連結清單中結點個數等于一行中非零元素的個數。
  • 差別
  • 對于任一确定的無向圖，鄰接矩陣是唯一的（行列号與頂點編号一緻），但鄰接表不唯一（連結次序與頂點編号無關）。
  • 鄰接矩陣的空間複雜度為O(n*2), 而鄰接表的空間複雜度為O(n+e)。
  • 用途：鄰接矩陣多用于稠密圖；而鄰接表多用于稀疏圖

十字連結清單——用于有向圖

  • 結點表中的結點的表示
    • 資料結構——圖
  • data：結點的資料域，儲存結點的資料值。
  • firstin：結點的指針域，給出自該結點出發的的第一條邊的邊結點的位址。
  • firstout：結點的指針場，給出進入該結點的第一條邊的邊結點的位址。
  • 邊結點表中的結點的表示
    • 資料結構——圖
  • info：邊結點的資料域，儲存邊的權值等。
  • tailvex：本條邊的出發結點的位址。
  • headvex：本條邊的終止結點的位址。
  • hlink：終止結點相同的邊中的下一條邊的位址。
  • tlink：出發結點相同的邊中的下一條邊的位址。 
typedef struct ArcBox{
  // 弧結點結構表示
  int tailvex, headvex;
  InfoType* info;
  struct ArcBox* hlink,* tlink;
} ArcBox;

typedef struct VexNode{
  // 頂點的結構表示
  VertexType data;
  ArcBox* firstin,* firstout;
} VexNode;

typedef struct{
  // 有向圖的十字連結清單
  VexNode xlist[MAX_VERTEX_NUM];  // 頂點結點
  int vexnum, arcnum;  // 有向圖的目前頂點數和弧數
} OLGraph;

void CreatDG_OLG(OLGraph &G){
  // 構造有向圖
  cin >> G.vexnum >> G.arcnum;  // 頂點數，弧數
  for(i = 0; i < G.vexnum; i++){
    // 建立頂點表
    G.xlist[i].data = new char[10];
    cin >> G.xlist[i].data;  // 讀入頂點資訊
    G.xlist[i].firstin = NULL;
    G.xlist[i].firstout = NULL;
  }
  for(k = 0; k < G.arcnum; k++){
    // 建立十字連結清單
    v1 = new char[10];
    v2 = new char[10];
    i = LocateVex_OLG(G, v1);
    j = LocateVex_OLG(G, v2);
    p = new ArcBox;
    p->info = NULL;
    p->headvex = j;  // 弧的終點
    p->tailvex = i;  // 弧的起點
    p->hlink = G.xlist[j].firstin;  // 前插
    p->tlink = G.xlist[i].firstout;
    G.xlist[j].firstin = G.xlist[i].firstout = p;
  }
}

無向圖的鄰接多重表存儲表示

資料結構——圖
  • mark：标志域，标記該條邊是否被搜尋過
  • ivex、jvex：該邊依附的兩個頂點在圖中的位置
  • ilink：指向下一條依附于頂點ivex的邊
  • jlink：指向下一條依附于頂點jvex的邊
  • info：指向和邊相關的各種資訊的指針域
在圖的連結存儲(鄰接表、逆鄰接表、十字連結清單和鄰接多重表)中，表頭向量需要占用n個存儲單元，所有邊結點需要占用2e或e存儲單元，是以最多需要（n+2e）個存儲單元，稀疏圖采用這種存儲方式可節省存儲空間。

圖的周遊

  • 定義：從已給的連通圖中某一頂點出發，沿着一些邊訪遍圖中所有的頂點，且使每個頂點僅被通路一次，就叫做圖的周遊，它是圖的基本運算。
  • 周遊實質：找每個頂點的鄰接點的過程。
  • 圖的特點：圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在通路完某個頂點之後可能會沿着某些邊又回到了曾經通路過的頂點。
怎樣避免重複通路 ？
  • 解決思路：設定輔助數組 visited [n ]，用來标記每個被通路過的頂點。
  • 初始狀态為0
  • i 被通路，改 visited [i]為1，防止被多次通路

深度優先搜尋（DFS —— Depth_First Search）

基本思想：仿樹的先序周遊過程。
資料結構——圖

簡單分析

  • 通路起始點v;
  • 若v的第1個鄰接點沒通路過，深度周遊此鄰接點；
  • 若目前鄰接點已通路過，再找v的第2個鄰接點重新周遊。

詳細歸納

資料結構——圖
  • 在通路圖中某一起始頂點v後，由 v 出發，通路它的任一鄰接頂點 w1；
  • 再從 w1 出發，通路與 w1鄰接但還未被通路過的頂點 w2；
  • 然後再從 w2 出發，進行類似的通路，…
  • 如此進行下去，直至到達所有的鄰接頂點都被通路過的頂點 u 為止。
  • 接着，退回一步，退到前一次剛通路過的頂點，看是否還有其它沒有被通路的鄰接頂點。
  • 如果有，則通路此頂點，之後再從此頂點出發，進行與前述類似的通路；
  • 如果沒有，就再退回一步進行搜尋。重複上述過程，直到連通圖中所有頂點都被通路過為止。

圖的深度優先搜尋算法

連通圖 
int visited[MAX_VERTEX_NUM];  // 全局變量
void Visit(VertexType x){cout << x << " ";}

/*-----------圖的深度優先搜尋算法（連通圖）-----------*/
void DFS(Graph G, int v){
  Visit(v); 
  visited[v] = true;
  // FirstAdjVex(G, v) 表示v的第一個鄰接點
  // NextAdjVex(G, v, w) 表示v相對于w的下一個鄰接點
  // w >= 0 表示鄰接點存在
  for(w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
    if(!visited[w]) DFS(G, w);
}
非連通圖 
/*-----------圖的深度優先搜尋算法（非連通圖）-----------*/
void DFSTraverse(Graph G){
  for(v = 0; v < G.vexnum; ++v) visited[v] = false;  // 通路标志數初始化
  for(v = 0; v < G.vexnum; ++v)
    if(!visited[v]) DFS(G, v);
}

周遊圖的過程實質上是對每個頂點查找其鄰接點的過程。

若給定圖的存儲結構,則從某一頂點出發的周遊結果應是唯一的。

鄰接矩陣表示圖的深度優先搜尋周遊
資料結構——圖
/*-----------鄰接矩陣表示圖的深度優先搜尋周遊-----------*/
void DFS_AM(AMGraph G, int v){
  // 圖G為鄰接矩陣類型
  cout << v;
  // 通路第v個結點
  visited[v] = true;
  for(w = 0; w < G.vexnum; w++){
    // 一次檢查鄰接矩陣v所在行
    if((G.arcs[v][w] != 0) && (!visited[w]))
      DFS(G, w);
    // w是v的鄰接點，如果w未通路，則遞歸調用DFS
  }
}
鄰接表表示圖的深度優先搜尋周遊
資料結構——圖
/*-----------鄰接表表示圖的深度優先搜尋周遊-----------*/
void DFS_AL(ALGraph G, int v){
  // 圖G為鄰接表類型
  cout << v;
  visited[v] = true;  // 通路第v個頂點
  p = G.vertics[v].firstarc;  // p指向v的邊連結清單的第一個邊結點
  while(p != NULL){
    // 邊結點非空 
    w = p->adjvex;  //表示w是v的鄰接點
    if(!visited[w]) DFS(G, w);  // 如果w未通路，則遞歸調用DFS
      p = p->nextarc;  // p指向下一個邊結點
    }
}
DFS算法效率分析
  • 用鄰接矩陣來表示圖，周遊圖中每一個頂點都要從頭掃描該頂點所在行，時間複雜度為O(n^2)。
  • 用鄰接表來表示圖，雖然有2e個表結點，但隻需掃描e個結點即可完成周遊，加上通路n個頭結點的時間，時間複雜度為O(n+e)。

稠密圖适于在鄰接矩陣上進行深度周遊；

稀疏圖适于在鄰接表上進行深度周遊。

廣度優先搜尋（BFS － Breadth_First Search）

基本思想：仿樹的層次周遊過程
資料結構——圖

簡單分析

  • 在通路了起始點v之後，依次通路v的鄰接點；
  • 然後再依次通路這些頂點中未被通路過的鄰接點；
  • 直到所有頂點都被通路過為止。

廣度優先搜尋是一種分層的搜尋過程，每向前走一步可能通路一批頂點，不像深度優先搜尋那樣有回退的情況。

是以，廣度優先搜尋不是一個遞歸的過程，其算法也不是遞歸的。

算法思想

  • 從圖中某個頂點v出發，通路v，并置visited[v]的值為true，然後将v進隊。
  • 隻要隊列不空，則重複下述處理
  • 隊頭頂點u出隊
  • 依次檢查u的所有鄰接點w，如果visited[w]的值為false，則通路w，并置visited[w]的值為true，然後将w進隊

圖的廣序優先搜尋周遊算法

連通圖 
/*------------廣度優先非遞歸周遊連通圖G（連通圖）------------*/
void BFS(Graph G, int v){
  cout << v;
  visited[v] = true;  // 通路第v個頂點
  InitQueue(Q);
  EnQueue(Q, v);
  while(!QueueEmpty(Q)){
    DeQueue(Q, u);
    for(w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w)) 
      if(!visited[w]){
        // w為u的尚未通路的鄰接頂點
        cout << w;
        visited[w] = false;
        EnQueue(Q, w);  // w進隊
      }
  }
}
非連通圖 
/*------------廣度優先非遞歸周遊連通圖G（非連通圖）------------*/
void BFSTraverse(Graph G){
  for(v = 0; v < G.vexnum; ++v) visited[v] = false;  // 通路标志數初始化
  for(v = 0; v < G.vexnum; ++v)
    if(!visited[v]) BFS(G, v);
}

BFS算法效率分析

  • 如果使用鄰接矩陣，則BFS對于每一個被通路到的頂點，都要循環檢測矩陣中的整整一行（ n 個元素），總的時間代價為O(n^2)。
  • 用鄰接表來表示圖，雖然有 2e 個表結點，但隻需掃描 e 個結點即可完成周遊，加上通路 n個頭結點的時間，時間複雜度為O(n+e)。

DFS與BFS算法效率比較

  • 空間複雜度相同，都是O(n)(借用了堆棧或隊列）；
  • 時間複雜度隻與存儲結構（鄰接矩陣或鄰接表）有關，而與搜尋路徑無關。

圖的應用

​​最小生成樹​​

​​最短路徑​​

​​拓撲排序​​

​​關鍵路徑​​

圖 存儲結構 周遊 深度優先搜尋 廣度優先搜尋
上一篇: [鴻蒙開發]設定圖示和應用名稱
下一篇: 【資料結構+算法】——概覽篇

繼續閱讀