[TOC]

写在前面

本篇文章整理《数据结构（C++语言版）》关于二叉树这种线性结构知识点。
整个数据结构部分章节列表如下:
1 向量
2 列表
3 栈
4 队列
5 二叉树
6 图

6 图

6.1 图的描述

比较特殊的两种图
（1）欧拉环路：经过所有的边有且仅有一次的环路。
（2）哈密尔顿环路经过所有点有且仅有一次的环路。

欧拉环路与哈密尔顿环路
邻接矩阵与关联矩阵
图可以通过矩阵形式进行描述。
（1）邻接矩阵：描述顶点之间相互邻接关系。（n x n格式，n个顶点）
（2）关联矩阵：描述顶点与边之间的关联关系。（n x e格式，n个顶点，e条边）
邻接矩阵示例

6.2 图结构的实现

图结构接口定义代码如下

template <typename Tv, typename Te>
class Graph {  
private:
  void reset() {  //所有顶点，边的辅助信息复位
    for (int i = 0; i < n; i++) {  //顶点
      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:  /*...顶点操作、边操作，图算法
}

6.2.1 顶点类型的实现

代码如下

typedef enum { UNDISCOVERED, DISCOVERED, VISITED } VStatus;

template <typename Tv> 
struct Vertex {  //顶点对象（并未严格封装）
  Tv data; int inDegree, outDegree;  //数据、出入度
  VStatus status;  //（如上三种）状态
  int dTime, fTime;  //时间标签
  int parent;  //在遍历树中的父节点
  int priority;  //在遍历树中的优先级（最短通路，极短跨边等）
  Vertex(Tv const & d):  //构造函数，初始化列表，构造新顶点
      data(d), inDegree(0), outDegree(0), status(UNDISCOVERED),
      dTime(-1), fTime(-1), parent(-1), priority(INT_MAX) {}
}

TIPS:关于typedef与define
1.使用方式
宏定义： #difine int_PTR int * //将int * 用int_PTR代替
typedef： typedef int * int_ptr //将int * 用int_ptr代替
2.编译处理
宏定义是预处理指令，在编译预处理时进行简单的替换，不做正确性检查；typedef是在编译时处理的。
const int_ptr p; //相当于const int * p,把指针锁住，即p不能改变，但其指向的内容可变
const int_PTR p; //仅仅将其替换掉，相当于const( int * p)，把指针指向对象锁住，即p指向的内容不能改变

6.2.2 边类型的实现

代码如下

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

template <typename Te>
struct Edge {  //边对象（并未严格封装）
  Te data;  //数据
  int weight;  //权重
  EStatus status;  //类型
  Edge(Te const& d, int w) :  //构造函数，初始化列表，构造新边
      data(d), weigth(w), status(UNDETERMINED) {}
}

6.2.3 基于邻接矩阵实现图结构

首先将顶点集与边集兑现为对应的数据结构。
对于边集而言，这里套用了两层Vector结构，继承了Vector中重载的[ ]操作符用法。第一层，将以某个顶点为中心的所有关联边整合（行向量），随后再整合为列向量。因而E[i] [j]即为邻接矩阵。

顶点集与边集
代码如下

template<typename Tv, typename Te>
class GraphMatrix : public Graph<Tv, Te> {
private:
  Vector< Vertex<Tv> > V;  //顶点集
  Vector< Vector< Edge<Te>* > > E;  //边集
public:
/*...操作接口...*/
  GraphMatrix() {n = e = 0; }
  ~GraphMatrix() {  //析构
    for (int j=0; j<n; j++)
      for (int k=0;k<n;k++)
        //基于Vector模板类，可以调用Vecotr封装的[ ]寻秩操作符
        delete E[j] [k];  //清除所有动态申请的边记录
  }
}

6.3 相关算法

6.3.1 顶点操作

1.枚举当前顶点所有邻接顶点
即从当前顶点i开始，依次判断其余顶点j与顶点i之间是否有关联边（i, j）存在。

int nextNbr(int i, int j) {  //若已枚举至邻居j，则转向下一个邻居
  while( (-1 < j) && !exits(i, --j) );  //逆序查找
  return j;
}

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

2.顶点插入
插入一个新顶点，需要对邻接矩阵进行扩充。①表示增加每个顶点到新顶点的边集合（初始化为NULL）②表示新顶点到每个顶点的边集合（初始化为NULL）③④表示对边集合与顶点集合扩充。

顶点插入

int insert(Tv const & vertex){   //插入顶点，返回编号
  for(int j = 0; j < n; j++) E[j].insert(NULL);  //①
  n++;  //增大矩阵列数
  E.insert( Vector< Edge<Te>* >(n, n, NULL) );  //②③
  return V.insert( Vertex<Tv> (vertex) );  //④
}

3.顶点删除

Tv remove(int i) {  //删除顶点及其关联边，返回该顶点信息
  for(int j = 0; j < n; j++)  {//删除关联矩阵中第i行（删除所有出边）
    if (exists(i, j)) {  
      delete E[i][j];
      V[j].inDegree--;
    }
  }
  E.remove(i);  //删除第i行
  for(int j = 0; j < n; j++)  {//删除关联矩阵第i列（删除所有入边）
    if (exists(j, i)) {
      delete E[j][i];
      V[j].outDegree--;
    }
  } 
  Tv vBak = vertex(i);  //备份顶点i的信息
  V.remove(i);
  return vBak;
}

6.3.2 广度优先遍历

以当前顶点为中心，遍历其所有邻接点。再以每个邻接点为中心，遍历其所有尚未访问的邻接点。该算法的实现与树的层次遍历类似，或者说，树的层次遍历是图的广度优先遍历的一种特殊情况。
具体算法中，每个顶点共设置三种状态{UNDISCOVERED, DISCOVERED, VISITED}分别表示未被发现、被发现、被访问，每条边共设置三种状态{UNDETERMINED, CROSS, TREE}分别表示未被发现、被访问、不访问。

BFS算法实现示意图

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;  //取出队首顶点v
    for(int u = firstNbr(v); -1 < u; u = nextNbr(v, u)) {  //找寻当前顶点v的邻接点u
      if(UNDISCOVERED == status(u)) { //若u未被发现
        status(u) = DISCOVERED; Q.enqueue(u);  //发现该节点并入队
        status(v, u) = TREE; parent(u) =v;  //访问该关联边
      } else //若u已被发现（已入队）或已被访问
        status(v, u) = CROSS;  //设置该关联边为不访问状态
    }
    status(v) = VISITED;
  }
}

