数据结构与算法

前言

写在前面的话：数据结构与算法。

  1. 对于初识数据结构的小伙伴们，鉴于后面的数据结构的构建会使用到同tag前面的内容，包括具体数据结构的应用，所使用到的数据结构，也是自己构建的，未使用系统的库文件，因此，建议这类小伙伴们按顺序进行学习；

  2. 对于想查询有关资料的小伙伴们，可以选择性地浏览。希望大家都能有所收获～

图的三大搜索算法构建

上一章我们介绍了图的拓扑排序以及拓扑序列，本章我们来了解如何用代码去实现图的三大算法：

  1. 广度优先搜索算法

  2. 深度优先搜索算法

  3. 拓扑排序算法

我们先新建一个Graph.h，本章依然从构建一个完整的图的角度来编写代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
/*
 *
 * 作者：易果啥笔
 * 时间：2021.8.22
 * 内容：图的头文件
 *
 *
 */

#ifndef STACK_GRAPH_H
#define STACK_GRAPH_H
#define hca(x) (fTime(x)) 
#include "Stack.h"
#include "Queue.h"

using VStatus = enum { UNDISCOVERED, DISCOVERED, VISITED }; //顶点状态
using EType = enum { UNDETERMINED, TREE, CROSS, FORWARD, BACKWARD }; //边在遍历树中所属的类型

template <typename Tv, typename Te> //顶点类型、边类型
class Graph { //图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 ) ) type ( i, j ) = UNDETERMINED; //类型
                   }
        }
        void BFS(int,int&);
        void DFS(int,int&);
        bool TSort(int,int&,Stack<Tv>*);
     public:
        // 顶点
        int n; //顶点总数
        virtual int insert ( Tv const& ) = 0; //插入顶点，返回编号
        virtual Tv remove ( int ) = 0; //删除顶点及其关联边，返回该顶点信息
        virtual Tv& vertex ( int ) = 0; //顶点v的数据（该顶点的确存在）
        virtual int inDegree ( int ) = 0; //顶点v的入度（该顶点的确存在）
        virtual int outDegree ( int ) = 0; //顶点v的出度（该顶点的确存在）
        virtual int firstNbr ( int ) = 0; //顶点v的首个邻接顶点
        virtual int nextNbr ( int, int ) = 0; //顶点v的（相对于顶点j的）下一邻接顶点
        virtual VStatus& status ( int ) = 0; //顶点v的状态
        virtual int& dTime ( int ) = 0; //顶点v的时间标签dTime
        virtual int& fTime ( int ) = 0; //顶点v的时间标签fTime
        virtual int& parent ( int ) = 0; //顶点v在遍历树中的父亲
        virtual int& priority ( int ) = 0; //顶点v在遍历树中的优先级数
        // 边：这里约定，无向边均统一转化为方向互逆的一对有向边，从而将无向图视作有向图的特例
        int e; //边总数
        virtual bool exists ( int, int ) = 0; //边(v, u)是否存在
        virtual void insert ( Te const&, int, int, int ) = 0; //在顶点v和u之间插入权重为w的边e
        virtual Te remove ( int, int ) = 0; //删除顶点v和u之间的边e，返回该边信息
        virtual EType & type ( int, int ) = 0; //边(v, u)的类型
        virtual Te& edge ( int, int ) = 0; //边(v, u)的数据（该边的确存在）
        virtual int& weight ( int, int ) = 0; //边(v, u)的权重
        // 算法
        void bfs ( int ); //广度优先搜索算法
        void dfs ( int ); //深度优先搜索算法 
        Stack<Tv>* tSort ( int ) //拓扑排序算法

 };


template <typename Tv, typename Te> //广度优先搜索BFS算法（全图）
void Graph<Tv, Te>::bfs ( int s ) { //assert: 0 <= s < n
        reset(); int clock = 0; int v = s; //初始化
        do //逐一检查所有顶点
               if ( UNDISCOVERED == status ( v ) ) //一旦遇到尚未发现的顶点
                  BFS ( v, clock ); //即从该顶点出发启动一次BFS
        while ( s != ( v = ( ++v % n ) ) ); //按序号检查，故不漏不重
     }

template <typename Tv, typename Te> //广度优先搜索BFS算法（单个连通域）
void Graph<Tv, Te>::BFS ( int v, int& clock ) { //assert: 0 <= v < n
     Queue<int> Q; //引入辅助队列
     status ( v ) = DISCOVERED; Q.enqueue ( v ); //初始化起点
     while ( !Q.empty() ) { //在Q变空之前，不断
           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 ); //发现该顶点
                      type ( v, u ) = TREE; parent ( u ) = v; //引入树边拓展支撑树
                 } else { //若u已被发现，或者甚至已访问完毕，则
                      type ( v, u ) = CROSS; //将(v, u)归类于跨边
                 }
                 status ( v ) = VISITED; //至此，当前顶点访问完毕
           }
}


