[TOC]

寫(xiě)在前面

本篇文章整理《數(shù)據(jù)結(jié)構(gòu)（C++語(yǔ)言版）》關(guān)于二叉樹(shù)這種線性結(jié)構(gòu)知識(shí)點(diǎn)。
整個(gè)數(shù)據(jù)結(jié)構(gòu)部分章節(jié)列表如下:
1 向量
2 列表
3 棧
4 隊(duì)列
5 二叉樹(shù)
6 圖

6 圖

6.1 圖的描述

比較特殊的兩種圖
（1）歐拉環(huán)路：經(jīng)過(guò)所有的邊有且僅有一次的環(huán)路。
（2）哈密爾頓環(huán)路經(jīng)過(guò)所有點(diǎn)有且僅有一次的環(huán)路。

歐拉環(huán)路與哈密爾頓環(huán)路

鄰接矩陣示例

6.2 圖結(jié)構(gòu)的實(shí)現(xiàn)

圖結(jié)構(gòu)接口定義代碼如下

template <typename Tv, typename Te>
class Graph {  
private:
  void reset() {  //所有頂點(diǎn)，邊的輔助信息復(fù)位
    for (int i = 0; i < n; i++) {  //頂點(diǎn)
      status(i) = UNDISCOVERED; dTime(i) = fTime(i) = -1;
      parent(i) = -1; priority(i) = INT_MAX;
      for (int j = 0; j < n; j++)   //邊
        if (exists(i, j)) status(i, j) = UNDETERMINED;
    }
  }
public:  /*...頂點(diǎn)操作、邊操作，圖算法
}

6.2.1 頂點(diǎn)類型的實(shí)現(xiàn)

代碼如下

typedef enum { UNDISCOVERED, DISCOVERED, VISITED } VStatus;

template <typename Tv> 
struct Vertex {  //頂點(diǎn)對(duì)象（并未嚴(yán)格封裝）
  Tv data; int inDegree, outDegree;  //數(shù)據(jù)、出入度
  VStatus status;  //（如上三種）狀態(tài)
  int dTime, fTime;  //時(shí)間標(biāo)簽
  int parent;  //在遍歷樹(shù)中的父節(jié)點(diǎn)
  int priority;  //在遍歷樹(shù)中的優(yōu)先級(jí)（最短通路，極短跨邊等）
  Vertex(Tv const & d):  //構(gòu)造函數(shù)，初始化列表，構(gòu)造新頂點(diǎn)
      data(d), inDegree(0), outDegree(0), status(UNDISCOVERED),
      dTime(-1), fTime(-1), parent(-1), priority(INT_MAX) {}
}

TIPS:關(guān)于typedef與define
1.使用方式
宏定義： #difine int_PTR int * //將int * 用int_PTR代替
typedef： typedef int * int_ptr //將int * 用int_ptr代替
2.編譯處理
宏定義是預(yù)處理指令，在編譯預(yù)處理時(shí)進(jìn)行簡(jiǎn)單的替換，不做正確性檢查；typedef是在編譯時(shí)處理的。
const int_ptr p; //相當(dāng)于const int * p,把指針鎖住，即p不能改變，但其指向的內(nèi)容可變
const int_PTR p; //僅僅將其替換掉，相當(dāng)于const( int * p)，把指針指向?qū)ο箧i住，即p指向的內(nèi)容不能改變

6.2.2 邊類型的實(shí)現(xiàn)

代碼如下

typedef enum{UNDETERMINED, TREE, CROSS, FORWARD， BACKWARD} EStatus;

template <typename Te>
struct Edge {  //邊對(duì)象（并未嚴(yán)格封裝）
  Te data;  //數(shù)據(jù)
  int weight;  //權(quán)重
  EStatus status;  //類型
  Edge(Te const& d, int w) :  //構(gòu)造函數(shù)，初始化列表，構(gòu)造新邊
      data(d), weigth(w), status(UNDETERMINED) {}
}

6.2.3 基于鄰接矩陣實(shí)現(xiàn)圖結(jié)構(gòu)

首先將頂點(diǎn)集與邊集兌現(xiàn)為對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)。
對(duì)于邊集而言，這里套用了兩層Vector結(jié)構(gòu)，繼承了Vector中重載的[ ]操作符用法。第一層，將以某個(gè)頂點(diǎn)為中心的所有關(guān)聯(lián)邊整合（行向量），隨后再整合為列向量。因而E[i] [j]即為鄰接矩陣。

頂點(diǎn)集與邊集

template<typename Tv, typename Te>
class GraphMatrix : public Graph<Tv, Te> {
private:
  Vector< Vertex<Tv> > V;  //頂點(diǎn)集
  Vector< Vector< Edge<Te>* > > E;  //邊集
public:
/*...操作接口...*/
  GraphMatrix() {n = e = 0; }
  ~GraphMatrix() {  //析構(gòu)
    for (int j=0; j<n; j++)
      for (int k=0;k<n;k++)
        //基于Vector模板類，可以調(diào)用Vecotr封裝的[ ]尋秩操作符
        delete E[j] [k];  //清除所有動(dòng)態(tài)申請(qǐng)的邊記錄
  }
}

