数据结构-6.图

写在前面

本篇文章整理《数据结构(C++语言版)》关于二叉树这种线性结构知识点。

图的描述

比较特殊的两种图
(1)欧拉环路:经过所有的边有且仅有一次的环路。
(2)哈密尔顿环路经过所有点有且仅有一次的环路。
欧拉环路与哈密尔顿环路
邻接矩阵与关联矩阵
图可以通过矩阵形式进行描述。
(1)邻接矩阵:描述顶点之间相互邻接关系。(n x n格式,n个顶点)
(2)关联矩阵:描述顶点与边之间的关联关系。(n x e格式,n个顶点,e条边)
邻接矩阵示例

图结构的实现

图结构接口定义代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
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: /*...顶点操作、边操作,图算法
}

顶点类型的实现

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
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指向的内容不能改变

边类型的实现

代码如下

1
2
3
4
5
6
7
8
9
10
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) {}
}

基于邻接矩阵实现图结构

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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]; //清除所有动态申请的边记录
}
}

相关算法

顶点操作

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

1
2
3
4
5
6
7
8
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)③④表示对边集合与顶点集合扩充。
顶点插入

1
2
3
4
5
6
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.顶点删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
}

广度优先遍历

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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搜索
多连通域情况

深度优先遍历

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

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

②若状态为DISCOVERED(表明该节点s已置入遍历树中),则将边(u,s)设置为BACKWARD(该边不置入遍历树),回退到其父节点u;
②

③若状态为VISITED,则比较节点u与节点s的发现时间(dTime)标签。若u标签更小,即u更早被发现,则标记边(u,s)为FORWARD;否则,标记为CROSS。
③
代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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无亲缘关系。
嵌套引理

本文标题:数据结构-6.图

文章作者:Lumo Wang

发布时间:2018年03月05日 - 14:03

最后更新:2018年11月07日 - 15:11

原始链接:https://luameows.github.io/2018/03/05/学习笔记-数据结构-6-图/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

请我喝杯咖啡,我会继续熬夜的~