template <typename Tv, typename Te> //深度优先搜索DFS算法（全图）
void Graph<Tv, Te>::dfs ( int s ) { //assert: 0 <= s < n
        reset(); int clock = 0; int v = s; //初始化
        do //逐一检查所有顶点
               if ( UNDISCOVERED == status ( v ) ) //一旦遇到尚未发现的顶点
                  DFS ( v, clock ); //即从该顶点出发启动一次DFS
        while ( s != ( v = ( ++v % n ) ) ); //按序号检查，故不漏不重
}


template <typename Tv, typename Te> //深度优先搜索DFS算法（单个连通域）
void Graph<Tv, Te>::DFS ( int v, int& clock ) { //assert: 0 <= v < n
        dTime ( v ) = ++clock; status ( v ) = DISCOVERED; //发现当前顶点v
        for ( int u = firstNbr ( v ); -1 < u; u = nextNbr ( v, u ) ) //枚举v的所有邻居u
               switch ( status ( u ) ) { //并视其状态分别处理
                  case UNDISCOVERED: //u尚未发现，意味着支撑树可在此拓展
                         type ( v, u ) = TREE; parent ( u ) = v; DFS ( u, clock ); break;
                      case DISCOVERED: //u已被发现但尚未访问完毕，应属被后代指向的祖先
                         type ( v, u ) = BACKWARD; break;
                      default: //u已访问完毕（VISITED，有向图），则视承袭关系分为前向边或跨边
                         type ( v, u ) = ( dTime ( v ) < dTime ( u ) ) ? FORWARD : CROSS; break;
                   }
        status ( v ) = VISITED; fTime ( v ) = ++clock; //至此，当前顶点v方告访问完毕
}


template <typename Tv, typename Te> //基于DFS的拓扑排序算法
Stack<Tv>* Graph<Tv, Te>::tSort ( int s ) { //assert: 0 <= s < n
        reset(); int clock = 0; int v = s;
        Stack<Tv>* S = new Stack<Tv>; //用栈记录排序顶点
        do {
               if ( UNDISCOVERED == status ( v ) )
                      if ( !TSort ( v, clock, S ) ) { //clock并非必需
                         while ( !S->empty() ) //任一连通域（亦即整图）非DAG
                                S->pop(); break; //则不必继续计算，故直接返回
                      }
            } while ( s != ( v = ( ++v % n ) ) );
        return S; //若输入为DAG，则S内各顶点自顶向底排序；否则（不存在拓扑排序），S空
     }

template <typename Tv, typename Te> //基于DFS的拓扑排序算法（单趟）
bool Graph<Tv, Te>::TSort ( int v, int& clock, Stack<Tv>* S ) { //assert: 0 <= v < n
        dTime ( v ) = ++clock; status ( v ) = DISCOVERED; //发现顶点v
        for ( int u = firstNbr ( v ); -1 < u; u = nextNbr ( v, u ) ) //枚举v的所有邻居u
               switch ( status ( u ) ) { //并视u的状态分别处理
                  case UNDISCOVERED:
                         parent ( u ) = v; type ( v, u ) = TREE;
                         if ( !TSort ( u, clock, S ) ) //从顶点u处出发深入搜索
                        return false; //若u及其后代不能拓扑排序（则全图亦必如此），故返回并报告
                         break;
                      case DISCOVERED:
                         type ( v, u ) = BACKWARD; //一旦发现后向边（非DAG），则
                         return false; //不必深入，故返回并报告
                      default: //VISITED (digraphs only)
                         type ( v, u ) = ( dTime ( v ) < dTime ( u ) ) ? FORWARD : CROSS;
                         break;
                   }
        status ( v ) = VISITED; S->push ( vertex ( v ) ); //顶点被标记为VISITED时，随即入栈
        return true; //v及其后代可以拓扑排序
}

#endif //STACK_GRAPH_H

代码中对各个算法都有比较详细的注释，请读者细细体会三大算法的实现。

前面说过，图的结构为：V和E集合，其中，V是顶点，E是边。简单来说，可以用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。

下面我们通过邻接矩阵来构建一个完整的图结构，为了能够与三大算法联系起来，我们在下面的GraphMatrix.h文件中include上面的Graph.h：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/*
 *
 * 作者：易果啥笔
 * 时间：2021.8.22
 * 内容：邻接矩阵的头文件
 *
 *
 */

#ifndef STACK_GRAPHMATRIX_H
#define STACK_GRAPHMATRIX_H
#include "Vector.h" //引入向量
#include "Graph.h" //引入图ADT