6.3 相關(guān)算法

6.3.1 頂點(diǎn)操作

1.枚舉當(dāng)前頂點(diǎn)所有鄰接頂點(diǎn)
即從當(dāng)前頂點(diǎn)i開(kāi)始，依次判斷其余頂點(diǎn)j與頂點(diǎn)i之間是否有關(guān)聯(lián)邊（i, j）存在。

int nextNbr(int i, int j) {  //若已枚舉至鄰居j，則轉(zhuǎn)向下一個(gè)鄰居
  while( (-1 < j) && !exits(i, --j) );  //逆序查找
  return j;
}

int firstNbr(int i){
  return nextNbr(i, n);
}

2.頂點(diǎn)插入
插入一個(gè)新頂點(diǎn)，需要對(duì)鄰接矩陣進(jìn)行擴(kuò)充。①表示增加每個(gè)頂點(diǎn)到新頂點(diǎn)的邊集合（初始化為NULL）②表示新頂點(diǎn)到每個(gè)頂點(diǎn)的邊集合（初始化為NULL）③④表示對(duì)邊集合與頂點(diǎn)集合擴(kuò)充。

頂點(diǎn)插入

int insert(Tv const & vertex){   //插入頂點(diǎn)，返回編號(hào)
  for(int j = 0; j < n; j++) E[j].insert(NULL);  //①
  n++;  //增大矩陣列數(shù)
  E.insert( Vector< Edge<Te>* >(n, n, NULL) );  //②③
  return V.insert( Vertex<Tv> (vertex) );  //④
}

3.頂點(diǎn)刪除

Tv remove(int i) {  //刪除頂點(diǎn)及其關(guān)聯(lián)邊，返回該頂點(diǎn)信息
  for(int j = 0; j < n; j++)  {//刪除關(guān)聯(lián)矩陣中第i行（刪除所有出邊）
    if (exists(i, j)) {  
      delete E[i][j];
      V[j].inDegree--;
    }
  }
  E.remove(i);  //刪除第i行
  for(int j = 0; j < n; j++)  {//刪除關(guān)聯(lián)矩陣第i列（刪除所有入邊）
    if (exists(j, i)) {
      delete E[j][i];
      V[j].outDegree--;
    }
  } 
  Tv vBak = vertex(i);  //備份頂點(diǎn)i的信息
  V.remove(i);
  return vBak;
}

6.3.2 廣度優(yōu)先遍歷

以當(dāng)前頂點(diǎn)為中心，遍歷其所有鄰接點(diǎn)。再以每個(gè)鄰接點(diǎn)為中心，遍歷其所有尚未訪問(wèn)的鄰接點(diǎn)。該算法的實(shí)現(xiàn)與樹(shù)的層次遍歷類似，或者說(shuō)，樹(shù)的層次遍歷是圖的廣度優(yōu)先遍歷的一種特殊情況。
具體算法中，每個(gè)頂點(diǎn)共設(shè)置三種狀態(tài){UNDISCOVERED, DISCOVERED, VISITED}分別表示未被發(fā)現(xiàn)、被發(fā)現(xiàn)、被訪問(wèn)，每條邊共設(shè)置三種狀態(tài){UNDETERMINED, CROSS, TREE}分別表示未被發(fā)現(xiàn)、被訪問(wèn)、不訪問(wèn)。

