[数据结构]图——C++描述
本文章不涉及图的顶点（vertex，也可以叫做结点，node）和边（edge）的操作（删除顶点、删除边、收缩边等），简单讲解并实现一些与图相关的算法。
图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph=(V，E)。V是vertex的缩写，表示要研究的图的顶点的有穷非空集合；E是Edge的缩写，表示要研究的顶点之间的关系集合。
下面来先介绍一下理解学习图之前所必须要了解的图的一些性质。
一、图的概念
（一）、有向图和无向图
有向图（directed graph），对于顶点 x 和 y 的关系用 <x, y> 有序二元序偶表示，<x, y>是有方向的，即 <x, y> 和 <y, x> 表示不同的关系，即表示不同的边。比如下面这个有向图：
所有的顶点：1,2,3
所有的边：<1, 2>, <1, 3>, <2, 3>, <3, 1>
无向图（undirected graph），对于顶点 x 和 y 的关系用 (x, y) 无序对表示，(x, y) 没有方向可言，(x, y) 和（y, x）表示同一条边。比如下面这个无向图：
所有的顶点：1,2,3
所有的边：(1, 2) , (1, 3) , (2, 3)
（二）、完全图（complete graph）
1、无向完全图
- 无向完全图的特性：
- 每个顶点都和其他顶点有边，边数达到最大。
- 若无向图有n个顶点，则有 n(n - 1) / 2 条边。
- 例子：
边数：(3 * 2) / 2 = 3
解释：对于每个顶点，除了自己和自己以外，都可以和其他的顶点存在一条边，也就是说，考虑方向的话总共可以构建n(n-1)条边，但是因为是无向图，有一半的边都是重复的，最终边数为n(n-1) / 2。
2、有向完全图
- 有向完全图图的特性：
- 每个顶点都和其他顶点有两条边（出边和入边），边数达到最大。
- 若无向图有n个顶点，则有 n(n - 1) 条边。
- 例子：
边数：3 * 2 = 6
解释：对于每个顶点，除了自己和自己以外，都可以和其他的顶点存在一条边，也就是说，最多构建了n(n-1)条边。
（三）、权（weight）
特性：
- 每条边带有权值，代表顶点到另一个顶点的代价，距离等。
- 带权图也称为网络（network）
（四）、邻接顶点（adjacent vertex）
- 始点、终点、端点、关联边
- 对于有向边 <u, v>
- 始点（initial node）: u
- 终点（terminal）：v
- 端点（end node）：u、v
- 对于无向边 (u, v)
- 端点：u、v
- 关联边
- 以结点 u 为端点的边，称为结点 u 的关联边。
- 邻接到、邻接结点、孤立结点、邻接边
- 对于有向边 <u, v>
- 邻接到：结点 u 邻接到 结点 v
- 邻接结点（adjacent node）：结点 u 和结点 v 互为邻接结点。
- 孤立结点（isolated node）：没有邻接结点的结点
- 邻接边（adjacent edge）：具有公共端点的边称为邻接边
（五）、子图（subgraph）
- 特性：
仅使用属于某个图中的顶点和边构成的图称为该图的子图。
- 例子：
（六）、度（degree）
- 对于有向图的顶点 v
- 出度（outdegree）:以 v 为起始点的边的个数，记为 outdegree(v)
- 入度（indegree）：以 v 为终点的边的个数。记为 indegree(v)
- 度（degree）：度 = 入度 + 出度，即 degree(v) = indegree(v) + outdegree(v)
- 一般的，若图有n个顶点、e条边，则有
- 对于无向图的顶点 v
- 度（degree）：度 = 入度 = 出度，即 degree(v) = indegree(v) = outdegree(v)
- 举例：
顶点v
入度
出度
度
0
1
2
3
1
1
1
2
2
1
1
2
3
2
1
3
4
1
1
2
该有向图边的个数
（七）、路径（path）
从某顶点
出发通过图中的边到达顶点
所经过若干的顶点序列
，则称顶点序列
为顶点
（八）、路径长度（path length）
从顶点
（九）、简单路径（通路）与回路
- 简单路径：路径
- 基本路径：路径
- 回路（cycle）：路径
（十）、连通和连通分量（ & ）
- 连通：在无向图中，若顶点
无向图
- 连通图（connected graph）：若图中任意一对顶点都是连通的，那么称此图为连通图。
- 连通分量（connected component）：非连通图中的极大连通子图称为连通分量。
有向图
- 强连通图：若每一对顶点
和
之间都存在一条从
- 连通图：非强连通图的极大连通子图叫做强连通分分量。
（十一）、生成树（spanning tree）
- 无向连通图的极小连通子图是生成树。若图中有 n 个顶点，则其生成树有且仅有 n - 1 条边组成。
二、图的存储结构
- 顶点的存储：
- 存储顶点集合 V，使用连续的该顶点类型的数组存储顶点信息即可，可以通过数组的下标找到对应的顶点信息。
- 建立 顶点 与 数组下标 的映射关系，可以通过具体的顶点定位到该顶点在数组中的相应位置。
下面来讲一下几种表示图的存储方法。
（一）邻接矩阵（adjacency matrix）表示
1、思路讲解
若图有n个顶点，则使用二维的n行n列的矩阵来表示顶点和顶点之间的边，该矩阵可以用二维数组 matrix 来表示。
设任意顶点
表示边
- 对于无权值的图
- 如果
- 如果
- 对于有权值的图
- 如果
- 如果
- 如果
- 简单约定：
- 为简单起见，权值 W 的类型我们认定为 int 类型
- 在无权图中，我们也采用matrix[i][j] = W_MAX 或 0 表示 i 和 j 没有边。
- 把无权图视为有权图，即使用有权图表示无权图，如果是无权图，在添加边时，则使用1作为边的权值加入。
下面是无权值的无向图和有向图的邻接矩阵表示：
无向图
矩阵特点：
- 无向图的邻接矩阵是对称的，即 matrix[i][j] = matrix[j][i].
- 主对角线上的元素的值都为0.
- 判断
- 找到始点为
- 遍历矩阵的第 i 行或第 i 列可以得到
有向图：
矩阵特点：
- 主对角线上的元素的值都为0.
- 判断
- 判断邻接自
- 判断邻接到
- 遍历矩阵的第 i 行得到
- 遍历矩阵的第 j 行得到
邻接矩阵的优点：
- 能以O(1)的时间复杂度判断出顶点
邻接矩阵的缺点：
- 存储稀疏图时比较浪费空间，稀疏图指的是顶点多但是边比较少的图。
- 遍历某个顶点
2、代码实现
下面是使用邻接矩阵来表示的图代码：
Graph.h:
#pragma once
#include <vector>
#include <unordered_map>
#include <assert.h>
#include <cstdio>
namespace MyGraph
{
using namespace std;
const int W_MAX = 999; //表示权值的最大值
//模板参数 V：顶点类型
template<class V>
class Graph
{
private:
typedef vector<vector<int>> Maxtrix; //邻接矩阵
typedef Graph<V> Self; //图自身
Maxtrix _matrix; //邻接矩阵
vector<V> _vertex; //每个下标对应一个顶点，通过下标访问顶点
unordered_map<V, int> _vToi; //顶点元素和下标建立映射关系，可以通过顶点快速找到顶点集合中的对应下标
bool _hasDir; //表示该图为有向图还是无向图,默认为无向图
//通过顶点获得对应映射的下标
int getVertexIndex(const V& v)
{
auto it = _vToi.find(v);
assert(it != _vToi.end()); //断言：传入的顶点没有所映射的下标值
return it->second;
}
public:
//构造函数 用n个顶点初始化图
Graph(const V* vArr, int n, bool hasDir = false)
:_hasDir(hasDir)
{
_matrix.resize(n);
_vertex.resize(n);
for (int i = 0; i < n; i++)
{
_matrix[i].resize(n);
//读入顶点并建立映射关系
_vertex[i] = vArr[i];
_vToi[vArr[i]] = i;
}
//初始化邻接矩阵,不用管图是否有权值，一律当有权处理
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
_matrix[i][j] = W_MAX;
}
_matrix[i][i] = 0; //对角线位置的权值设为0
}
}
//为顶点 v1 v2添加边
//把无权图视为有权图，即使用有权图表示无权图.
//如果是无权图，在添加边时，则使用1作为边的权值加入。
bool addEdge(const V& v1, const V& v2, int wt = 1)
{
int i = getVertexIndex(v1);
int j = getVertexIndex(v2);
if (i == j)
{
cout << "无法给顶点自己建立边" << endl;
return false;
}
else if (_matrix[i][j] < W_MAX)
{
cout << "该条边已经添加过了" << endl;
return false;
}
else
{
_matrix[i][j] = wt;
if (!_hasDir)
_matrix[j][i] = wt;
}
return true;
}
//打印邻接矩阵
void printMatrix()
{
int n = _vertex.size();
//打印顶点集合
for (int i = 0; i < n; i++)
{
printf("_vertex[%d]->", i);
cout << _vertex[i] << endl;
}
cout << endl;
//打印矩阵的列号
printf("%4c", ' ');
for (int i = 0; i < n; i++)
{
printf("%4d", i);
}
cout << endl;
//打印邻接矩阵
for (int i = 0; i < n; i++)
{
printf("%-4d", i); //打印行号
for (int j = 0; j < n; j++)
{
printf("%4d", _matrix[i][j]);
}
cout << endl;
}
}
};
}
测试代码main.cpp：
#include <iostream>
#include <cstring>
#include "Graph.h"
using namespace std;
//对邻接矩阵表示的图进行测试
int test1()
{
char str[] = "01234";
MyGraph::Graph<char> g(str, strlen(str), true);
g.addEdge('0', '1');
g.addEdge('0', '3');
g.addEdge('1', '2');
g.addEdge('2', '3');
g.addEdge('3', '4');
g.addEdge('4', '0');
g.printMatrix();
return 0;
}
int main()
{
test1();
return 0;
}使用的测试用例以及运行结果：
（二）、邻接表（adjacency list）表示
1、思路讲解
设图的顶点个数为 n ，那么则需要开辟大小为 n 的指针数组，每个指针对应着一个链表。数组中的第 i 个链表里的每个结点都记录着以 为始点的边。
下面来看一下使用邻接表表示无向图的例子：
观察发现，同一条边在邻接表中出现了两遍，对于边 (i , j), 其中一条边在顶点为
如果想要找到始点为
下面来看一下使用邻接表表示有向图的例子：
对于有向图，每条边都是不相同的，所以一条边只会在链表结点中出现一次， 我们遍历顶点
如果为有权图，把权值存在结点里面就行，可以为了简单起见，把无权图也作为有权图处理，使用有权图表示无权图时，权值设置为 1 即可。
使用邻接表表示的代码这里就不写了，就是维护一个简单的单链表，每次加进一条边，将边结点头插进链表即可，比较简单，需要注意的是：在每一次添加边的时候，需要遍历一遍链表结点，看这条边是否已经被重复添加过了；还要记得写析构函数把链表结点一一释放掉。
邻接表的优点：
- 存储稀疏图时空间开销小。
- 在遍历某个顶点
邻接表的缺点：
- 不能以O(1)的时间复杂度判断出顶点
- 想要快速找顶点
- 用邻接表存储无向图时，同一条边会被存储两遍，如果我们要标记某条边，则需要将邻接表中这条边对应的两个结点找出来都标记一遍，但是这两个结点在不同的链表上，操作不方便，下面的邻接多重表可以解决这个问题。
（三）邻接多重表(adjacency multilist)
1、思路讲解
邻接多重表解决了邻接表存储无向图时重复存储边的问题。
邻接多重表的链表结点由下面五个关键的域组成：
其中 mark 为标记域，可以表示该条边是否被遍历过，i 和 j 表示该边的两个顶点
下面来看使用邻接多重表存储无向图的例子：
这个多重邻接表是我自己连的。在初次看到这个结点之间的指针交织错乱的多重邻接表时，是个人都要慌，但是其实很简单的，请听我分析完，你就会发现这个结构是多么的简单又奇妙。
先来读懂这个多重邻接表，再来看是如何实现的。还是每个顶点对应一条链表。
对于下标为0的顶点A: 头指针指向 (0, 1) 这个结点，我们就找到了 (0, 1) 这条边，然后要找依附于顶点A的下一条边，顶点A的下标为0，在结点中对应数据域为 i ，所以接下来我们访问指针 iNext 所指向的这个结点，于是就找到了 (0, 3) 这条边。按照上面的规律，访问 iNext ，但是 iNext 为空，遍历结束。我们就得到了 (0, 1) 和 (0, 3) 这两条边。也就是 (A, B) 和 (A, D)
对于下标为1的顶点B: 头指针指向 (0, 1) 这条边，1对应着数据域 j ，所以我们访问 jNext 指向的下一个结点，也就是 (1, 2)。接着访问 iNext ,也就是 (1, 4) ,接着 iNext 等于空，访问结束。得到 (0, 1) (1, 2) 和 (1,4) 这一些边，也就是 (A, B) (B, C) 和 (B, E)
对于下标2的顶点C：(1, 2) (2, 3) (2, 4) 即 (B, C) (C, D) (C, E)
对于下标3的顶点D: (2, 3) (0, 3) 即 (C, D) (A, D)
对于下标4的顶点E: (1, 4) (2, 4) 即 (B, E) (C, E)
下面来讲一下这个邻接多重表是怎么做到的。每个顶点都对应着一个独立的链表，然后每条边对应着一个结点，每个结点会存在于两个独立的链表中，比如说 和
这两个顶点的边 (i, j) ，他既存在于第 i 个链表中，又存在于第 j 个链表中。第 i 个链表存储依附于顶点 i 的边，第 j 个链表存储依附于顶点 j 的边，也就是说，当我们插入一条边时 (i , j)，我们要同时将该结点头插到第 i 个链表和第 j 个链表中去。
下面来演示这一过程。
插入边：(0, 3)
插入边：(2, 4)
插入边：(1, 4)
插入边: (2, 3)
插入边: (1, 2)
插入边: (0, 1)
多重邻接表这个结构还有个头疼的地方就是析构时没那么简单，因为单个结点会存在于两个链表中，如果遍历到一个结点就删除一个结点，会破坏多重邻接表的结构，会导致结点丢失，内存泄露。这里讲一下两种思路，一种比较简单粗暴（我不假思索就想到的解决方案），另一是需要技巧和思考才能想到的方法（我问的室友，室友给出的更合理的解决方案）。
方法一：使用set容器，将每个结点遍历一遍将其地址存入set容器中，借助set可以去重的性质，可以将复杂的多重邻接表的析构转为遍历set容器中的指针进行析构。
方法二：使用标记域 mark 辅助析构，当我们第一次遍历到某结点时，我们不要把该结点直接析构，而是将该结点 mark 标记域标记true，然后先放着不管，继续遍历链表中其他结点，进行相同操作，放着不管没关系，因为这个结点还可以通过另一个链表找到，不用担心丢失结点。当访问到 mark 被标记的结点时，我们可以知道，如果 mark 被标记过了，说明这个结点先前在另一个链表中访问过了，我们这个时候如果不管这个结点，这个结点就会永远丢失！因为它现在只存在于现在正在访问的这个链表中，这个时候我们就可以将这个结点安全释放掉了，然后再继续遍历链表的其他结点，进行相同操作。
多说一嘴，还可以不使用 mark 标记域实现上面的功能，也就是说，打头一开始就可以不用给边结点定义 mark 域（还是室友想到的，核心思想还是上面那样），首先我们临时创建一个边结点，叫做dummyNode，使用该结点充当 mark 的功能。就是在遍历顶点 这个顶点对应的链表时，当我们第一次遍历到某结点时，我们把依附于顶点
的指针（ iNext 和 jNext 都有可能）的值指向 dummyNode，然后遍历其他结点，进行相同的操作。然后我们再遍历下一个顶点
的链表，如果我们第二次遍历到某个结点时，其中不依附于顶点
的指针（ iNext 和 jNext 都有可能）在第一次遍历时已经将其指向了dummyNode，这个时候我们就可以将其安全释放掉了，然后接着遍历链表其他结点，进行相同操作。
如果想要不重复的打印出邻接多重表的所有边，在遍历顶点 的链表结点时，我们规定只将
在边中对应着 i 位置的边打印出来，不打印
在边中对应着 j 位置的边，这样就可达到不重复的打印出所有边的目的。
2、代码实现
Graph.h:
#pragma once
#include <vector>
#include <unordered_map>
#include <assert.h>
#include <cstdio>
//多重邻接表版本
namespace MyGraph1
{
using namespace std;
const int W_MAX = 999; //表示权值的最大值
//邻接多重表结点的定义
struct EdgeNode
{
bool _mark; //标记
int _i;
int _j;
EdgeNode* _iNext; //指向依附于顶点i的下一条边
EdgeNode* _jNext; //指向依附于顶点j的下一条边
//如果边需要带权值，在这里加上即可
EdgeNode(int i, int j)
:_mark(false), _i(i), _j(j),
_iNext(nullptr), _jNext(nullptr)
{}
};
//模板参数 V：顶点类型
template<class V>
class Graph
{
private:
vector<EdgeNode*> _multList; //指针数组，用于维护每个链表
vector<V> _vertex; //每个下标对应一个顶点，通过下标访问顶点
unordered_map<V, int> _vToi; //顶点元素和下标建立映射关系，可以通过顶点快速找到顶点集合中的对应下标
//通过顶点获得对应映射的下标
int getVertexIndex(const V& v)
{
auto it = _vToi.find(v);
assert(it != _vToi.end()); //断言：传入的顶点没有所映射的下标值
return it->second;
}
public:
//构造函数 用n个顶点初始化图
Graph(const V* vArr, int n)
{
//初始化多重邻接表，一开始链表都为空
_multList.resize(n, nullptr);
_vertex.resize(n);
for (int i = 0; i < n; i++)
{
//读入顶点并建立映射关系
_vertex[i] = vArr[i];
_vToi[vArr[i]] = i;
}
}
//为顶点 v1 v2添加边
bool addEdge(const V& v1, const V& v2)
{
int i = getVertexIndex(v1);
int j = getVertexIndex(v2);
if (i == j)
{
cout << "无法给顶点自己建立边" << endl;
return false;
}
else
{
//在这里添加边，还需要进行查重操作，即判断要加入的边是否已经存在了
//查重操作的代码就不给出了，这里假设插入的每一条边都不重复
//................................
//................................
//该边结点依附于顶点 i 和 j，
//所以要把该结点头插到第 i 个链表和第 j 个链表中
EdgeNode* newEdge = new EdgeNode(i, j);
//头插到第 i 个链表中
newEdge->_iNext = _multList[i];
_multList[i] = newEdge;
//头插到第 j 个链表中
newEdge->_jNext = _multList[j];
_multList[j] = newEdge;
return true;
}
}
//打印各顶点所对应的链表
void printList()
{
int n = _vertex.size();
EdgeNode* pCur = nullptr;
for (int i = 0; i < n; i++)
{
pCur = _multList[i];
cout << "顶点" << _vertex[i] << " ,对应第 " << i << " 个链表：";
while (pCur)
{
cout << "(" << pCur->_i << ", " << pCur->_j << ") ";
if (i == pCur->_i) //顶点对应 i
pCur = pCur->_iNext;
else //顶点对应 j
pCur = pCur->_jNext;
}
cout << endl;
}
}
//邻接表的释放操作
~Graph()
{
int n = _vertex.size();
EdgeNode* pCur = nullptr;
EdgeNode* pNext = nullptr;
for (int i = 0; i < n; i++)
{
pCur = _multList[i];
while (pCur)
{
if (i == pCur->_i) //顶点对应 i
pNext = pCur->_iNext;
else //顶点对应 j
pNext = pCur->_jNext;
if (pCur->_mark == false) //如果是第一次访问，先不做处理
{
pCur->_mark = true;
}
else //第二次访问, 说明该结点只存在于当前这个链表当中，可以安全删除
{
//删除 pCur 结点
cout << "删除边:(" << pCur->_i << ", " << pCur->_j << ") " << endl;
delete pCur;
}
pCur = pNext;
}
}
}
};
}main.cpp ：
#include <iostream>
#include <cstring>
#include "Graph.h"
using namespace std;
//测试邻接多重表
void test2()
{
char str[] = "ABCDE";
MyGraph1::Graph<char> g(str, strlen(str));
//按照测试用例的顺序添加边
g.addEdge('A', 'D');
g.addEdge('C', 'E');
g.addEdge('B', 'E');
g.addEdge('C', 'D');
g.addEdge('B', 'C');
g.addEdge('A', 'B');
g.printList();
}
int main()
{
//test1();
test2();
return 0;
}测试用例以及结果：
测试用例：
测试结果：
（四）十字链表(Orthogonal List)
1、思路讲解
十字链表是表示有向图的一种链式存储结构。在邻接表中，想要知道某个顶点的出边和入边，则需要维护一个出边表和一个入边表，需要将同一条边存储两遍，而十字链表能够将入边表和出边表结合起来，同一条边只需要存储一次，进一步节省了空间。
每个顶点都对应两个指针，分别是firstin和firstout，firstin表示依附于当前顶点的第一条入边，firstout表示依附于当前顶点的第一条出边，通过firstin和firstout所对应的链表可以找到当前顶点的所有入边和出边。
十字链表结点由下面四个域组成： 
mark 为标记域，starti 和 startj 表示该边的两个顶点
下面来看下使用十字链表存储有向图的例子：
对于下标为0的顶点A:
出边：访问出边的方法为找到firstout所指向的 (0, 1) 这条边，然后因为starti 为 0 对应着 iNext，我们找到下一条出边 (0, 3), 这样我们就把顶点 A 的所有出边找到了，也就是 （0, 1） 和 （0，3） 即 (A, B) 和 (A, D)
入边：访问入边的方法为找到firstin所指向的 (4, 0） 这条边，然后因为 endj 为 0 对应着 jNext, jNext为空，所以顶点 A 的入边为(4, 0) 也就是 (E, A)
对于下标为1的顶点B:
出边：(1, 2) 即 (B, C)
入边：(0, 1) 即 (A, B)
对于下标为2的顶点C：
出边：(2, 3) 即 (C, D)
入边：(1, 2) 即 (B, C)
对于下标为3的顶点D:
出边：(3, 4) 即 (D, E)
入边：(0, 3) 和 (2 , 3) 即 (A, D) 和 (C, D)
对于下标为4的顶点E：
出边：(4, 0) 即 (E, A)
入边：(3, 4) 即 (D, E)
实现十字链表的方法为，当插入的边为 <i, j> 时，我们需要把这条边头插到第 i 个顶点的fristout链表中，即增添第 i 个顶点的出边，然后还需要把这条边头插到第 j 个顶点的firstin链表中，即增添第 j 个顶点的入边。十字链表的析构比较简单，只需要将每个结点的firstout所指向的链表依次释放掉，firstin置为空即可，不像析构多重邻接表那么复杂，因为每个顶点的firstout链表里的边都是该顶点的出边，而每条边是不相同的，不会出现在别的顶点的出边链表里，所以可以直接析构掉出边链表，不用担心因为破坏了结构而丢失结点。
2、代码实现
Graph.h
#pragma once
#include <vector>
#include <unordered_map>
#include <assert.h>
#include <cstdio>
//十字链表版本
namespace MyGraph2
{
using namespace std;
const int W_MAX = 999; //表示权值的最大值
//十字链表结点的定义
struct EdgeNode
{
bool _mark; //标记
int _starti;
int _endj;
EdgeNode* _iNext; //指向下一条边,下一条边的starti和这里的starti相同
EdgeNode* _jNext; //指向下一条边,下一条边的endj和这里的endi相同
//如果边需要带权值，在这里加上即可
EdgeNode(int i, int j)
:_mark(false), _starti(i), _endj(j),
_iNext(nullptr), _jNext(nullptr)
{}
};
//顶点的表结构定义
struct VertexTable
{
EdgeNode* firstin = nullptr;
EdgeNode* firstout = nullptr;
};
//模板参数 V：顶点类型
template<class V>
class Graph
{
private:
vector<VertexTable> _ortList; //顶点表数组
vector<V> _vertex; //每个下标对应一个顶点，通过下标访问顶点
unordered_map<V, int> _vToi; //顶点元素和下标建立映射关系，可以通过顶点快速找到顶点集合中的对应下标
//通过顶点获得对应映射的下标
int getVertexIndex(const V& v)
{
auto it = _vToi.find(v);
assert(it != _vToi.end()); //断言：传入的顶点没有所映射的下标值
return it->second;
}
public:
//构造函数 用n个顶点初始化图
Graph(const V* vArr, int n)
{
//初始化顶点表数组
_ortList.resize(n);
_vertex.resize(n);
for (int i = 0; i < n; i++)
{
//读入顶点并建立映射关系
_vertex[i] = vArr[i];
_vToi[vArr[i]] = i;
}
}
//为顶点 v1 v2添加边
bool addEdge(const V& v1, const V& v2)
{
int i = getVertexIndex(v1);
int j = getVertexIndex(v2);
if (i == j)
{
cout << "无法给顶点自己建立边" << endl;
return false;
}
else
{
//在这里添加边，还需要进行查重操作，即判断要加入的边是否已经存在了
//查重操作的代码就不给出了，这里假设插入的每一条边都不重复
//................................
//................................
//该边为 <i, j>
//所以要把该边头插到第i个顶点的出边表和第j个顶点的入边表去
EdgeNode* newEdge = new EdgeNode(i, j);
//头插到第 i 个顶点的出边表
newEdge->_iNext = _ortList[i].firstout;
_ortList[i].firstout = newEdge;
//头插到第 j 个顶点的入边表
newEdge->_jNext = _ortList[j].firstin;
_ortList[j].firstin = newEdge;
return true;
}
}
//打印各顶点所对应的链表
void printList()
{
int n = _vertex.size();
EdgeNode* pCur = nullptr;
for (int i = 0; i < n; i++)
{
pCur = _ortList[i].firstout;
cout << "顶点" << _vertex[i] << " ,对应第 " << i << " 个链表：" << endl;
cout << "出边: ";
while (pCur)
{
cout << "<" << pCur->_starti << ", " << pCur->_endj << "> ";
pCur = pCur->_iNext;
}
cout << endl;
pCur = _ortList[i].firstin;
cout << "入边: ";
while (pCur)
{
cout << "<" << pCur->_starti << ", " << pCur->_endj << "> ";
pCur = pCur->_jNext;
}
cout << endl << "---------------------" << endl;
}
}
//十字链的释放操作
~Graph()
{
int n = _vertex.size();
EdgeNode* pCur = nullptr;
EdgeNode* pNext = nullptr;
for (int i = 0; i < n; i++)
{
pCur = _ortList[i].firstout;
while (pCur)
{
pNext = pCur->_iNext;
cout << "删除边: <" << pCur->_starti << ", " << pCur->_endj << "> " << endl;
delete pCur;
pCur = pNext;
}
_ortList[i].firstin = _ortList[i].firstout = nullptr;
}
}
};
}main.cpp:
#include <iostream>
#include <cstring>
#include "Graph.h"
using namespace std;
//测试十字链表
void test3()
{
char str[] = "ABCDE";
MyGraph2::Graph<char> g(str, strlen(str));
//按照测试用例的顺序添加边
g.addEdge('A', 'B');
g.addEdge('A', 'D');
g.addEdge('B', 'C');
g.addEdge('C', 'D');
g.addEdge('D', 'E');
g.addEdge('E', 'A');
g.printList();
}
int main()
{
//test1();
test3();
return 0;
}测试用例和运行结果：
测试用例：
运行结果：
三、图的遍历
为了方便介绍后面的内容，都采用邻接矩阵表示。
遍历图的方法有两种，分别是深度优先遍历(depth first search，DFS) 和 广度优先遍历(breadth first search, BFS)。
（一）、深度优先遍历
1、DFS算法思路
深度优先遍历使用了递归的思想。首先我们需要一个访问标志 visited 数组，如果对应的顶点 i 被访问过了，则 visited[i] = true。
遍历方法如下：
首先指定一个起始的顶点 v 作为当前顶点，然后将该顶点标记为已访问，接着在顶点 v 的所有邻接顶点中，找出尚未访问过的一个顶点，以当前结点为入口，将尚未访问过的那个顶点作为下一步要进行访问的当前顶点，重复上述过程。
如果当前顶点的所有邻接顶点都已经访问完了，则回溯到访问该顶点的入口处，继续取出当前顶点未访问过的邻接顶点作为下一步要访问的当前顶点。重复上述过程，直到最初指定的起始顶点的所有邻接顶点都被访问到，此时与起始顶点 v 连通的所有顶点都被访问过了。
由于该访问方式跟树的前序遍历次序类似，所以通过深度优先遍历而得来的连通子图又称为原图的深度优先生成树(DFS tree)。
下面是深度优先搜索的示意图：
图中的数字表示访问的次序，得到ABEGCFDHI这个序列。
2、DFS的性能分析
对于有 n 个顶点，e条边的图：
- 空间复杂度：需要开辟用于标记顶点是否被访问过的标志数组，总时间复杂度为 O(n)。
- 时间复杂度：
- 邻接矩阵表示：对于每个顶点 v，需要遍历顶点 v 的所有的边，所需时间为O(n)，则遍历图中所有边所需的时间为
。所以最终的时间复杂度为
- 邻接表：对于每个顶点 v ，需要遍历顶点 v 的所有边，则遍历图中所有边所需要时间为O(e)，每个顶点都被访问一遍，所需时间为 O(n)。所以最终的时间复杂度为 O(n + e)。
（二）、广度优先遍历
1、BFS算法思路
广度优先遍历是一个逐层遍历的过程，类似于树的层序遍历，一层一层的访问结点。
需要准备的工作：首先我们需要一个访问标志 visited 数组，如果对应的顶点 i 被访问过了，则visited[i] = true。然后我们还需要一个队列辅助遍历，该队列存储着将要访问顶点，并且加入到队列里的顶点也要标记为已访问。首先将要遍历的第一个起始顶点入队列。
执行的操作：取出队列中的一个顶点进行访问，然后将该顶点的所有未被标记过的邻接顶点入队列，重复上面操作，直到连通图中的所有顶点都被访问到为止。
下面是深度优先搜索的示意图：
图中的数字表示访问的次序，遍历每一层的顶点，得到层序：
- A
- B D C
- E F
- G H
- I
通过广度优先遍历而得来的连通子图称为原图的广度优先生成树(BFS tree)。
2、BFS的性能分析
对于有 n 个顶点，e条边的图：
- 空间复杂度：需要开辟用于标记顶点是否被访问过的标志数组和一个队列，总时间复杂度为 O(n)。
- 时间复杂度：
- 邻接矩阵表示：对于每个顶点 v，需要遍历顶点 v 的所有的边，所需时间为O(n)，则遍历图中所有边所需的时间为
- 邻接表：对于每个顶点 v，需要遍历顶点 v 的所有边，则遍历图中所有边所需要时间为O(e)，每个顶点都被访问一遍，所需时间为O(n)。所以最终的时间复杂度为O(n + e)。
（三）、代码实现
在使用DFS和BFS遍历图的时候，都需要提供一个起始点来遍历。如果遍历的图不是连通图，单单通过这一个起始点是无法遍历到所有顶点的，所以在起始点执行完一次搜索后，还要检查visited中未被访问过的顶点，以这些顶点作为起始点展开一轮新的遍历，这样才能遍历完所有顶点。
Graph.h
#pragma once
#include <vector>
#include <queue>
#include <unordered_map>
#include <assert.h>
#include <cstdio>
//邻接矩阵版本
namespace MyGraph
{
using namespace std;
const int W_MAX = 999; //表示权值的最大值
//模板参数 V：顶点类型
template<class V>
class Graph
{
private:
typedef vector<vector<int>> Maxtrix; //邻接矩阵
typedef Graph<V> Self; //图自身
Maxtrix _matrix; //邻接矩阵
vector<V> _vertex; //每个下标对应一个顶点，通过下标访问顶点
unordered_map<V, int> _vToi; //顶点元素和下标建立映射关系，可以通过顶点快速找到顶点集合中的对应下标
bool _hasDir; //表示该图为有向图还是无向图,默认为无向图
//通过顶点获得对应映射的下标
int getVertexIndex(const V& v);
//实现深度优先递归的子函数
void _travelDFS(int i, vector<bool>& isVisited)
{
//先遍历打印当前i所对应的顶点
cout << _vertex[i] << "->";
isVisited[i] = true;
//然后通过递归深度遍历该顶点的没有遍历过的邻接顶点
int n = _matrix.size();
for (int j = 0; j < n; j++)
{
if (_matrix[i][j] != W_MAX && !isVisited[j])
{
_travelDFS(j, isVisited);
}
}
}
//辅助广度优先遍历DFS的子函数:以beginV顶点为起始点进行广度优先搜索
void _traveBFS(const V& beginV, vector<bool>& isVisited)
{
int n = _vertex.size();
int beginI = getVertexIndex(beginV);
queue<int> q;
q.push(beginI);
int levelCount = 1; //层数
int levelNums = 1; //每层的个数
while (!q.empty())
{
levelNums = q.size();
cout << "level:" << levelCount << " ";
//遍历该层顶点
for (int l = 0; l < levelNums; l++)
{
int i = q.front();
q.pop();
cout << _vertex[i] << " ";
isVisited[i] = true; //标记已访问状态
for (int j = 0; j < n; j++)
{
//找出当前顶点的邻接顶点，未访问过的顶点或不在队列中的顶点进入队列
if (_matrix[i][j] != W_MAX && !isVisited[j])
{
q.push(j);
isVisited[j] = true; //进入队列的顶点标志为已访问的状态
}
}
}
cout << endl;
levelCount++;
}
}
public:
//构造函数 用n个顶点初始化图
Graph(const V* vArr, int n, bool hasDir = false);
//为顶点 v1 v2添加边
//把无权图视为有权图，即使用有权图表示无权图.
//如果是无权图，在添加边时，则使用1作为边的权值加入。
bool addEdge(const V& v1, const V& v2, int wt = 1);
//打印邻接矩阵
void printMatrix();
//DFS深度优先遍历
void traveDFS(const V& beginV)
{
int n = _vertex.size();
vector<bool> isVisited(n, false); //用来表示该顶点是否已经遍历过了
int index = getVertexIndex(beginV);
cout << "顶点" << _vertex[index] << "所在的连通分量：";
_travelDFS(index, isVisited);
cout << endl;
//图不一定都是连通图，要检查有没有不与顶点beginV连通的顶点
// 检查剩余没遍历过的顶点，从中继续以该顶点进行深度遍历
// 如果该点被访问过了，这个点一定在之前求出的连通分量中。
// 连通分量：与该顶点有路径的最大连通图。
for (int i = 0; i < n; i++)
{
if (!isVisited[i])
{
cout << "顶点" << _vertex[i] << "所在的连通分量：";
_travelDFS(i, isVisited);
cout << endl;
}
}
}
//图的广度优先遍历 BFS
void traveBFS(const V& beginV)
{
int n = _vertex.size();
vector<bool> isVisited(n, false);
//先对beginV顶点进行广度优先搜索
_traveBFS(beginV, isVisited);
cout << endl;
//再找剩余没有遍历过的顶点，找出其他连通分量
for (int i = 0; i < n; i++)
{
if (!isVisited[i])
{
_traveBFS(_vertex[i], isVisited);
cout << endl;
}
}
}
};
}main.cpp
#include <iostream>
#include <cstring>
#include "Graph.h"
using namespace std;
//测试深度和广度优先遍历
void test4()
{
char str[] = "ABEDCGFHI";
MyGraph::Graph<char> g(str, strlen(str));
g.addEdge('A', 'B');
g.addEdge('B', 'E');
g.addEdge('A', 'D');
g.addEdge('A', 'C');
g.addEdge('B', 'C');
g.addEdge('E', 'G');
g.addEdge('D', 'F');
g.addEdge('C', 'F');
g.addEdge('F', 'H');
g.addEdge('H', 'I');
g.traveDFS('A');
cout << endl;
g.traveBFS('A');
}
int main()
{
//test1();
test4();
return 0;
}测试用例和运行结果：
四、最小生成树
（一）最小生成树概念
连通图的每一棵生成树，都是原图的一个极大无环子图。也就是说，从其中删去任何一条边，生成树就不再连通；反之，在其中引入任何一条新边，都会恰好形成一个回路。
一个图有多种不同的生成树，对于带权图（网络），不同生成树所对应的总权值也不尽相同，而在给定的有权连通图中找出总权值最小的生成树是实际应用中经常遇到的问题，满足该条件生成树称为最小（代价）生成树（minimum-cost spanning tree）。
按照定义，若连通网络中有 n 个顶点，则其生成树必然有 n 个顶点、n - 1条边。因此，构造最小生成树有下面3条准则。
- 只能使用该网络中的边来构造最小生成树；
- 只能使用恰好n-1条边来联结网络中的n个顶点；
- 选中的这n - 1 条边不能构成回路。
构造最小生成树的典型方法有下面将要介绍的两种。这两个算法都属于贪心算法：给定带权图 N = {V, E}，V 中有n个顶点。首先构造一个包含全部n个顶点和0条边的森林（Forest），然后不断迭代。每次经过一轮迭代，就会在F中引入一条边。经过 n-1 轮迭代，最终得到一棵包含 n - 1条边的最小生成树。
同一带权图可能有多棵不同的最小生成树，比如说多条边的权值相同时容易发生这种现象。
（二）、克鲁斯卡尔（Kruskal）算法
1、思路分析
该算法的基本过程如下：对于一个有 n 个顶点的连通网络 N = {V, E}，首先构造一个由这 n 个顶点组成、不含任何边的图 T = {V, ∅}，其中每个顶点自成一个连通分量。
不断从E中取出权值最小的一条边（若有多条，任取其一），若该边的两个端点来自不同的连通分量，则将此边加入到 T 中。如此重复，直到所有顶点在同一个连通分量上为止，所以该算法也叫避圈法。
下面来举例演示上面的过程：
我们可以看出，使用Kruskal算法求出的最小生成树是唯一的。
下面来看一下该算法的伪代码，分析一下实现上述操作需要做哪些准备。
从边集合 E 中选出一条具有最小代价的边 (v,w) 并从 E 中删除, 可以使用最小堆来实现，最小堆我们可以采用STL的泛型容器：优先队列 （priority_queue）。
而判断边 (v, w) 的两个端点是否在同一个连通分量上则需要应用到并查集(union-find set) ,用于查找两个元素是否在同一个集合上。
2、代码实现
UFSet.h:
#pragma once
#include <vector>
namespace MyUFSet
{
using namespace std;
//并查集
class UFSet
{
private:
vector<int> _parent; //集合元素数组（父指针数组），存储每个结点的双亲位置，如果为负数，则为根节点，对应负数的绝对值为集合个数
public:
UFSet(int size)
:_parent(size, -1)
{
//一开始每个集合元素都为-1，每个元素自成一个集合
}
//找到某个集合成员的根,并压缩路径
int FindRoot(int x)
{
int root = x;
while (_parent[root] >= 0)
{
root = _parent[root];
}
//找到根后，把当前成员x以及上层的所有成员摘下来直接和根相连
int cur = x;
int oldParent;
while (_parent[cur] >= 0)
{
oldParent = _parent[cur];
_parent[cur] = root;
cur = oldParent;
}
return root;
}
//合并两个子集
bool Union(int x1, int x2)
{
int root1 = FindRoot(x1);
int root2 = FindRoot(x2);
if (root1 == root2)
return false;
//默认将root2集合 并 到root1集合
//选择将较小的一方root2的集合并到较大的一方，如果root2集合较大，交换两个root的值，让root2集合永远较小
if (_parent[root1] > _parent[root2]) //-root1 < -root2
{
swap(root1, root2);
}
_parent[root1] += _parent[root2]; //将root2的集合个数加到root1集合上
_parent[root2] = root1; //root2集合并到root1
return true;
}
//得到并查集中集合的个数
int GetCount()
{
int count = 0;
for (auto p : _parent)
{
if (p < 0)
{
count++;
}
}
return count;
}
//判断两个元素在不在一个集合
bool IsTogether(int x, int y)
{
return FindRoot(x) == FindRoot(y);
}
};
};
Graph.h:
#pragma once
#include <vector>
#include <queue>
#include <unordered_map>
#include <assert.h>
#include <cstdio>
#include "UFSet.h" //自己实现的并查集
//邻接矩阵版本
namespace MyGraph
{
using namespace std;
const int W_MAX = 999; //表示权值的最大值
//边的存储结构，用于给最小堆提供边的存储类型
struct Edge
{
typedef Edge Self;
int _source; //始点
int _dest; //目标点
int _wt; //权值
Edge(int source, int dest, const int wt)
:_source(source), _dest(dest), _wt(wt)
{ }
//重载一系列比较运算符，用于提供最小堆算法进行比较操作
bool operator>(const Self& other) const
{
return _wt > other._wt;
}
bool operator<(const Self& other)const
{
return _wt < other._wt;
}
bool operator==(const Self& other) const
{
return _wt == other._wt;
}
};
//模板参数 V：顶点类型
template<class V>
class Graph
{
private:
typedef vector<vector<int>> Maxtrix; //邻接矩阵
typedef Graph<V> Self; //图自身
Maxtrix _matrix; //邻接矩阵
vector<V> _vertex; //每个下标对应一个顶点，通过下标访问顶点
unordered_map<V, int> _vToi; //顶点元素和下标建立映射关系，可以通过顶点快速找到顶点集合中的对应下标
bool _hasDir; //表示该图为有向图还是无向图,默认为无向图
//通过顶点获得对应映射的下标
int getVertexIndex(const V& v);
//实现深度优先递归的子函数
void _travelDFS(int i, vector<bool>& isVisited);
//辅助广度优先遍历DFS的子函数:以beginV顶点为起始点进行广度优先搜索
void _traveBFS(const V& beginV, vector<bool>& isVisited);
//初始化reGraph用的函数，将当前图的顶点拷贝到reGraph上，但是不拷贝边。
//用于使用reGraph来作为最小生成树的返回结果图
void initReGraph(Self& reGraph)
{
//初始化reGraph数组
reGraph._vertex = _vertex;
reGraph._vToi = _vToi;
int n = _vertex.size();
reGraph._matrix.resize(n);
for (int i = 0; i < n; i++)
{
reGraph._matrix[i].resize(n);
for (int j = 0; j < n; j++)
{
reGraph._matrix[i][j] = W_MAX;
}
_matrix[i][i] = 0; //对角线位置的权值设为0
}
}
public:
//构造函数 用n个顶点初始化图
Graph(const V* vArr, int n, bool hasDir = false);
//为顶点 v1 v2添加边
//把无权图视为有权图，即使用有权图表示无权图.
//如果是无权图，在添加边时，则使用1作为边的权值加入。
bool addEdge(const V& v1, const V& v2, int wt = 1);
//打印邻接矩阵
void printMatrix();
//DFS深度优先遍历
void traveDFS(const V& beginV);
//图的广度优先遍历 BFS
void traveBFS(const V& beginV);
//获取该图的最小生成树 Kruskal,图的类型为无向图
bool Kruskal(Self& reGraph)
{
//初始化reGraph数组,用于将生成树作为输出型参数返回
initReGraph(reGraph);
int n = _vertex.size();
//使用优先级队列存在E中取出权值由小到大的边
priority_queue<Edge, vector<Edge>, greater<Edge>> minEdge;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < i; j++) // j < i 防止存入 i == j 和 对称重复的边
{
if (_matrix[i][j] != W_MAX)
{
minEdge.push(Edge(i, j, _matrix[i][j]));
}
}
}
//每次迭代选出权值最小的两条边
//使用并查集判断该条边的邻接顶点是否在一个连通分量上，如果是就舍弃这条边，否则就将该边添加到reGraph中
int edgeCount = 0; //最小生成树当前的边数
MyUFSet::UFSet ufs(n); //自己实现的并查集
int totalW = 0; //计算总权值
while (!minEdge.empty() && edgeCount != n - 1)
{
int source = (minEdge.top())._source;
int dest = (minEdge.top())._dest;
int wt = (minEdge.top())._wt;
minEdge.pop(); //弹出该条边
if (!ufs.IsTogether(source, dest)) //端点不在同一个连通分量上
{
reGraph._matrix[source][dest] = wt;
reGraph._matrix[dest][source] = wt;
ufs.Union(source, dest); //合并成一个连通分量
edgeCount++;
totalW += wt;
cout << "加入边：(" << source << ", " << dest << ") " << wt << endl;
}
else
{
cout << "舍弃边：(" << source << ", " << dest << ") " << wt << endl;
}
}
cout << "总权值" << totalW << endl;
//n个顶点的连通图最终的最小生成树有 n - 1条边
if (edgeCount != n - 1)
return false;
else
return true;
}
};
}main.cpp
#include <iostream>
#include <cstring>
#include "Graph.h"
using namespace std;
//测试Kruskal算法
void test5()
{
char str[] = "0123456";
MyGraph::Graph<char> g(str, strlen(str));
MyGraph::Graph<char> reGraph(nullptr, 0); //空图,用于接收返回的图
g.addEdge('0', '1', 28);
g.addEdge('0', '5', 10);
g.addEdge('1', '6', 14);
g.addEdge('1', '2', 16);
g.addEdge('5', '4', 25);
g.addEdge('6', '4', 24);
g.addEdge('6', '3', 18);
g.addEdge('2', '3', 12);
g.addEdge('4', '3', 22);
g.Kruskal(reGraph);
reGraph.printMatrix();
}
int main()
{
//test1();
test5();
return 0;
}测试用例以及运行结果：
（三）、普里姆（Prim）算法
1、思路讲解
在任意给定的带权图 N = {V, E}，将顶点集合分为两部分： 和
，
表示当前生成树的顶点集合，
是当前不在生成树里的顶点的集合。因为网络是连通的，所以
和
的顶点之间必定会一条或多条边相连，这些边的集合E称之为割边集，删除割边集里的所有边会导致原连通图 N 不连通，割边集里的一条边称之为割边或桥(bridge)。
在每一轮迭代中，挑出所有桥中权值的最小者 (u, v), u ∈ , v ∈
,然后将顶点 v 加入到生成树的顶点集合中
=
∪ {u}，将边 (u, v) 加入到生成树边的集合中，即
=
∪ {(u, v)}。不断重复上述过程，每经过一轮
都会增加一个顶点，当
中含有 n个顶点，
有 n - 1 条边时，最小生成树求解完毕。
下面举例演示该过程：
和Kruskal的算法不同，Prim算法的生成树是从一个顶点开始慢慢从小树长大成大树的，指定生成最小树的起始点不同，最小生成树的结构极有可能不同。
下面来看一下算法的伪代码，分析一下怎么实现：
判断某个顶点在不在最小生成树的集合里，使用一个名为inMST的bool数组标记顶点。
取出代价最小的边我们采用最小堆，也就是优先级队列来解决这个问题，我们每次往生成树中加入一个新的顶点时，我们就把以该顶点为起始点的所有桥更新加入到优先级队列里。
具体的代码实现中，为保证加入的边不会构成环路，我们需要在加入边时判断终点是否在最小生成树的顶点集合里，如果是则舍弃这条边。
2、代码实现
Graph.h
#pragma once
#include <vector>
#include <queue>
#include <unordered_map>
#include <assert.h>
#include <cstdio>
#include "UFSet.h" //自己实现的并查集
//邻接矩阵版本
namespace MyGraph
{
using namespace std;
const int W_MAX = 999; //表示权值的最大值
//边的存储结构，用于给最小堆提供边的存储类型
struct Edge
{
typedef Edge Self;
int _source; //始点
int _dest; //目标点
int _wt; //权值
Edge(int source, int dest, const int wt)
:_source(source), _dest(dest), _wt(wt)
{ }
//重载一系列比较运算符，用于提供最小堆算法进行比较操作
bool operator>(const Self& other) const
{
return _wt > other._wt;
}
bool operator<(const Self& other)const
{
return _wt < other._wt;
}
bool operator==(const Self& other) const
{
return _wt == other._wt;
}
};
//模板参数 V：顶点类型
template<class V>
class Graph
{
private:
typedef vector<vector<int>> Maxtrix; //邻接矩阵
typedef Graph<V> Self; //图自身
Maxtrix _matrix; //邻接矩阵
vector<V> _vertex; //每个下标对应一个顶点，通过下标访问顶点
unordered_map<V, int> _vToi; //顶点元素和下标建立映射关系，可以通过顶点快速找到顶点集合中的对应下标
bool _hasDir; //表示该图为有向图还是无向图,默认为无向图
//通过顶点获得对应映射的下标
int getVertexIndex(const V& v);
//实现深度优先递归的子函数
void _travelDFS(int i, vector<bool>& isVisited);
//辅助广度优先遍历DFS的子函数:以beginV顶点为起始点进行广度优先搜索
void _traveBFS(const V& beginV, vector<bool>& isVisited);
//初始化reGraph用的函数，将当前图的顶点拷贝到reGraph上，但是不拷贝边。
//用于使用reGraph来作为最小生成树的返回结果图
void initReGraph(Self& reGraph)
{
//初始化reGraph数组
reGraph._vertex = _vertex;
reGraph._vToi = _vToi;
int n = _vertex.size();
reGraph._matrix.resize(n);
for (int i = 0; i < n; i++)
{
reGraph._matrix[i].resize(n);
for (int j = 0; j < n; j++)
{
reGraph._matrix[i][j] = W_MAX;
}
_matrix[i][i] = 0; //对角线位置的权值设为0
}
}
public:
//构造函数 用n个顶点初始化图
Graph(const V* vArr, int n, bool hasDir = false);
//为顶点 v1 v2添加边
//把无权图视为有权图，即使用有权图表示无权图.
//如果是无权图，在添加边时，则使用1作为边的权值加入。
bool addEdge(const V& v1, const V& v2, int wt = 1);
//打印邻接矩阵
void printMatrix();
//DFS深度优先遍历
void traveDFS(const V& beginV);
//图的广度优先遍历 BFS
void traveBFS(const V& beginV);
//获取该图的最小生成树 Kruskal,图的类型为无向图
bool Kruskal(Self& reGraph);
//Prim算法获取最小生成树
bool Prim(const V& beginV, Self& reGraph)
{
initReGraph(reGraph);
int n = _vertex.size();
vector<bool> inMST(n, false); //用于标记该下标的顶点是否在最小生成树的顶点集合中
//当前可选的桥(u,v)
// 桥：u ∈ 最小生成树顶点集合V v ∈ 顶点集合V - 最小生成树顶点集合VMST
priority_queue<Edge, vector<Edge>, greater<Edge>> minBridge;
int edgeCount = 0; //当前最小生成树边的个数
//上一次加入最小生成树集合的顶点
int lastIn = getVertexIndex(beginV);
inMST[lastIn] = true;
int totalW = 0; //计算最小生成树的总权值
do
{
//lastIn顶点作为u，不在inMST中的顶点作为v，更新新的桥（u,v）
for (int j = 0; j < n; j++)
{
if (_matrix[lastIn][j] != W_MAX && !inMST[j])
{
minBridge.push(Edge(lastIn, j, _matrix[lastIn][j]));
}
}
//从所有桥中选出最小的桥，更新生成树顶点
while (!minBridge.empty())
{
int source = (minBridge.top())._source;
int dest = (minBridge.top())._dest;
int wt = (minBridge.top())._wt;
minBridge.pop();
if (!inMST[dest]) // v 不在生成树顶点集合里,将v加入顶点集合，边(u, v)加入顶点集合
{
cout << "选择边: (" << source << ", " << dest << ") " << wt << endl;
reGraph._matrix[source][dest] = wt;
reGraph._matrix[dest][source] = wt;
lastIn = dest; //更新最后一个进入最小生成树的顶点，以更新桥
inMST[lastIn] = true; //将该顶点标记为在最小生成树顶点集合中
totalW += wt;
edgeCount++;
break;
}
else
{
cout << "舍弃边: (" << source << ", " << dest << ") " << wt << endl;
}
}
} while (edgeCount < n - 1 && !minBridge.empty());
cout << "总权值：" << totalW << endl;
if (edgeCount != n - 1)
return false;
else
return true;
}
};
}main.cpp
#include <iostream>
#include <cstring>
#include "Graph.h"
using namespace std;
//测试Prim算法
void test6()
{
char str[] = "ABCDEF";
MyGraph::Graph<char> g(str, strlen(str));
MyGraph::Graph<char> reGraph(nullptr, 0); //空图,用于接收返回的图
g.addEdge('A', 'B', 6);
g.addEdge('A', 'C', 1);
g.addEdge('A', 'D', 5);
g.addEdge('B', 'C', 5);
g.addEdge('C', 'D', 5);
g.addEdge('B', 'E', 3);
g.addEdge('C', 'E', 6);
g.addEdge('C', 'F', 4);
g.addEdge('D', 'F', 2);
g.addEdge('E', 'F', 6);
g.Prim('A', reGraph);
reGraph.printMatrix();
}
int main()
{
//test1();
test6();
return 0;
}测试用例以及运行结果：
（四）、两种算法的性能分析
对于n个顶点，e条边的图。
- 若采用邻接表方式表示
- Kruskal算法：O(n + eloge)，该算法适用于稀疏图，即边的数量接近于顶点的数量的情况。
- Prim算法：O(eloge)，该算法适用于稠密图，即边的数量接近于顶点的数量的平方的情况。
- 若采用邻接矩阵方法表示，两种算法的时间复杂度都为
五、最短路径
最短路径的问题是指：从带权图的某一顶点出发（称之为源点 ），找出一条通往另一顶点（称之为终点
）的最短路径，也就是沿路径各边的权值总和达到最小。
（一）、Dijkstra算法
1、思路分析
Dijkstra算法是荷兰计算机科学家迪杰斯特拉给出的求非负权值的单源最短路径的算法。
其按照路径长度的递增次序，逐步产生最短路径。首先求出长度最短的一条路径，然后参照这条最短路径求出长度次短的一条最短路径，依次类推，直到从顶点到其他各终点的最短路径全部求出为止。
具体做法:
设集合 S 存放已经求出的最短路径的终点。以后每求出一条最短路径（
, ...... ,
）， 就将终点
引入一个辅助数组dist（distance），dist[i] 存储从源点
引入一个辅助数组path，对于最短路径(
在每一次求出最短路径之后，其终点
，修改其dist[i]:
，其中 W(k, i)是边(k, j) 的权值。
第0条最短路径为 (
第1条最短路径为 (
。
下一条最短路径为 (
按照上面的方法，我们来看一个求最短路径的实例：
我们以顶点 0 作为源点，求源点到各终点的最短路径。
dist数组变化： 步数 集合S dist[0] dist[1] dist[2] dist[3] dist[4] 解析 1 ∅ 0 ∞ ∞ ∞ ∞ 第0条最短路径为源点到源点本身，对应的dist = 0，将源点0并入 S 2 {0} 0 10 ∞ 30 100 求出了终点0的最短路径，更新dist[1],dist[3],dist[4]，并在V - S中找出下一条最短路径的终点为1 3 {0, 1} 0 10 60 30 100 求出了终点1的最短路径，更新dist[2],并在V - S中找出下一条最短路径的终点为 3 4 {0, 1, 3} 0 10 50 30 90 求出了终点3的最短路径，更新dist[2],dist[4],并在V-S中找出下一条最短路径的终点为 2 5 {0, 1, 3, 2} 0 10 50 30 60 求出了终点2的最短路径，更新dist[4],并在V-S中找出下一条最短路径的终点为 4 6 {0, 1, 3, 2, 4} 0 10 50 30 60 算法结束，对于终点为4的最短路径，其最短路径为dist[4]=60 黄色标志：已确定最短路径的终点 最终我们得到一个存储着最短路径信息的dist和path数组。
path数组 步数 集合S path[0] path[1] path[2] path[3] path[4] 解析 1 ∅ -1 -1 -1 -1 -1 初始化-1作为根，不能再回溯 2 {0} -1 0 -1 0 0 求出终点0的最短路径，修改path[1] = path[3] = path[4] = 0 3 {0, 1} -1 0 1 0 0 求出终点1的最短路径，修改path[2] = 1 4 {0, 1, 3} -1 0 3 0 3 求出终点3的最短路径，修改path[2] = path[4] = 3 5 {0, 1, 3, 2} -1 0 3 0 2 求出终点2的最短路径，更新path[4] = 2,并找出下一条最短路径的终点为 4 6 {0, 1, 3, 2, 4} -1 0 3 0 2 算法结束,对于终点为4的最短路径,根据下标回溯 4<-2<-3<-0
下面来看一下实现该算法的伪代码：
- 初始化： S = ∅， path[i] = -1，dist[i] = ∞， dist[begin] = 0；（i = 1, 2, 3, ..., n，n为顶点个数，begin为始点位置）。
- 找出下一条最短路径的终点k：
![dist[k] = min\begin{Bmatrix} dist[i] \end{Bmatrix}, i \in V - S;](https://latex.csdn.net/eq?dist%5Bk%5D%20%3D%20min%5Cbegin%7BBmatrix%7D%20dist%5Bi%5D%20%5Cend%7BBmatrix%7D%2C%20i%20%5Cin%20V%20-%20S%3B)
- 修改：
如果dist[i]的值发生变动，则更新path[i] = k。
- 判断：若 S = V，则算法结束，否则转到第二步继续执行。
2、代码实现
Graph.h
#pragma once
#include <vector>
#include <queue>
#include <unordered_map>
#include <assert.h>
#include <cstdio>
#include "UFSet.h" //自己实现的并查集
//邻接矩阵版本
namespace MyGraph
{
using namespace std;
const int W_MAX = 999; //表示权值的最大值
//边的存储结构，用于给最小堆提供边的存储类型
struct Edge
{
typedef Edge Self;
int _source; //始点
int _dest; //目标点
int _wt; //权值
Edge(int source, int dest, const int wt)
:_source(source), _dest(dest), _wt(wt)
{ }
//重载一系列比较运算符，用于提供最小堆算法进行比较操作
bool operator>(const Self& other) const
{
return _wt > other._wt;
}
bool operator<(const Self& other)const
{
return _wt < other._wt;
}
bool operator==(const Self& other) const
{
return _wt == other._wt;
}
};
//模板参数 V：顶点类型
template<class V>
class Graph
{
private:
typedef vector<vector<int>> Maxtrix; //邻接矩阵
typedef Graph<V> Self; //图自身
Maxtrix _matrix; //邻接矩阵
vector<V> _vertex; //每个下标对应一个顶点，通过下标访问顶点
unordered_map<V, int> _vToi; //顶点元素和下标建立映射关系，可以通过顶点快速找到顶点集合中的对应下标
bool _hasDir; //表示该图为有向图还是无向图,默认为无向图
//通过顶点获得对应映射的下标
int getVertexIndex(const V& v);
//实现深度优先递归的子函数
void _travelDFS(int i, vector<bool>& isVisited);
//辅助广度优先遍历DFS的子函数:以beginV顶点为起始点进行广度优先搜索
void _traveBFS(const V& beginV, vector<bool>& isVisited);
//初始化reGraph用的函数，将当前图的顶点拷贝到reGraph上，但是不拷贝边。
//用于使用reGraph来作为最小生成树的返回结果图
void initReGraph(Self& reGraph);
void readShortPath(int beginI, vector<int>& dist, vector<int>& path)
{
int n = _vertex.size();
for (int i = 0; i < n; i++)
{
if (i != beginI)
{
cout << _vertex[beginI] << "->" << _vertex[i] << "的最短路径: ";
int cur = i;
while (cur != -1)
{
cout << _vertex[cur] << " <- ";
cur = path[cur];
}
cout << " 路径长度：" << dist[i] << endl;
}
}
}
public:
//构造函数 用n个顶点初始化图
Graph(const V* vArr, int n, bool hasDir = false);
//为顶点 v1 v2添加边
//把无权图视为有权图，即使用有权图表示无权图.
//如果是无权图，在添加边时，则使用1作为边的权值加入。
bool addEdge(const V& v1, const V& v2, int wt = 1);
//打印邻接矩阵
void printMatrix();
//DFS深度优先遍历
void traveDFS(const V& beginV);
//图的广度优先遍历 BFS
void traveBFS(const V& beginV);
//获取该图的最小生成树 Kruskal,图的类型为无向图
bool Kruskal(Self& reGraph);
//Prim算法获取最小生成树
bool Prim(const V& beginV, Self& reGraph);
//Dijkstra算法求非负权值的最短路径
void Dijsktra(const V& beginV)
{
int n = _vertex.size();
int beginI = getVertexIndex(beginV);
vector<int> dist;
vector<int> path;
dist.resize(n);
path.resize(n);
for (int j = 0; j < n; j++)
{
//初始化父路径数组，用于回溯找出某个顶点的最短路径 -1代表根
path[j] = -1;
//初始化dist最短路径值为无穷
dist[j] = W_MAX;
}
dist[beginI] = 0; //一开始自己到自己路径长度最短
//最短路径顶点的集合S，初始化为空集
vector<bool> mSet(n, false);
//使用dijkstra逐步求出最短路径
for (int i = 0; i < n; i++)
{
int minW = W_MAX;
int minI = beginI; //找出下一条最短路径的终点minI
for (int j = 0; j < n; j++)
{
if (!mSet[j] && dist[j] < minW)
{
minW = dist[j];
minI = j;
}
}
mSet[minI] = true; //将该最短路径终点加入到已确定最短路径的终点集合S里
//更新从该终点minI出发到其他终点的最短路径长度dist，如果有更小的权值就更新
for (int j = 0; j < n; j++)
{
if (!mSet[j] &&
_matrix[minI][j] != W_MAX &&
dist[minI] + _matrix[minI][j] < dist[j])
{
dist[j] = dist[minI] + _matrix[minI][j];
path[j] = minI;
}
}
}
//解析最短路径
readShortPath(beginI, dist, path);
}
};
}main.h
#include <iostream>
#include <cstring>
#include "Graph.h"
using namespace std;
//测试Dijkstra算法
void test7()
{
char str[] = "01234";
MyGraph::Graph<char> g(str, strlen(str), true);
g.addEdge('0', '1', 10);
g.addEdge('0', '3', 30);
g.addEdge('0', '4', 100);
g.addEdge('1', '2', 50);
g.addEdge('2', '4', 10);
g.addEdge('3', '4', 60);
g.addEdge('3', '2', 20);
g.Dijsktra('0');
}
int main()
{
//test1();
test7();
return 0;
}测试用例和运行结果：
（二）、Bellman-Ford算法
Dijkstra算法只能求非负权值的单源最短路径。对于有负权值的图，使用该算法并不一定能够求出正确的最短路径。如下面这个例子：
如果使用 Dijkstra 算法，以始点0出发计算该图的最短路径，那么第一条最短路径的终点就会被确定为2, 路径为 0->2,权值为5，后面不会再更新终点2的最短路径。但是我们知道这条路径并不是最短的，最短的路径应该是 0->1->2，权值为2。
为了能够求解带负权值的单源最短路径问题， Bellman和Ford提出了从源点逐次绕过其他顶点，以缩短到达终点的最短路径长度的方法，刚方法必须要求图中不能够有带负权值的边组成的回路，如下面这个图：
回路：0->1->0,每绕一圈回路，总路径长度就会减少1。，无法求出最短路径。
下面来讲解一下 Bellman-Ford算法的思路。
1、算法思路
对于有 n 个顶点的图中任意两个顶点若有最短路径，则最短路径最多有 n - 1 条边，因为如果有超过 n - 1 条边，那么就一定会形成回路。该算法可以将这任意两个顶点之间经过的不超过 n - 1条边的所有可能存在的最短路径都依次比对一遍，最终得到最短的那一条路径。
构造一个最短路径长度的数组序列
，
序列。
设已经求出了
， 即从源点 v 出发到达终点j的最多经过 k - 1 条边的的最短路径的长度，那么找到各个顶点 j 到达顶点 u 的权值W(j, u)，计算
，得到从源点 v 出发绕过各个顶点，经过最多k条边到达终点 u 的可能最短路径长度，我们将该值和
做比较，取较小者作为
由此得到
![dist^{1}[u] = W(v, u)](https://latex.csdn.net/eq?dist%5E%7B1%7D%5Bu%5D%20%3D%20W%28v%2C%20u%29)
![dist^{k}[u] = \min \begin{Bmatrix} dist^{k-1}[u], \min (dist^{k-1}[j] + W(j, u) ) \end{Bmatrix}](https://latex.csdn.net/eq?dist%5E%7Bk%7D%5Bu%5D%20%3D%20%5Cmin%20%5Cbegin%7BBmatrix%7D%20dist%5E%7Bk-1%7D%5Bu%5D%2C%20%5Cmin%20%28dist%5E%7Bk-1%7D%5Bj%5D%20+%20W%28j%2C%20u%29%20%29%20%5Cend%7BBmatrix%7D)
示例：
k dist^k[0] dist^k[1] dist^k[2] dist^k[3] dist^k[4] dist^k[5] dist^k[6] 解析 0 0 ∞ ∞ ∞ ∞ ∞ ∞ 经过0条边的最短路径长度 1 0 6 5 5 ∞ ∞ ∞ 对于顶点1，可以绕过顶点0、2到达，选择 0->1；对于顶点2，可以绕过顶点0、3到达，选择0->2
2 0 3 3 5 5 4 ∞ 对于顶点1，可以绕过顶点0、2到达，选择 2->1；对于顶点2，可以绕过顶点0、3到达，选择3->2；对于顶点4，可以绕过顶点1、2到达，选择1->4；对于顶点5，可以绕过顶点3到达，选择3->5 3 0 1 3 5 2 4 7 最多经过3条边，得到的最短路径长度 4 0 1 3 5 0 4 5 最多经过4条边，得到的最短路径长度 5 0 1 3 5 0 4 3 最多经过5条边，得到的最短路径长度 6 0 1 3 5 0 4 3 最多经过6条边，得到的最短路径长度 黄色标识：发生改动的最短路径终点
步数 path[0] path[1] path[2] path[3] path[4] path[5] path[6] 0 -1 -1 -1 -1 -1 -1 -1 1 -1 0 0 0 -1 -1 -1 2 -1 2 3 0 1 3 -1 3 -1 2 3 0 1 3 5 4 -1 2 3 0 1 3 4 5 -1 2 3 0 1 3 4 6 -1 2 3 0 1 3 4 对于终点为4的结点，最短路径为4<-1<-2<-3<-0
下面来分析算法的代码实现：
- 按照递推公式，进行n - 1轮迭代，每一轮对
进行更新，得到
- 若更新一轮发现
- 若n - 1轮迭代后，还能继续更新出新的
2、代码实现
Graph.h:
#pragma once
#include <vector>
#include <queue>
#include <unordered_map>
#include <assert.h>
#include <cstdio>
#include "UFSet.h" //自己实现的并查集
//邻接矩阵版本
namespace MyGraph
{
using namespace std;
const int W_MAX = 999; //表示权值的最大值
//边的存储结构，用于给最小堆提供边的存储类型
struct Edge
{
typedef Edge Self;
int _source; //始点
int _dest; //目标点
int _wt; //权值
Edge(int source, int dest, const int wt)
:_source(source), _dest(dest), _wt(wt)
{ }
//重载一系列比较运算符，用于提供最小堆算法进行比较操作
bool operator>(const Self& other) const
{
return _wt > other._wt;
}
bool operator<(const Self& other)const
{
return _wt < other._wt;
}
bool operator==(const Self& other) const
{
return _wt == other._wt;
}
};
//模板参数 V：顶点类型
template<class V>
class Graph
{
private:
typedef vector<vector<int>> Maxtrix; //邻接矩阵
typedef Graph<V> Self; //图自身
Maxtrix _matrix; //邻接矩阵
vector<V> _vertex; //每个下标对应一个顶点，通过下标访问顶点
unordered_map<V, int> _vToi; //顶点元素和下标建立映射关系，可以通过顶点快速找到顶点集合中的对应下标
bool _hasDir; //表示该图为有向图还是无向图,默认为无向图
//通过顶点获得对应映射的下标
int getVertexIndex(const V& v);
//实现深度优先递归的子函数
void _travelDFS(int i, vector<bool>& isVisited);
//辅助广度优先遍历DFS的子函数:以beginV顶点为起始点进行广度优先搜索
void _traveBFS(const V& beginV, vector<bool>& isVisited);
//初始化reGraph用的函数，将当前图的顶点拷贝到reGraph上，但是不拷贝边。
//用于使用reGraph来作为最小生成树的返回结果图
void initReGraph(Self& reGraph);
void readShortPath(int beginI, vector<int>& dist, vector<int>& path);
public:
//构造函数 用n个顶点初始化图
Graph(const V* vArr, int n, bool hasDir = false);
//为顶点 v1 v2添加边
//把无权图视为有权图，即使用有权图表示无权图.
//如果是无权图，在添加边时，则使用1作为边的权值加入。
bool addEdge(const V& v1, const V& v2, int wt = 1);
//打印邻接矩阵
void printMatrix();
//DFS深度优先遍历
void traveDFS(const V& beginV);
//图的广度优先遍历 BFS
void traveBFS(const V& beginV);
//获取该图的最小生成树 Kruskal,图的类型为无向图
bool Kruskal(Self& reGraph);
//Prim算法获取最小生成树
bool Prim(const V& beginV, Self& reGraph);
//Dijkstra算法求非负权值的最短路径
void Dijsktra(const V& beginV);
//Bellman_Ford 算法求最短路径
bool Bellman_Ford(const V& beginV)
{
int n = _vertex.size();
int beginI = getVertexIndex(beginV);
vector<int> dist;
vector<int> path;
dist.resize(n);
path.resize(n);
for (int j = 0; j < n; j++)
{
//初始化父路径数组，用于回溯找出某个顶点的最短路径 -1代表根
path[j] = -1;
//初始化dist最短路径值都为无穷
dist[j] = W_MAX;
}
dist[beginI] = 0; //自己到自己的路径长度为最小
bool isRenew = false; //如果执行一轮后各个终点的最短路径没有发生变化，那么以后也不会有了，可以提前跳出
for (int k = 0; k < n; k++)
{
isRenew = false;
//计算使用当前不超过k - 1条边的最短路径终点j的 权值 与 j到u的权值 W(j,u) 之和
// 该和代表的意义：从源点 v 出发到终点j的最短路径，再从j 邻接到 u 的 路径
//将计算出的权值之和 与 顶点u当前最短路径值 作比较
//如果该和比到u的现有的最短路径值要小，就更新路径
for (int u = 0; u < n; u++)
{
for (int j = 0; j < n; j++)
{
if (_matrix[j][u] != W_MAX && dist[j] + _matrix[j][u] < dist[u])
{
dist[u] = dist[j] + _matrix[j][u];
path[u] = j;
isRenew = true;
}
}
}
if (!isRenew)
{
//cout << "已求出最短路径，提前跳出" << "k = " << k << " n = " << n << endl;
break;
}
}
//检测是否有带负权值的环路，如果有的话下面会继续无限更新，那就无法找到最短路径
for (int u = 0; u < n; u++)
{
for (int j = 0; j < n; j++)
{
if (_matrix[j][u] != W_MAX && dist[j] + _matrix[j][u] < dist[u]) //还能继续更新，说明有负权回路
{
return false;
}
}
}
readShortPath(beginI, dist, path);
return true;
}
};
}main.cpp:
#include <iostream>
#include <cstring>
#include "Graph.h"
using namespace std;
//测试Bellman-Ford算法
void test8()
{
char str[] = "0123456";
MyGraph::Graph<char> g(str, strlen(str), true);
g.addEdge('0', '1', 6);
g.addEdge('0', '2', 5);
g.addEdge('0', '3', 5);
g.addEdge('1', '4', -1);
g.addEdge('2', '4', 1);
g.addEdge('2', '1', -2);
g.addEdge('3', '2', -2);
g.addEdge('3', '5', -1);
g.addEdge('4', '6', 3);
g.addEdge('5', '6', 3);
g.Bellman_Ford('0');
}
int main()
{
//test1();
test8();
return 0;
}测试用例和运行结果：
（三）、floyd算法
前面的两个算法都是求单源最短路径，即从某个始点出发到达任意顶点的最短路径。若想得出任意一对顶点的最短路径，则需要将每个顶点作为始点进行一次Dijkstra算法，时间复杂度为O(n^3)。而下面要介绍的Floyd算法可以求出任意两个顶点之间的最短路径（不带负权回路的图），时间复杂度也为O(n^3)。
1、算法思路
该算法使用了动态规划的思想，首先需要创建一个二维数组 dist[i][j]，用于存储任意两个顶点之间的最短路径长度，dist[i][j] 表示顶点 i 到顶点 j 的最短路径长度。初始化时，对角线的元素为 0 ，其他元素都为 W_MAX，即权值的最大值。以后逐步尝试在原最短路径 dist[i][j] 中加入其他最短路径的顶点 k 作为中间顶点，如果增加中间顶点后，得到的路径 dist[i][k] + dist[k][j] 比原来的最短路径 dist[i][j] 小，那么则以此新的最短路径 i - > k -> j 代替原路径 i -> j。
算法的伪代码：
初始化：dist[i][i] = 0,若 i 和 j 有边，则 dist[i][j] = W(i，j)， 其余 dist[i][j] = W_MAX， (i,j = 1, 2,......, n, n为图的顶点个数，W(i，j)为i和j边的权值)。
迭代：
分别遍历每一个顶点 k，将顶点 k 作为中间顶点，更新dist数组。
对于每一对顶点 i 和 j，如果 dist[i][k] + dist[k][j] < dist[i][j]，则 dist[i][j] = dist[i][k] + dist[k][j] 并且更新 path[i][j] = path[k][j]（dist[i][j]的最短路径是通过 i -> k -> j，即 i 到 k 的最短路径，再从 k 到 j 的最短路径得来的，所以 path[i][j] 要能回溯到 k 顶点，即 path[i][j] = path[k][j]）
最终：dist数组中存储的就是每对顶点之间的最短路径长度，path数组存储了每对顶点的最短路径。
2、代码实现
Graph.h
#pragma once
#include <vector>
#include <queue>
#include <unordered_map>
#include <assert.h>
#include <cstdio>
#include "UFSet.h" //自己实现的并查集
//邻接矩阵版本
namespace MyGraph
{
using namespace std;
const int W_MAX = 999; //表示权值的最大值
//边的存储结构，用于给最小堆提供边的存储类型
struct Edge
{
typedef Edge Self;
int _source; //始点
int _dest; //目标点
int _wt; //权值
Edge(int source, int dest, const int wt)
:_source(source), _dest(dest), _wt(wt)
{ }
//重载一系列比较运算符，用于提供最小堆算法进行比较操作
bool operator>(const Self& other) const
{
return _wt > other._wt;
}
bool operator<(const Self& other)const
{
return _wt < other._wt;
}
bool operator==(const Self& other) const
{
return _wt == other._wt;
}
};
//模板参数 V：顶点类型
template<class V>
class Graph
{
private:
typedef vector<vector<int>> Maxtrix; //邻接矩阵
typedef Graph<V> Self; //图自身
Maxtrix _matrix; //邻接矩阵
vector<V> _vertex; //每个下标对应一个顶点，通过下标访问顶点
unordered_map<V, int> _vToi; //顶点元素和下标建立映射关系，可以通过顶点快速找到顶点集合中的对应下标
bool _hasDir; //表示该图为有向图还是无向图,默认为无向图
//通过顶点获得对应映射的下标
int getVertexIndex(const V& v);
//实现深度优先递归的子函数
void _travelDFS(int i, vector<bool>& isVisited);
//辅助广度优先遍历DFS的子函数:以beginV顶点为起始点进行广度优先搜索
void _traveBFS(const V& beginV, vector<bool>& isVisited);
//初始化reGraph用的函数，将当前图的顶点拷贝到reGraph上，但是不拷贝边。
//用于使用reGraph来作为最小生成树的返回结果图
void initReGraph(Self& reGraph);
void readShortPath(int beginI, vector<int>& dist, vector<int>& path);
public:
//构造函数 用n个顶点初始化图
Graph(const V* vArr, int n, bool hasDir = false);
//为顶点 v1 v2添加边
//把无权图视为有权图，即使用有权图表示无权图.
//如果是无权图，在添加边时，则使用1作为边的权值加入。
bool addEdge(const V& v1, const V& v2, int wt = 1);
//打印邻接矩阵
void printMatrix();
//DFS深度优先遍历
void traveDFS(const V& beginV);
//图的广度优先遍历 BFS
void traveBFS(const V& beginV);
//获取该图的最小生成树 Kruskal,图的类型为无向图
bool Kruskal(Self& reGraph);
//Prim算法获取最小生成树
bool Prim(const V& beginV, Self& reGraph);
//Dijkstra算法求非负权值的最短路径
void Dijsktra(const V& beginV);
//Bellman_Ford 算法求最短路径
bool Bellman_Ford(const V& beginV);
bool Floyd()
{
int n = _vertex.size();
vector<vector<int>> vvDist; //vvDist[i][j] 表示从顶点i到顶点j的最短路径
vector<vector<int>> vvPath; //vvPath[i][j] 表示从顶点i到顶点j的最短路径的父路径
vvDist.resize(n);
vvPath.resize(n);
//初始化二维数组
for (int i = 0; i < n; i++)
{
vvDist[i].resize(n, W_MAX);
vvPath[i].resize(n, -1);
for (int j = 0; j < n; j++)
{
if (_matrix[i][j] != W_MAX)
{
vvDist[i][j] = _matrix[i][j];
vvPath[i][j] = i;
}
}
//自己到自己的路径值最短
vvDist[i][i] = 0;
vvPath[i][i] = -1;
}
//使用floyd算法求 任意两点的最短路径
//每轮检测一下每个顶点i 经过顶点 k（0，1,2,3,4,.....n） 到顶点j 是否能产生最短路径 ，如果能，则更新最短路径
// 最终检测了顶点i 经过所有的顶点k 到j的路径长度， 产生出的最短路径
for (int k = 0; k < n; k++)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (vvDist[i][k] + vvDist[k][j] < vvDist[i][j])
{
vvDist[i][j] = vvDist[i][k] + vvDist[k][j];
vvPath[i][j] = vvPath[k][j];
}
}
}
}
//解读最短路径
for (int i = 0; i < n; i++)
{
readShortPath(i, vvDist[i], vvPath[i]);
cout << endl;
}
return true;
}
};
}main.cpp
#include <iostream>
#include <cstring>
#include "Graph.h"
using namespace std;
//测试Floyd算法
void test9()
{
char str[] = "0123";
MyGraph::Graph<char> g(str, strlen(str), true);
g.addEdge('0', '1', 1);
g.addEdge('0', '3', 4);
g.addEdge('1', '2', 9);
g.addEdge('1', '3', 2);
g.addEdge('2', '0', 3);
g.addEdge('2', '1', 5);
g.addEdge('2', '3', 8);
g.addEdge('3', '2', 6);
g.Floyd();
}
int main()
{
test9();
return 0;
}测试用例以及测试结果：
六、AOV网络、拓扑排序
1、概念与算法思路
有向图可以表示一个工程。在这种有向图中，用顶点表示活动，用有向边 <u, v> 表示活动 u 必须先于活动 v 进行。这种有向图称为顶点表示活动的网络图（activity on vertices network，AOV网络）。例如下面这个学生选修课程学习的图，每个课程之间具有先修和后修的次序，具有反自反性、反对称性和传递性，可以算为没有自反性的偏序关系。
在AOV网络表示的有向图中，不能有有向回路，如果存在这样的回路则表明某个活动以自己为先决条件，这是不对的，这样的工程图存在问题，对程序而言会造成死循环，所以我们首先要判定一个AOV网络是否存在有向环。
检查有向环需要使用拓扑排序有序序列，将各个顶点排成一个线性有序的序列，使得AOV网络中所有活动的前驱和后驱关系在这个有序序列中都能够得到满足，这种运算叫做拓扑排序（topological sorting）。若拓扑排序后的有序序列的顶点个数和工程图中的活动个数相同，那么该工程图不存在有向环。
图 (c) 是图 (a) 的拓扑排序后的一个有序序列，在这个序列中，每对活动之间的前驱后驱关系都能满足原图 (a)，并且对于没有前驱和后驱关系的活动 C1 和 C2，我们也人为的增加了前驱后驱关系。
拓扑排序的步骤：
输入AOV网络，建立对应工程的有向图。
- 在有向图中找到一个入度为0的顶点并直接输出。
- 从图中删去该顶点，同时删去以该顶点为始点的有向边。
- 重复上述步骤，直到图中没有入度为0的顶点可以输出为止。
下面是上述过程的一个例子：
上述过程的算法我们需要使用一个 inDegree[i] 的数组，表示顶点 i 的入度，下面是该算法的伪代码：
该过程需要使用栈，我们可以重复利用 inDegree[] 这个数组来实现栈的功能， inDegree 既可以表示某个顶点的入度，又维护着一个链栈，当 inDegree 不再充当表示入度的功能时， inDegree 充当栈的角色， inDegree[i] 记录的是栈中上一个栈元素的下标，可以节省空间。栈初始化时设置 top = -1，表示栈为空，top指向栈顶元素的下标。
入栈： inDegree[i] = top; top = i；
出栈： v = top， top = inDegree[top]；
在某些场景中，我们还需要用到逆拓扑排序，我们可以将拓扑有序中输出的栈顶元素用另一个栈维护，该栈仍然存储在 inDegree[] 数组中。 例如，逆拓扑排序维护的栈一开始初始化栈顶 link = -1，当拓扑排序输出栈顶元素 top 时，我们可以将其链入我们的逆拓扑排序的栈中，即：inDegree[top] = link; link = top。这样，拓扑排序完成后，link 维护的栈就是一个逆拓扑排序序列。
2、代码实现：
Graph.h
#pragma once
#include <vector>
#include <queue>
#include <unordered_map>
#include <assert.h>
#include <cstdio>
#include "UFSet.h" //自己实现的并查集
//邻接矩阵版本
namespace MyGraph
{
using namespace std;
const int W_MAX = 999; //表示权值的最大值
//边的存储结构，用于给最小堆提供边的存储类型
struct Edge
{
typedef Edge Self;
int _source; //始点
int _dest; //目标点
int _wt; //权值
Edge(int source, int dest, const int wt)
:_source(source), _dest(dest), _wt(wt)
{ }
//重载一系列比较运算符，用于提供最小堆算法进行比较操作
bool operator>(const Self& other) const
{
return _wt > other._wt;
}
bool operator<(const Self& other)const
{
return _wt < other._wt;
}
bool operator==(const Self& other) const
{
return _wt == other._wt;
}
};
//模板参数 V：顶点类型
template<class V>
class Graph
{
private:
typedef vector<vector<int>> Maxtrix; //邻接矩阵
typedef Graph<V> Self; //图自身
Maxtrix _matrix; //邻接矩阵
vector<V> _vertex; //每个下标对应一个顶点，通过下标访问顶点
unordered_map<V, int> _vToi; //顶点元素和下标建立映射关系，可以通过顶点快速找到顶点集合中的对应下标
bool _hasDir; //表示该图为有向图还是无向图,默认为无向图
//通过顶点获得对应映射的下标
int getVertexIndex(const V& v);
//实现深度优先递归的子函数
void _travelDFS(int i, vector<bool>& isVisited);
//辅助广度优先遍历DFS的子函数:以beginV顶点为起始点进行广度优先搜索
void _traveBFS(const V& beginV, vector<bool>& isVisited);
//初始化reGraph用的函数，将当前图的顶点拷贝到reGraph上，但是不拷贝边。
//用于使用reGraph来作为最小生成树的返回结果图
void initReGraph(Self& reGraph);
void readShortPath(int beginI, vector<int>& dist, vector<int>& path);
public:
//构造函数 用n个顶点初始化图
Graph(const V* vArr, int n, bool hasDir = false);
//为顶点 v1 v2添加边
//把无权图视为有权图，即使用有权图表示无权图.
//如果是无权图，在添加边时，则使用1作为边的权值加入。
bool addEdge(const V& v1, const V& v2, int wt = 1);
//打印邻接矩阵
void printMatrix();
//DFS深度优先遍历
void traveDFS(const V& beginV);
//图的广度优先遍历 BFS
void traveBFS(const V& beginV);
//获取该图的最小生成树 Kruskal,图的类型为无向图
bool Kruskal(Self& reGraph);
//Prim算法获取最小生成树
bool Prim(const V& beginV, Self& reGraph);
//Dijkstra算法求非负权值的最短路径
void Dijsktra(const V& beginV);
//Bellman_Ford 算法求最短路径
bool Bellman_Ford(const V& beginV);
//Floyd算法求任意两个顶点的最短路径
bool Floyd();
//拓扑排序算法
bool TopologicalSort()
{
int n = _vertex.size();
vector<int> inDegree(n, 0);
int top = -1; //栈顶的下标，直接在inDegree里建立链栈，不额外开空间
//计算每个顶点的入度，保存到数组中
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (i != j && _matrix[j][i] != W_MAX)
{
inDegree[i]++; //i顶点的入度++
}
}
if (inDegree[i] == 0) //入度为0的顶点加入栈中
{
//入栈
inDegree[i] = top; //记录上一个栈顶的下标
top = i;
}
}
//拉链，将每次出栈的元素又重新压回栈，最终得到逆拓扑有序序列
int link = -1;
int count = 0; //拓扑排序输出的顶点个数，若排序结束count不等于n则工程有问题，带有环
while (top != -1)
{
int topV = top;
//出栈
top = inDegree[top];
//拉链，维护另一个栈，其出栈顺序为逆拓扑有序
inDegree[topV] = link;
link = topV;
cout << _vertex[topV] << " ";
count++;
//将顶点topV的邻接顶点的入度减一，如果邻接顶点减为0，则入栈
for (int i = 0; i < n; i++)
{
//满足topV 和 i 有边, AOV图具有反自反性
if (_matrix[topV][i] != W_MAX && _matrix[topV][i] != 0)
{
inDegree[i]--;
if (inDegree[i] == 0)
{
inDegree[i] = top;
top = i;
}
}
}
}
cout << endl;
//输出逆拓扑有序
while (link != -1)
{
int topV = link;
//出栈
link = inDegree[link];
cout << _vertex[topV] << " ";
}
cout << endl;
if (count != n)
return false;
else
return true;
}
};
}main.cpp
#include <iostream>
#include <cstring>
#include "Graph.h"
using namespace std;
void test10()
{
char str[] = "012345"; //c0 c1 c2 c3 c4 c5
MyGraph::Graph<char> g(str, strlen(str), true);
g.addEdge('0', '1');
g.addEdge('0', '3');
g.addEdge('1', '5');
g.addEdge('2', '1');
g.addEdge('2', '5');
g.addEdge('4', '0');
g.addEdge('4', '1');
g.addEdge('4', '5');
g.TopologicalSort();
}
int main()
{
test10();
return 0;
}测试用例以及测试结果：
七、AOE网络
1、思路讲解
在AOE网络中，使用有向边表示一个工程的各项活动（active），用有向边上的权值表示活动的持续时间（duration），用顶点表示事件（event），这样的有向图称为用边表示活动的网络（active on edge network，AOE网络）。下面是一个AOE网络的实例：
在该图中，只有一个入度为0顶点，是工程的开始点（源点），一个出度为 0 的顶点，是工程的结束点（汇点）。
在一个AOE网络中我们需要分析出整个工程完工所需要的时间，工程的完工时间取决于关键路径的长度。从源点开始到达汇点的有向路径可能不止一条，只有这些有向路径上的活动都被完成了，整个工程才能完成，所以整个工程完成的时间取决于从源点到汇点的路径中最长的路径，这条路径上活动的时间之和就是工程的完工时间，该路径称为关键路径（critical path）。上面图中存在两条关键路径为：a1, a4, a7, a10 或 a1, a4, a8, a11，路径长度为18，所以该工程的完工时间为18。
要找出关键路径，就得先找出关键活动，即不按期完成就会影响整个工程完工的活动。关键路径上的所有活动都是关键活动，找到了关键活动就能找到关键路径。下面来定义几个与计算关键活动有关的量，设图有n个事件：
事件 Vi 的最早可能开始时间 Ve[i]：Ve[i] 的值为从源点出发到达事件 Vi 的最长路径长度。Ve[n - 1]是整个工程的最早完工时间。
事件 Vi 的最迟允许开始时间 Vl[i]：Vl[i] 的值为 Ve[n - 1] 减去从 Vi 到汇点 Vn-1 的最长路径的长度。
活动 ak 的最早可能开始时间 Ae[k]：设活动 ak 在有向边 <Vi, Vj> 上，则 Ae[k] 的值等于事件 Vi 的最早可能开始时间，即 Ve[i]。
活动 ak 的最迟允许开始时间 Al[k]：设活动 ak 在有向边 <Vi, Vj> 上，则 Al[k] 的值等于事件 Vj 的最迟允许开始时间减去完成活动 ak 所需要的时间（duration(<i，j>)），即 Al[k] = Vl[j] - duration(<i，j>)。
松弛时间（slack time）：Al[k] - Ae[k] 表示活动最早可能开始时间和最迟允许开始事件的时间余量，也称松弛时间，松弛时间为0的活动是关键活动。
要求关键路径，就得求出 Ae[k] 和 Al[k]，要求 Ae[k] 和 Al[k] 就得求 Ve[i] 和 Vl[i]。下面是对应的求Ve[i] 和 Vl[i]的递推公式和算法：
递推公式：
伪代码：
逐步执行算法过程，观察Ve[]和Vl[]的变化：
例子：
最早可能开始时间：
step Ve[0] Ve[1] Ve[2] Ve[3] Ve[4] Ve[5] Ve[6] Ve[7] Ve[8] 解析 栈 1 0 0 0 0 0 0 0 0 0 初始化，将源点入栈进行拓扑排序求Ve 0 2 0 6 4 5 0 0 0 0 0 把顶点0摘下，更新邻接顶点1,2,3 1,2,3 3 0 6 4 5 0 7 0 0 0 把顶点3摘下，更新邻接顶点5 1,2,5 4 0 6 4 5 0 7 0 11 0 把顶点5摘下，更新邻接顶点7 1,2 5 0 6 4 5 5 7 0 11 0 把顶点2摘下，更新邻接顶点4 1 6 0 6 4 5 7 7 0 11 0 把顶点1摘下，更新邻接顶点4 4 7 0 6 4 5 7 7 16 14 0 把顶点4摘下，更新邻接顶点6,7 6,7 8 0 6 4 5 7 7 16 14 18 把顶点7摘下，更新邻接顶点8 6 9 0 6 4 5 7 7 16 14 18 把顶点6摘下，更新邻接顶点8 8 10 0 6 4 5 7 7 16 14 18 把顶点8摘下.算法结束 null 红色标识：当前拓扑排序所选中的元素，依次为 0,3,5,2,1,4,7,6,8 算法执行过程中最早可能开始时间和最迟允许开始时间的变化：
step Vl[0] Vl[1] Vl[2] Vl[3] Vl[4] Vl[5] Vl[6] Vl[7] Vl[8] 解析 栈 1 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 18 初始化，按照逆拓扑排序的顺序求Vl，Vl[8] = Ve[8] 0,3,5,2,1,4,7,6,8 2 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 18 更新顶点8，算 Vl[j] - duration(<8,j>)的最小值 0,3,5,2,1,4,7,6 3 ∞ ∞ ∞ ∞ ∞ ∞ 16 ∞ 18 更新顶点6，算 Vl[j] - duration(<6,j>)的最小值 0,3,5,2,1,4,7 4 ∞ ∞ ∞ ∞ ∞ ∞ 16 14 18 更新顶点7，算 Vl[j] - duration(<7,j>)的最小值 0,3,5,2,1,4 5 ∞ ∞ ∞ ∞ 7 ∞ 16 14 18 更新顶点4，算 Vl[j] - duration(<4,j>)的最小值 0,3,5,2,1 6 ∞ 6 ∞ ∞ 7 ∞ 16 14 18 更新顶点1，算 Vl[j] - duration(<1,j>)的最小值 0,3,5,2 7 ∞ 6 6 ∞ 7 ∞ 16 14 18 更新顶点2，算 Vl[j] - duration(<2,j>)的最小值 0,3,5 8 ∞ 6 6 ∞ 7 10 16 14 18 更新顶点5，算 Vl[j] - duration(<5,j>)的最小值 0,3 9 ∞ 6 6 8 7 10 16 14 18 更新顶点3，算 Vl[j] - duration(<3,j>)的最小值 0 10 0 6 6 8 7 10 16 14 18 更新顶点0，算法结束 null 红色表示：当前更新的Vl
接着按照上面计算出的 Ve[k]和Vl[k] 计算 Ae[k] 和 Al[k]，根据 Ae[k] - Al[k] 是否为 0输出关键活动。
2、代码实现
Graph.h
#pragma once
#include <vector>
#include <queue>
#include <unordered_map>
#include <assert.h>
#include <cstdio>
#include "UFSet.h" //自己实现的并查集
//邻接矩阵版本
namespace MyGraph
{
using namespace std;
const int W_MAX = 999; //表示权值的最大值
//边的存储结构，用于给最小堆提供边的存储类型
struct Edge
{
typedef Edge Self;
int _source; //始点
int _dest; //目标点
int _wt; //权值
Edge(int source, int dest, const int wt)
:_source(source), _dest(dest), _wt(wt)
{ }
//重载一系列比较运算符，用于提供最小堆算法进行比较操作
bool operator>(const Self& other) const
{
return _wt > other._wt;
}
bool operator<(const Self& other)const
{
return _wt < other._wt;
}
bool operator==(const Self& other) const
{
return _wt == other._wt;
}
};
//模板参数 V：顶点类型
template<class V>
class Graph
{
private:
typedef vector<vector<int>> Maxtrix; //邻接矩阵
typedef Graph<V> Self; //图自身
Maxtrix _matrix; //邻接矩阵
vector<V> _vertex; //每个下标对应一个顶点，通过下标访问顶点
unordered_map<V, int> _vToi; //顶点元素和下标建立映射关系，可以通过顶点快速找到顶点集合中的对应下标
bool _hasDir; //表示该图为有向图还是无向图,默认为无向图
//通过顶点获得对应映射的下标
int getVertexIndex(const V& v);
//实现深度优先递归的子函数
void _travelDFS(int i, vector<bool>& isVisited);
//辅助广度优先遍历DFS的子函数:以beginV顶点为起始点进行广度优先搜索
void _traveBFS(const V& beginV, vector<bool>& isVisited);
//初始化reGraph用的函数，将当前图的顶点拷贝到reGraph上，但是不拷贝边。
//用于使用reGraph来作为最小生成树的返回结果图
void initReGraph(Self& reGraph);
void readShortPath(int beginI, vector<int>& dist, vector<int>& path);
public:
//构造函数 用n个顶点初始化图
Graph(const V* vArr, int n, bool hasDir = false);
//为顶点 v1 v2添加边
//把无权图视为有权图，即使用有权图表示无权图.
//如果是无权图，在添加边时，则使用1作为边的权值加入。
bool addEdge(const V& v1, const V& v2, int wt = 1);
//打印邻接矩阵
void printMatrix();
//DFS深度优先遍历
void traveDFS(const V& beginV);
//图的广度优先遍历 BFS
void traveBFS(const V& beginV);
//获取该图的最小生成树 Kruskal,图的类型为无向图
bool Kruskal(Self& reGraph);
//Prim算法获取最小生成树
bool Prim(const V& beginV, Self& reGraph);
//Dijkstra算法求非负权值的最短路径
void Dijsktra(const V& beginV);
//Bellman_Ford 算法求最短路径
bool Bellman_Ford(const V& beginV);
//Floyd算法求任意两个顶点的最短路径
bool Floyd();
//拓扑排序算法
bool TopologicalSort();
//AOE网络：求关键活动
bool CriticalPath()
{
int n = _vertex.size();
vector<int> inDegree(n, 0);
int top = -1; //栈顶下标，为-1代表空栈
//初始化每个顶点的入度
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (i != j && _matrix[j][i] != W_MAX)
{
inDegree[i]++;
}
}
if (inDegree[i] == 0)
{
//入链栈
inDegree[i] = top;
top = i;
}
}
int link = -1; //用来维护逆拓扑有序的另一个链栈
//从拓扑有序中算出 Ve[i]
//第一个事件的最早可能开始时间为0，从该位置开始更新其他位置的Ve
vector<int> Ve(n, 0);
int count = 0; //用于统计拓扑排序得到的序列个数
while (top != -1)
{
int i = top;
top = inDegree[top]; //出栈
//将该顶点压入另一个链栈
inDegree[i] = link;
link = i;
count++;
//更新邻接顶点j的Ve[j] j：<i,j> Ve[j] = Max{Ve[i] + duration(<i,j>) }
for (int j = 0; j < n; j++)
{
if (i != j && _matrix[i][j] != W_MAX)
{
if (Ve[i] + _matrix[i][j] > Ve[j])
{
Ve[j] = Ve[i] + _matrix[i][j];
}
inDegree[j]--; //j入度减少
if (inDegree[j] == 0)
{
inDegree[j] = top;
top = j;
}
}
}
}
//AOV网络有环，工程有问题
if (count != n)
{
cout << "count = " << count << endl;
return false;
}
//通过逆拓扑有序更新出Vl[i]
vector<int> Vl(n, W_MAX);
Vl[link] = Ve[link]; //最终的汇点的最迟允许开始时间等于汇点的最早可能开始时间，
link = inDegree[link]; //退出栈顶元素，从该位置开始计算最迟允许开始事件
while (link != -1)
{
int i = link;
link = inDegree[link];
// 事件i的最迟开始时间 Vl[i] = min{Vl[j] - duration(<i,j>) } i是有向边始点:<i,j>
for (int j = 0; j < n; j++)
{
if (_matrix[i][j] != W_MAX && Vl[j] - _matrix[i][j] < Vl[i])
{
Vl[i] = Vl[j] - _matrix[i][j];
}
}
}
//求关键活动的Ae[i]和Al[j]
for (int i = 0; i < n; i++)
{
//图的每条边表示一个活动a : <i, j>
for (int j = 0; j < n; j++)
{
if (i != j && _matrix[i][j] != W_MAX)
{
int Ae = Ve[i]; //活动<i, j>的最早可能开始时间
int Al = Vl[j] - _matrix[i][j]; //活动<i, j>的最迟允许开始时间
if (Ae == Al) //没有一点松弛时间，为关键活动
{
cout << "关键活动:" << _vertex[i] << "->" << _vertex[j] << endl;
}
}
}
}
return true;
}
};
}main.cpp
#include <iostream>
#include <cstring>
#include "Graph.h"
using namespace std;
//测试AOE网络图，求关键活动
void test11()
{
char str[] = "012345678"; //c0 c1 c2 c3 c4 c5
MyGraph::Graph<char> g(str, strlen(str), true);
g.addEdge('0', '1', 6);
g.addEdge('0', '2', 4);
g.addEdge('0', '3', 5);
g.addEdge('1', '4', 1);
g.addEdge('2', '4', 1);
g.addEdge('3', '5', 2);
g.addEdge('4', '6', 9);
g.addEdge('4', '7', 7);
g.addEdge('5', '7', 4);
g.addEdge('6', '8', 2);
g.addEdge('7', '8', 4);
g.CriticalPath();
}
int main()
{
test11();
return 0;
}测试用例和测试结果
八、参考文献
- 《数据结构（C语言版）》严蔚敏、吴伟民编著。
- 《数据结构（用面向对象方法与C++语言描述）》（第3版）殷人昆编著。
- 《离散数学》古天龙、常亮编著。
本文所引用的图片和测试用例均来源于 《数据结构（C语言版）》和《数据结构（用面向对象方法与C++语言描述）》（第3版）。