數據結構與算法——淺析圖科技頭條網

數據結構與算法——淺析圖

2020-03-10 09:26:55 sandag

圖的元素叫作頂點，頂點間的連接關係叫做

邊，跟頂點相連的邊的條數稱為 頂點的度

圖根據是否有方向可分為 有向圖 和 無向圖 ，有向圖的邊有方向，度也分為入度 (指向頂點的邊的個數)和出度 (頂點指向的邊的個數)

有權重的圖稱為 帶權圖 ，也就是邊有權值

用圖展示下(左上無權無向圖、右上無權有向圖、左下有權無向圖、右下有權有向圖)：

存儲方式

圖的存儲方式有兩種，一種是 鄰接矩陣 ，另一種是 鄰接表

鄰接矩陣實質是n×n的二維數組 ， m[i][j] 在無權無向圖中代表是否連接， m[i][j] 在無權有向圖中代表i是否單向連接j， m[i][j] 在有權無向圖中代表是否i和j的連接權重， m[i][j] 在有權有向圖中代表i單向連接j的權重

優點是存儲方式簡單，查詢高效，缺點是當點多邊少時，鄰接矩陣易造成內存空間浪費，以有向有權圖為例：

鄰接表實質就是一組動態數組(或鏈表、紅黑樹、跳錶、散列表等)，優點是內存佔用少，缺點就是查詢相比鄰接矩陣低(有序動態數組可以二分查找，紅黑樹、跳錶、散列表相比鏈表也快很多)，以有向有權圖用鄰接表(鏈表形式)為例：

拓撲排序

讓有向無環圖中所有頂點排成一個 線性序列

，使圖中任意一對頂點u和v，若點u到v連通，都滿足在線性序列中u位於v前。有兩種實現方法，分別是 Kahn算法 和 DFS

它可用於檢測 圖中是否存在環 、還可以通過 局部順序來推導全局順序 (比如用於處理編譯文件的依賴項)

Kahn算法

實質上是貪心算法。如果某個頂點 入度為 0 ，就表示沒有任何頂點必須先於這個頂點執行，那麼這個頂點就可以執行了。

因此我們先從圖中找出一個入度為 0 的頂點並輸出，然後把這個頂點從圖中刪除（把這個頂點可達的頂點的入度都減 1）。循環執行上面的過程直到所有的頂點都被輸出

偽代碼：

<code>void Kahn() {
  for (int i = 0; i < v; ++i) {
    for (int j = 0; j < vec[i].size(); ++j) { 

      int w = vec[i][j]; //說明存在i->w
      num[w]++;\t\t\t//統計節點的入度
    }
  }
  //先把入度為0的節點加入隊列
  for (int i = 0; i < v; ++i) {
    if (num[i] == 0) queue.push(i);
  }
  //循環執行：輸出入度為0的節點，並把該節點指向的節點入度--，若指向節點入度變為0則加入隊列
  while (!queue.isEmpty()) {
    int i = queue.pop();
    printf("->%d", i);
    for (int j = 0; j < vec[i].size(); ++j) {
      int k = vec[i][j];
      num[k]--;
      if (num[k] == 0) queue.push(k);
    }
  }
}
複製代碼/<code>

DFS算法

先 通過鄰接表構造逆鄰接表 ，再 遞歸處理每個頂點 (對於一個頂點先輸出可達它的所有頂點，再輸出自己)

偽代碼：

<code>void Topology() {
  for (int i = 0; i < v; ++i) { // 通過鄰接表生成逆鄰接表
    for (int j = 0; j < vec[i].size(); ++j) {
      int w = vec[i][j]; // i->w
      vecRotate[w].push(i); // w->i
    } 

  }
  for (int i = 0; i < v; ++i) { // 深度優先遍歷圖
    if (visited[i] == false) {\t// 未標記走過的進行dfs
      visited[i] = true;\t
      dfs(i);
    }
  }
}

void dfs(int v) {
  for (int i = 0; i < vecRotate[v].size(); ++i) {
    int w = vecRotate[v][i];
    if (visited[w] == true) continue;\t//若指向v的節點w已經標記過就跳過
    visited[w] = true;\t\t\t\t\t//否則就標記先dfs輸出w
    dfs(w);
  }
  //先輸出可達它的所有頂點，再輸出自己
  printf("->%d", v);
}/<code>

單源最短路

用於求 一個頂點到一個頂點 的最短距離，最常見的算法為dijkstra算法，時間複雜度為O(E × logV)E為邊數，V為頂點個數，具體做法是：

用 v 數組記錄起點到每個點的距離 (初始化無窮大)，然後把起始頂點初始化為 0 並放入 優先級隊列

每次從優先級隊列取出 距離最小

的頂點p，若 p可直達q，且v[p]+p到q距離 < v[q] ，就更新 v[q]=v[p]+p到q距離，並把q加入到優先級隊列，重複該過程直到找到終止或隊空

除此之外， predecessor數組記錄每個頂點的前驅 ，用於 還原最短路徑 ； inqueue數組判定頂點是否已經在優先隊列中 ， 避免重複添加 ， m數組記錄相鄰節點+距離

具體流程圖：

偽代碼

<code>void dijkstra(int s, int t) { \t//獲取s->t的最短路徑
  //step1:先初始化s到所有節點的距離無窮大
  for (int i = 1; i <= n; i++) {
      v[i].id = i;
      v[i].dist = INF;
  }
  //step2：再將到s節點(它本身)的距離初始化為0，並加入到優先隊列
  v[s].dist = 0;
  queue.push(v[s]);
  inqueue[s] = true;
  //循環執行
  while (!queue.isEmpty()) {
    minVertex = queue.pop(); //從優先級隊列取出距離最小的頂點minVertex
    if (minVertex.id == t) break; \t// 找到終點直接跳出
    //查找所有與距離最小節點相連的頂點
    for (int i = 0; i < m[minVertex.id].size(); ++i) {
      int tempDist = m[minVertex.id][i].dist; 
      int e = m[minVertex.id][i].id;
      //若minVertex可直達e，且v[minVertex]+minVertex到e距離      if (minVertex.dist + tempDist < v[e].dist) {
        //就更新v[e]=v[minVertex]+minVertex到e距離
        v[e].dist = minVertex.dist + tempDist;
        predecessor[v[e].id] = minVertex.id;
        //並把e加入到優先級隊列(若e已經在優先隊列中，則直接修改)
        if (inqueue[v[e].id] == true) {
          queue.update(v[e].dist);      // 更新隊列中的 dist 值
        } else {
          queue.push(v[e]);
          inqueue[v[e].id] = true;
        }
      }
    } 

  }
  // 輸出最短路徑
  printf(s);
  print(s, t);
}
//根據前驅遞歸輸出路徑
void print(int s, int t) {
  if (s == t) return;
  print(s, predecessor[t]);
  printf("->%d", t);
}/<code>