BFS算法實(shí)現(xiàn)示意圖

template <typename Tv, typename Te>
void Graph<Tv, Te>::BFS(int v, int & clock){
  Queue<int> Q; status(v) = DISCOVERED; Q.enqueue(v);
  while( !Q.empty() ) {
    int v = Q.dequeue();
    dTime(v) = ++clock;  //取出隊(duì)首頂點(diǎn)v
    for(int u = firstNbr(v); -1 < u; u = nextNbr(v, u)) {  //找尋當(dāng)前頂點(diǎn)v的鄰接點(diǎn)u
      if(UNDISCOVERED == status(u)) { //若u未被發(fā)現(xiàn)
        status(u) = DISCOVERED; Q.enqueue(u);  //發(fā)現(xiàn)該節(jié)點(diǎn)并入隊(duì)
        status(v, u) = TREE; parent(u) =v;  //訪問(wèn)該關(guān)聯(lián)邊
      } else //若u已被發(fā)現(xiàn)（已入隊(duì)）或已被訪問(wèn)
        status(v, u) = CROSS;  //設(shè)置該關(guān)聯(lián)邊為不訪問(wèn)狀態(tài)
    }
    status(v) = VISITED;
  }
}

變式：若該圖中包含不只一個(gè)連通域的情形，采用BFS搜索，只需逐一檢查每個(gè)頂點(diǎn)，若狀態(tài)為UNDISCOVERED，則對(duì)當(dāng)前頂點(diǎn)啟動(dòng)BFS搜索。

多連通域情況

6.3.3 深度優(yōu)先遍歷

起始于頂點(diǎn)s，在其未被訪問(wèn)的鄰接點(diǎn)中任選其一，遞歸執(zhí)行。
設(shè)父節(jié)點(diǎn)為v，其遞歸執(zhí)行的子節(jié)點(diǎn)u。
①若u的鄰接節(jié)點(diǎn)s狀態(tài)為UNDISCOVERED，則繼續(xù)遞歸執(zhí)行；

①

j的鄰居包含g么？？？？？？？？？

②若狀態(tài)為DISCOVERED（表明該節(jié)點(diǎn)s已置入遍歷樹(shù)中），則將邊（u，s）設(shè)置為BACKWARD（該邊不置入遍歷樹(shù)），回退到其父節(jié)點(diǎn)u；

②

③若狀態(tài)為VISITED，則比較節(jié)點(diǎn)u與節(jié)點(diǎn)s的發(fā)現(xiàn)時(shí)間（dTime）標(biāo)簽。若u標(biāo)簽更小，即u更早被發(fā)現(xiàn)，則標(biāo)記邊（u，s）為FORWARD；否則，標(biāo)記為CROSS。

③

代碼如下

template<typename Tv, typename Te>
void Graph<Tv, Te>::DFS(int v, int & clock) {
  dTime(v) = ++clock; status(v) = DISCOVERED;
  for(int u = firstNbr(v); -1 < u; u = nextNbr(v, u)) {
    switch( status(u) ) {
      case UNDISCOVERED:  //u尚未發(fā)現(xiàn)，支撐數(shù)可在u點(diǎn)進(jìn)行拓展
        status(v, u) = TREE; parent(u) =v; DFS(u, clock); break;  //在u點(diǎn)遞歸
      case DISCOVERED:  //u已被發(fā)現(xiàn)
        status(v, u) = BACKWARD; break;
      default:  //u已訪問(wèn)完畢
        status(v, u) = dTime(v) < dTime(u) ? FORWARD : CROSS; break;
  }
  status(v) = VISITED; fTime(v) = ++clock;  //記錄節(jié)點(diǎn)訪問(wèn)完畢的時(shí)鐘
}

嵌套引理
1.頂點(diǎn)活動(dòng)期active[u] = ( dTime[u], fTime[u] )
2.給定有向圖G=（V, E）及其任一DFS森林，則
active[u] ? active[v]，則u是v的后代；
active[u] ? active[v]，則u是v的祖先；
active[u] ∩ active[v] = ?，則u與v無(wú)親緣關(guān)系。

嵌套引理