template <typename Tv> struct Vertex { //顶点对象（为简化起见，并未严格封装）
        Tv data; int inDegree, outDegree; VStatus status; //数据、出入度数、状态
        int dTime, fTime; //时间标签
        int parent; int priority; //在遍历树中的父节点、优先级数
        Vertex ( Tv const& d = ( Tv ) 0 ) : //构造新顶点
           data ( d ), inDegree ( 0 ), outDegree ( 0 ), status ( UNDISCOVERED ),
           dTime ( -1 ), fTime ( -1 ), parent ( -1 ), priority ( INT_MAX ) {} //暂不考虑权重溢出
};

template <typename Te> struct Edge { //边对象（为简化起见，并未严格封装）
        Te data; int weight; EType type; //数据、权重、类型
        Edge ( Te const& d, int w ) : data ( d ), weight ( w ), type ( UNDETERMINED ) {} //构造
     };

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++ ) //边记录
                         delete E[j][k]; //逐条清除
            }
     // 顶点的基本操作：查询第i个顶点（0 <= i < n）
        virtual Tv& vertex ( int i ) { return V[i].data; } //数据
        virtual int inDegree ( int i ) { return V[i].inDegree; } //入度
        virtual int outDegree ( int i ) { return V[i].outDegree; } //出度
        virtual int firstNbr ( int i ) { return nextNbr ( i, n ); } //首个邻接顶点
        virtual int nextNbr ( int i, int j ) //相对于顶点j的下一邻接顶点（改用邻接表可提高效率）
        { while ( ( -1 < j ) && ( !exists ( i, --j ) ) ); return j; } //逆向线性试探
        virtual VStatus& status ( int i ) { return V[i].status; } //状态
        virtual int& dTime ( int i ) { return V[i].dTime; } //时间标签dTime
        virtual int& fTime ( int i ) { return V[i].fTime; } //时间标签fTime
        virtual int& parent ( int i ) { return V[i].parent; } //在遍历树中的父亲
        virtual int& priority ( int i ) { return V[i].priority; } //在遍历树中的优先级数
     // 顶点的动态操作
        virtual int insert ( Tv const& vertex ) { //插入顶点，返回编号
               for ( int j = 0; j < n; j++ ) E[j].insert ( NULL ); n++; //各顶点预留一条潜在的关联边
               E.insert ( Vector<Edge<Te>*> ( n, n, ( Edge<Te>* ) NULL ) ); //创建新顶点对应的边向量
               return V.insert ( Vertex<Tv> ( vertex ) ); //顶点向量增加一个顶点
            }
        virtual Tv remove ( int i ) { //删除第i个顶点及其关联边（0 <= i < n）
               for ( int j = 0; j < n; j++ ) //所有出边
                      if ( exists ( i, j ) ) { delete E[i][j]; V[j].inDegree--; e--; } //逐条删除
               E.remove ( i ); n--; //删除第i行
               Tv vBak = vertex ( i ); V.remove ( i ); //删除顶点i
               for ( int j = 0; j < n; j++ ) //所有入边
                      if ( Edge<Te> * x = E[j].remove ( i ) ) { delete x; V[j].outDegree--; e--; } //逐条删除
               return vBak; //返回被删除顶点的信息
            }
     // 边的确认操作
        virtual bool exists ( int i, int j ) //边(i, j)是否存在
        { return ( 0 <= i ) && ( i < n ) && ( 0 <= j ) && ( j < n ) && E[i][j] != NULL; }
     // 边的基本操作：查询顶点i与j之间的联边（0 <= i, j < n且exists(i, j)）
        virtual EType & type ( int i, int j ) { return E[i][j]->type; } //边(i, j)的类型
        virtual Te& edge ( int i, int j ) { return E[i][j]->data; } //边(i, j)的数据
        virtual int& weight ( int i, int j ) { return E[i][j]->weight; } //边(i, j)的权重
     // 边的动态操作
        virtual void insert ( Te const& edge, int w, int i, int j ) { //插入权重为w的边e = (i, j)
               if ( exists ( i, j ) ) return; //确保该边尚不存在
               E[i][j] = new Edge<Te> ( edge, w ); //创建新边
               e++; V[i].outDegree++; V[j].inDegree++; //更新边计数与关联顶点的度数
            }
        virtual Te remove ( int i, int j ) { //删除顶点i和j之间的联边（exists(i, j)）
               Te eBak = edge ( i, j ); delete E[i][j]; E[i][j] = NULL; //备份后删除边记录
               e--; V[i].outDegree--; V[j].inDegree--; //更新边计数与关联顶点的度数
               return eBak; //返回被删除边的信息
            }
};
#endif //STACK_GRAPHMATRIX_H

至此，一个完整的图结构就构建完毕了。

图作为数学领域与计算机领域交汇的内容，不论是在数学领域，还是在计算机领域，都有着非常多的应用，这些应用不仅推动了数学和计算机的发展，更是体现着人类的独高智慧。

本文作者：LuoYing @ 小小白的笔记屋

本文链接：https://luoying.netlify.app/2021/08/22/58nr6yi6/

本文标题：数据结构与算法之-----图（代码实现）

本文版权：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！