变式：若该图中包含不只一个连通域的情形，采用BFS搜索，只需逐一检查每个顶点，若状态为UNDISCOVERED，则对当前顶点启动BFS搜索。

多连通域情况

6.3.3 深度优先遍历

起始于顶点s，在其未被访问的邻接点中任选其一，递归执行。
设父节点为v，其递归执行的子节点u。
①若u的邻接节点s状态为UNDISCOVERED，则继续递归执行；

①

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

②若状态为DISCOVERED（表明该节点s已置入遍历树中），则将边（u，s）设置为BACKWARD（该边不置入遍历树），回退到其父节点u；

②

③若状态为VISITED，则比较节点u与节点s的发现时间（dTime）标签。若u标签更小，即u更早被发现，则标记边（u，s）为FORWARD；否则，标记为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尚未发现，支撑数可在u点进行拓展
        status(v, u) = TREE; parent(u) =v; DFS(u, clock); break;  //在u点递归
      case DISCOVERED:  //u已被发现
        status(v, u) = BACKWARD; break;
      default:  //u已访问完毕
        status(v, u) = dTime(v) < dTime(u) ? FORWARD : CROSS; break;
  }
  status(v) = VISITED; fTime(v) = ++clock;  //记录节点访问完毕的时钟
}

嵌套引理
1.顶点活动期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无亲缘关系。

嵌套引理