好久没有更新简书文章了，今天来跟大家分享以下图的另外一个知识点，也就是“关键路径算法”。顺便向大家分享自己使用邻接矩阵实现的图的基本算法的源代码【有些算法用邻接表会更加节省空间，不过这里小编主要是分享算法实现的逻辑。哈哈，其实就是懒】。
谈到关键路径，那就绕不开AOE网了。
一、AOE网相关概念与性质
图1
我们直接看上图1，这是一个AOE网。AOE网是一个表示工程的带权有向图，其中的顶点用来表示某个事件，弧用来表示活动，弧上的权值用来表示活动持续的时间。
在AOE网中：
（1）始点或源点：入度为0的顶点，它表示一个工程的开始；
（2）终点或汇点：出度为0的顶点，它表示一个工程的结束；
（3）路径长度：路径上各个活动所持续的时间之和；
（4）活动Ai：由弧<vi , vj>表示。弧上的权值用来表示活动持续的时间。
在上图的AOE网中，V1是源点，V9是汇点。
AOE网的性质：
（1）只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始；
（2）只有在进入某顶点的各活动都结束，该顶点所代表的事件才能发生。
关键路径：在AOE网中，从始点到终点具有最大路径长度（该路径上的各个活动所持续的时间之和）的路径称为关键路径。
关键活动：关键路径上的活动称为关键活动。
由于AOE网中的某些活动能够同时进行，故完成整个工程所必须花费的时间应该为始点到终点的最大路径长度。关键路径长度是整个工程所需的最短工期。
二、基本思想
（1）要找出一个AOE网中的关键路径，就要先找出网里的关键活动，这些关键活动间的路径就是关键路径。
（2）判断一个活动是不是关键活动，方法是要先找到所有活动的最早开始时间和最晚开始时间，并且对它们进行比较，如果二者相等（意味着这个活动在该工程中没有时间松动），说明这个活动是关键活动。
（3）对于活动，它最早的开始时间等于事件Vi最早的发生时间earlist[Vi]（事件v的最早发生时间用earlist[v]）。假设E[Vi]表示所有到达顶点Vi的弧的集合，len<Vi, Vj>表示活动<Vi, Vj>的持续时间，那么：
事件Vi最早的发生时间earlist[Vi]
注意，这里假设顶点下标从0开始，所以Vi=0，则表示它是源点，因此最早的开始时间为0；当某个顶点不是源点，那么只有在它前面的事件都发生完后，才能轮到这个事件，所以用了max。
（4）对于活动，它最晚的开始时间等于事件Vj最晚的发生时间减去这个活动的持续事件，即latest[Vj]-len<Vi, Vj>（事件v的最晚的发生时间用latest[v])。假设S[Vj]表示所有从顶点Vj出发的弧的集合，len<Vj, Vk>表示活动<Vj, Vk>的持续时间，那么：
事件Vj最晚的发生时间
（5）活动的最早开始时间用e[i]表示。若活动ai是由弧<Vk , Vj>表示，则活动a的最早开始时间应等于事件Vk的最早发生时间。因此，有：e[i]=earlist[Vk]
（6）活动的最晚开始时间用l[i]表示。活动ai的最晚开始时间是指，在不推迟整个工期的前提下，ai必须开始的最晚时间。若ai由弧<Vk，Vj>表示，则ai的最晚开始时间要保证事件Vj的最迟发生时间不拖后。因此，有：l[i]=latest[Vj]-len<Vk,Vj>
最早时间与最晚时间
活动用时X时间，它最早要从E1时刻开始（一开始就开始），最晚要从L2-X时刻开始（即恰好完成）。所以，如果它是关键活动，则必然有E1=L2-X，也就是e[i]=l[i]，否则它就不是关键活动。
三、例子解析
看了上述这么多文字，可能有点晕，我们结合图1来分析以下。
（一）求出到达各个状态的最早时间（按最大计）
这个过程是要从源点开始向汇点顺推：
1、V1是源点，其最早开始时间是earlist[V1]=0。
2、V2、V3、V4最早时间分别是是earlist[V2]=6、earlist[V3]=4、earlist[V4]=5。
3、对于V5而言，V2到V5所花费时间是earlist[V2]+len<V2,V5>=6+1=7，而V3到V5所花费时间是earlist[V3]+len<V3,V5>=4+1=5。我们要按最大计，也就是V5最早时间是earlist[V5]=max{7,5}=7，按最大计是因为只有活动a4和a5同时完成了，才能到达V5状态。V3到V5需要5分钟，但是此时a4活动尚未完成（7分钟），所以都不能算到达V5，故而要按最大计。
4、V6只有从V4到达，所以V6的最早完成时间是：earlist[V6]=earlist[V4]+len<V4,V6>=5+2=7。
5、同理，V7最早完成时间是earlist[V7]=earlist[V5]+len<V5,V7>=7+9=16。
6、对于V8而言，和V5处理方法一致。
earlist[V8]=max{earlist[V5]+len<V5,V8>,earlist[V6]+len<V6,V8>}=max{7+7,7+4}=14
7、同理V9可算出是earlist[V9]=18。
这样，我们可以得到各个状态的最早时间的表：
状态表1
（二）求出到达各个状态的最晚时间（按最小计）
这个过程是要从汇点开始向源点逆推：
1、V9最早完成时间为18，latest[v9]=earlist[V9]=18则V7最迟开始时间latest[V7]=latest[V9]-len<V7,V9>=18-2=16;
图2
因为活动a10所需时间2。如果V7开始时间比16晚，则V9完成时间就会比18晚，这显然不对。
2、同理，V8最迟开始时间latest[V8]=latest[V9]-len<V8,V9>=18-4=14;
3、对于V5而言，可以从V7、V8两个点开始向前推算，此时要按最小计，即latest[V5]=min{latest[V7]-len<V5,V7>,latest[V8]-len<V5,V8>}=min{16-9,14-7}=7
图3
4、同理，可计算出剩下的点
这样，我们可以得到各个状态的最早和最晚时间的表：
状态表2
事实上，源点和汇点的最晚时间和最早时间必定是相同的。
（三）求出关键路径
求出关键活动，则关键活动所在路径即为关键路径。
1、对于活动a1，最早开始时间e[1]=earlist[V1]=0，最晚开始时间l[1]=latest[V2]-len<V1,V2>=6-6=0。e[1]=l[1]，因此，a1是关键活动。
活动a1
2、对于活动a2，最早开始时间e[2]=earlist[V2]=6，最晚开始时间l[2]=latest[V3]-len<V1,V3>=6-4=2。e[2]!=l[2]，由于a2的开始时间是不定的，所以它不能主导工程的进度，从而它不是关键活动。
活动a2
3、采取相同的方法，可以找到这些关键活动。
关键活动
上表中蓝色底纹表示的点即为处于关键路径的点。尽管它们的最早时间与最晚时间都相同，但是这与它们是否为关键路径的点无关。因为这还取决于起始点的最早时间以及活动时间。
关键路径
四、算法实现
获取图的关键路径，要首先得到该图的一个拓扑序列。一般来说如果结点数量较少，我们采用邻接表来构建图。不过这个地方，小编使用的是邻接矩阵来存储数据，毕竟有关的算法都是在之前的基础上添加上去，小编也就不再把相关的算法使用邻接表实现一遍。不过小编之前有分享过邻接表实现一部分图算法，可以把有关算法添加进去就行。相关的知识可以看小编分享的文章。这里小编也不做过多的解释，直接贴上图的有关算法代码大全。
#include <iostream>
#include <windows.h>
#include<limits.h>
using namespace std;
const int DefaultVertices = 30; // 默认最大顶点数
class STack
{
public:
int elem[DefaultVertices];//栈区
int Stackcount;//栈顶指针
};
template <class M, class N>
class EData
{
public:
M start; // 边的起点
M end; // 边的终点
N weight; // 边的权重
public:
EData(){}
EData(M s, M e, N w):start(s),end(e),weight(w){}
};
template <class T, class E>
class GraphMatrix {
public:
bool isWeighted; //是否带权 ,无权图默认边上权值为1，即weight=1
bool isDirected; //是否有向，0代表有向，1代表无向
GraphMatrix(int sz=DefaultVertices); // 构造函数
~GraphMatrix(); // 析构函数
void inputGraph(); // 创建基于邻接矩阵的图
void outputGraph(); // 输出图的所有顶点和边信息
T getValue(int i); // 取顶点i的值，i不合理返回0
E getWeight(int v1, int v2); // 取边(v1, v2)上的权值
int getFirstNeighbor(int v); // 取顶点v的第一个邻接顶点
int getNextNeighbor(int v, int w); // 取v的邻接顶点w的下一个邻接顶点
bool insertVertex(const T& vertex); // 插入顶点vertice
bool insertEdge(int v1, int v2, E cost); // 插入边(v1, v2)权值为cost，有向图
bool insertUEdge(int v1, int v2, E cost); // 插入边(v1, v2)权值为cost,无向图
bool removeVertex(int v); // 删去顶点v和所有与它相关联的边
bool removeEdge(int v1, int v2); // 在图中删去边(v1, v2)
int getVertexPos(T vertex); // 给出顶点vertice在图中的位置
void DFS();//深度度优先搜索
void DFS1(int i, int *visited);
void BFS();//广度优先搜索
void Floyd();//弗洛伊德算法 [多源最短路径]
void Dijkstra(int k);//Dijkstra最短路径算法 [单源最短路径]
void Prim(char x); //Prim（普利姆算法）
int getPosition(T ch); // 返回ch在矩阵中的位置
EData<T,E>* getEdges(); // 获取图中的边
void sortEdges(EData<T,E>* edges, int elen); // 对边按照权值大小进行排序(由小到大)
int getEnd(int vends[], int i); // //找集体老大，并查集的一部分 ,获取i的终点
void unionn(int vends[],int x,int y);//加入团体，并查集的一部分
void kruskal(); // 克鲁斯卡尔（Kruskal)最小生成树
void FindInAndOutDegree (); //求图各顶点的入度
void Initial (STack& stack); //初始化一个堆栈
bool Push (STack &stack,int &i); //将一个元素入栈
bool Pop (STack& stack,int &i); //将一个元素出栈
bool Gettop (STack& stack,int &i); //得到栈顶元素
bool StackEmpty (STack& stack); //判断堆栈是否为空
bool StackFull(STack& stack); //判断栈满
bool CriticalPath (); //求图的关键路径
bool TopologicalSort (); //进行拓扑排序
private:
int maxVertices; // 图中最大的顶点数
int numEdges; // 当前边数
int numVertices; // 当前顶点数
T *VerticesList; // 顶点表
E **Edge; // 邻接矩阵
int *indegree; //存放各顶点的入度
int *outdegree; //存放各顶点的出度
//T *Stack;//堆栈定义相关操作
//int Stackcount;//堆栈指针
int earlist[DefaultVertices]; //存放各顶点的最早发生时间
int latest[DefaultVertices]; //存放各顶点的最晚发生时间
STack IndegreeZeroStack,ToPoStack;//ToPoStack为拓扑序列顶点栈，IndegreeZeroStack为零入度顶点栈。
E maxWeight; // 代表无穷大的值（=∞）
};
// 构造函数
template <class T, class E>
GraphMatrix<T, E>::GraphMatrix(int sz) {
int i, j;
maxVertices = sz;
maxWeight=10000;
numVertices = 0;
numEdges = 0;
VerticesList = new T[maxVertices]; // 创建顶点表数组
Edge = new E*[maxVertices]; // 创建邻接矩阵数组
for(i = 0; i < maxVertices; i++)
Edge[i] = new E[maxVertices];
for(i = 0; i < maxVertices; i++) { // 邻接矩阵初始化
for(j = 0; j < maxVertices; j++)
{
if(i == j) // 矩阵对角处，即为同一顶点
Edge[i][j] = 0;
else // 不是同一顶点的，即两顶点一开始没有边相连，为无穷大∞
Edge[i][j] = maxWeight;
}
}
}
// 析构函数
template <class T, class E>
GraphMatrix<T, E>::~GraphMatrix() {
delete []VerticesList; // 释放动态分配的空间
delete []Edge;
}
// 创建基于邻接矩阵的图
template <class T, class E>
void GraphMatrix<T, E>::inputGraph() {
int i, j, k,h;
int n, m; // 要输入的顶点数和边数
T e1, e2; // 边的两端顶点
E weight; // 边对应的权值
cout << "请输入顶点数和边数:" << endl;
cin >> n >> m;
cout << "请输入顶点：" << endl;
for(i = 0; i < n; i++) { // 建立顶点表数据
cin >> e1;
insertVertex(e1); // 插入
}
cout<<"有向图选0，无向图选1："<<endl;
cin>>h;
if(h==0)
isDirected=0;
else
isDirected=1;
cout<<"是否有权(0代表无权，1代表有权)："<<endl;
cin>>isWeighted;
if(!isWeighted) {
cout << "请输入边的两端顶点:" << endl;
i = 0;
while(i < m){ // 输入边
cin >> e1 >> e2; // 输入端点信息
j = getVertexPos(e1); // 查顶点号
k = getVertexPos(e2);
if(j == -1 || k == -1)
cout << "边两端点信息有误，重新输入!" << endl;
else {
if(h==1)
insertUEdge(j, k, 1);
else if(h==0)
insertEdge(j, k, 1);
else
cout<<"输入错误";
i++;
}
} //
return;
}
cout << "请输入边的两端顶点和权值:" << endl;
i = 0;
while(i < m){ // 输入边
cin >> e1 >> e2 >> weight; // 输入端点信息
j = getVertexPos(e1); // 查顶点号
k = getVertexPos(e2);
if(j == -1 || k == -1)
cout << "边两端点信息有误，重新输入!" << endl;
else {
if(h==1)
insertUEdge(j, k, weight);
else if(h==0)
insertEdge(j, k, weight);
else
cout<<"输入错误";
i++;
}
} // for结束
}
// 输出图的所有顶点和边信息
template <class T, class E>
void GraphMatrix<T, E>::outputGraph() {
int i, j, n, m;
T e1, e2;
E w;
n = numVertices;
m = numEdges;
if(!isWeighted){
if (!isDirected)
cout << "这是个有向无权图" << endl;
else
cout << "这是个无向无权图" << endl;
}else{
if(!isDirected)
cout<< "这是个有向有权图" << endl;
else
cout << "这是个无向有权图" << endl;
}
cout << "顶点数为：" << n << "，边数为：" << m << endl;
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
w = getWeight(i, j); // 取边上权值
if(w > 0 && w < maxWeight) { // 有效，即这两顶点存在边
e1 = getValue(i);
e2 = getValue(j);
if(!isWeighted){
cout << "(" << e1 << "," << e2 << ")" << endl;
}else{
cout << "(" << e1 << "," << e2 << "," << w << ")" << endl;
}
}
}
} // for
}
// 给出顶点vertice在图中的位置
template <class T, class E>
int GraphMatrix<T, E>::getVertexPos(T vertex) {
for(int i = 0; i < numVertices; i++)
if(VerticesList[i] == vertex)
return i;
return -1;
}
// 取顶点i的值，i不合理返回NULL
template <class T, class E>
T GraphMatrix<T, E>::getValue(int i) {
if(i >= 0 && i < numVertices)
return VerticesList[i];
return 0;
}
// 取边(v1, v2)上的权值
template <class T, class E>
E GraphMatrix<T, E>::getWeight(int v1, int v2) {
if(v1 != -1 && v2 != -1) // 存在这两个顶点
return Edge[v1][v2];
return 0;
}
// 取顶点v的第一个邻接顶点
template <class T, class E>
int GraphMatrix<T, E>::getFirstNeighbor(int v) {
if(v != -1) {
for(int col = 0; col < numVertices; col++)
if(Edge[v][col] > 0 && Edge[v][col] <maxWeight)
return col;
}
return -1;
}
// 取v的邻接顶点w的下一个邻接顶点
template <class T, class E>
int GraphMatrix<T, E>::getNextNeighbor(int v, int w) {
if(v != -1 && w != -1) {
for(int col = w+1; col < numVertices; col++) {
if(Edge[v][col] > 0 && Edge[v][col] < maxWeight)
return col;
}
}
return -1;
}
// 插入顶点vertice
template <class T, class E>
bool GraphMatrix<T, E>::insertVertex(const T& vertex) {
if(numVertices == maxVertices) // 顶点表满
return false;
VerticesList[numVertices++] = vertex;
return true;
}
// 插入边(v1, v2)权值为cost
template <class T, class E>
bool GraphMatrix<T, E>::insertEdge(int v1, int v2, E cost) {
if(v1 > -1 && v1 < numVertices && v2 > -1 && v2 < numVertices && Edge[v1][v2] == maxWeight)
{ // 顶点v1,v2都存在，并且v1，v2没有边
Edge[v1][v2]=cost;
numEdges++;
return true;
}
return false;
}
// 插入边(v1, v2)权值为cost
template <class T, class E>
bool GraphMatrix<T, E>::insertUEdge(int v1, int v2, E cost) {
if(v1 > -1 && v1 < numVertices && v2 > -1 && v2 < numVertices && Edge[v1][v2] == maxWeight)
{ // 顶点v1,v2都存在，并且v1，v2没有边
Edge[v1][v2] = Edge[v2][v1] = cost;
numEdges++;
return true;
}
return false;
}
// 删去顶点v和所有与它相关联的边
template <class T, class E>
bool GraphMatrix<T, E>::removeVertex(int v) {
if(v < 0 && v > numVertices) // v不在图中，不删除
return false;
if(numVertices == 1) // 只剩一个顶点，不删除
return false;
int i, j;
VerticesList[v] = VerticesList[numVertices-1]; // 用最后一个顶点替代当前要删的顶点
// 删除与v相关联边数
for(i = 0; i < numVertices; i++) {
if(Edge[i][v] > 0 && Edge[i][v] < maxWeight)
numEdges--;
}
// 用最后一列，填补第v列
for(i = 0; i < numVertices; i++)
Edge[i][v] = Edge[i][numVertices-1];
numVertices--; // 顶点数减1
// 用最后一行，填补第v行
for(j = 0; j < numVertices; j++)
Edge[v][j] = Edge[numVertices][j];
return true;
}
// 在图中删去边(v1, v2)
template <class T, class E>
bool GraphMatrix<T, E>::removeEdge(int v1, int v2) {
if(v1 > -1 && v1 < numVertices && v2 > -1 && v2 < numVertices && Edge[v1][v2] < maxWeight) {
Edge[v1][v2] = Edge[v2][v1] = maxWeight;
numEdges--; // 边数减1
return true;
}
return false;
}
//
template <class T, class E>
void GraphMatrix<T, E>::DFS() {
int i;
int visited[30]; // 顶点访问标记
// 初始化所有顶点都没有被访问
for (i = 0; i < numVertices; i++)
visited[i] = 0;
cout << "DFS: ";
for (i = 0; i < numVertices; i++)
{
//printf("\n== LOOP(%d)\n", i);
if (!visited[i])
DFS1(i, visited);
}
cout << endl;
}
template <class T, class E>
void GraphMatrix<T, E>::DFS1(int i, int *visited) {
int w;
visited[i] = 1;
cout << VerticesList[i] << " ";
// 遍历该顶点的所有邻接顶点。若是没有访问过，那么继续往下走
for (w = getFirstNeighbor(i); w >= 0; w = getNextNeighbor(i, w))
{
if (!visited[w])
DFS1(w, visited);
}
}
template <class T, class E>
void GraphMatrix<T, E>::BFS() {
int head = 0;
int rear = 0;
int queue[DefaultVertices]; // 辅组队列
int visited[DefaultVertices]; // 顶点访问标记
int i, j, k;
for (i = 0; i < numVertices; i++)
visited[i] = 0;
cout << "BFS: ";
for (i = 0; i < numVertices; i++)
{
if (!visited[i])
{
visited[i] = 1;
cout <<VerticesList[i] << " ";
queue[rear++] = i; // 入队列
}
while (head != rear)
{
j = queue[head++]; // 出队列
for (k = getFirstNeighbor(j); k >= 0; k = getNextNeighbor(j, k)) //k是为访问的邻接顶点
{
if (!visited[k])
{
visited[k] = 1;
cout <<VerticesList[k] << " ";
queue[rear++] = k;
}
}
}
}
cout << endl;
}
template <class T, class E>
void GraphMatrix<T, E>::Floyd()
{
//可以正确处理有向图或负权（但不可存在负权回路）的最短路径问题。
int distance[numVertices][numVertices];//记录顶点间的最小路径值
int path[numVertices][numVertices];//记录对应点的最小路径的前驱点，例如path[1][3] = 2 说明顶点1到顶点3的最小路径要经过2
//初始化floyd算法的两个矩阵
for (int i = 0; i < numVertices; i++) {
for(int j = 0; j < numVertices; j++){
path[i][j] = -1;
distance[i][j] = Edge[i][j];
}
}
//这里是弗洛伊德算法的核心部分
//k为中间点
for(int k = 0; k < numVertices; k++){
//i为起点
for(int i = 0 ; i < numVertices; i++){
//j为终点
for(int j =0; j < numVertices; j++){
if(distance[i][j] > (distance[i][k] + distance[k][j]) && distance[i][k]!= maxWeight && distance[k][j]!= maxWeight){
distance[i][j] = distance[i][k] + distance[k][j];//更新最小路径
path[i][j] = k;//更新最小路径中间顶点
}
}
}
}
/*for(int i = 0 ; i < numVertices; i++){
for(int j =0; j < numVertices; j++){
cout<< distance[i][j]<<' ';
}
cout<<endl;
}*/
for(int i = 0 ; i < numVertices; i++){
for(int j =0; j < numVertices; j++){
if(distance[i][j]==maxWeight){
cout<<"没有路可以从"<<getValue(i)<<"走到"<<getValue(j)<<endl;
}
if(distance[i][j]!=maxWeight && i!=j){
cout<<getValue(i)<<"到"<<getValue(j)<<"的最短路径为：";
int k=path[i][j];
cout<<getValue(i);
while(k != j && k!=-1){
cout<<"->"<<getValue(k);//打印中间点
k= path[k][j];
}
cout<<"->"<<getValue(j)<<"-----最短距离为："<<distance[i][j]<<endl;
}
}
}
}
template <class T, class E>
void GraphMatrix<T, E>::Dijkstra(int k)
{
int* final = new int[numVertices];
int* path = new int[numVertices];
int* distance = new int[numVertices];
int i;
// 初始化结点
for (i = 0; i < numVertices; i++) {
path[i] = -1;
final[i] = 0;
distance[i] = maxWeight;
}
distance[k] = 0; // 初始化源点
for (i = 0; i < numVertices; i++) { // 寻找不同长度的最短路径
int min = maxWeight; // 当前所知里顶点j的最短距离
int index = -1; // 最短距离对应的下标
int j;
for (j = 0; j < numVertices; j++) {
if (!final[j]) { // j在V-S中
if (distance[j] < min) {
min = distance[j];
index = j;
}
}
}// 寻找最短路径
if (index == -1) break;
final[index] = 1; // 离j最近的顶点Index并入S，第一次一定是v0
for (j = 0; j < numVertices; j++) { // 更新距离矩阵，一定要判断是否达，即arc[][]!=OO，否则会整数溢出
if(Edge[index][j]<0){
cout << "这是个带负权的有向图，Dijkstra算法无法进行求解" << endl;
return ;
}
if (!final[j] && Edge[index][j] != maxWeight && (min + Edge[index][j] < distance[j])) {
distance[j] = min +Edge[index][j];
path[j] = index;
}
}
}
for (i = 0; i < numVertices; i++)
{
cout<<VerticesList[k]<<"到顶点"<<VerticesList[i]<<"的最短路径距离为"<<distance[i]<<endl;
cout<<"逆序输出路径:" ;
int index=0;
int j=i;
while(path[j]!=-1)
{
cout<<VerticesList[j]<<"<-";
j=path[j];
}
cout<<VerticesList[k];
cout<<endl;
}
delete[] final;
}
template <class T, class E>
void GraphMatrix<T, E>::Prim(char x)//普利姆算法（参数：起点（即第一个生成的点，可随便取））
{
int lowcost[DefaultVertices], closest[DefaultVertices], i, min, j, k;
int v=getVertexPos(x);
/***初始化lowcost数组，closest数组(即从起点开始设置lowcost数组，closest数组相应的值，以便后续生成使用)***/
for (i = 0; i < numVertices; i++)//赋初值，即将closest数组都赋为第一个节点v，lowcost数组赋为第一个节点v到各节点的权重
{
closest[i] = v;
lowcost[i] = Edge[v][i];//Edge[v][i]的值指的是节点v到i节点的权重
}
/**********************************开始生成其他的节点*********************************/
for (i = 1; i < numVertices; i++)//接下来找剩下的n-1个节点（g.n是图的节点个数）
{
/*****找到一个节点，该节点到已选节点中的某一个节点的权值是当前最小的*****/
min = maxWeight;//INF表示正无穷（每查找一个节点，min都会重新更新为INF，以便获取当前最小权重的节点）
for (j = 0; j < numVertices; j++)//遍历所有节点
{
if (lowcost[j] != 0 && lowcost[j] < min)//若该节点还未被选且权值小于之前遍历所得到的最小值
{
min = lowcost[j];//更新min的值
k = j;//记录当前最小权重的节点的编号
}
}
/****************输出被连接节点与连接节点，以及它们的权值***************/
cout<<"边（"<< VerticesList[closest[k]]<<","<<VerticesList[k]<<")权为："<<min<<endl;
//printf("边(%c,%c)权为:%d\n", VerticesList[closest[k]],VerticesList[k], min);
/***********更新lowcost数组，closest数组，以便生成下一个节点************/
lowcost[k] = 0;//表明k节点已被选了(作标记)
//选中一个节点完成连接之后，作数组相应的调整
for (j = 0; j <numVertices ; j++)//遍历所有节点
{
/* if语句条件的说明：
* （1）Edge[k][j] != 0是指k！=j，即跳过自身的节点
* （2）Edge[k][j]是指刚被选的节点k到节点j的权重，lowcost[j]是指之前遍历的所有节点与j节点的最小权重。若Edge[k][j] < lowcost[j],则说明当前刚被选的节点k与节点j之间存在更小的权重，则需要更新
* （3）有人会问：为什么只跳过掉自身的节点（即k==j），而不跳过所有的已选节点？当然我们可以在if语句条件中增加跳过所有的已选节点的条件（即lowcost[j] == 0），而在本程序中我们只跳过了自身的节点？（注意：我们假设图中的边的权值大于0）但其实不是，Edge[k][j] < lowcost[j]条件已包含跳过所有的已选节点，原因是在邻接矩阵中权值为0是最小的，即Edge[k][j]>=0，而已选节点满足lowcost[j] == 0，则已选节点j是不满足Edge[k][j] < lowcost[j]，则会被跳过
*/
if (Edge[k][j] != 0 && Edge[k][j] < lowcost[j])
{
//更新lowcost数组，closest数组
lowcost[j] = Edge[k][j];//更新权重，使其当前最小
closest[j] = k;//进入到该if语句里，说明刚选的节点k与当前节点j有更小的权重，则closest[j]的被连接节点需作修改为k
}
}
}
}
template <class T, class E>
int GraphMatrix<T, E>::getPosition(T ch)
{
int i;
for(i=0; i<numVertices; i++)
if(VerticesList[i]==ch)
return i;
return -1;
}
template <class T, class E>
EData<T,E>* GraphMatrix<T, E>::getEdges()
{
int i,j;
int index=0;
EData<T,E> *edges;
edges = new EData<T,E>[numEdges];
for (i=0; i < numVertices; i++)
{
for (j=i+1; j < numVertices; j++)
{
if (Edge[i][j]!=maxWeight)
{
edges[index].start = VerticesList[i];
edges[index].end = VerticesList[j];
edges[index].weight = Edge[i][j];
index++;
}
}
}
cout<<"edges数组未排序:"<<endl;
for(i=0;i<index;i++)
{
cout<<edges[i].start<<"-->"<<edges[i].end<<"="<<edges[i].weight<<endl;
}
cout<<endl;
return edges;
}
template <class T, class E>
void GraphMatrix<T, E>::sortEdges(EData<T,E>* edges, int elen)
{
int i,j;
for (i=0; i<elen; i++)
{
for (j=i+1; j<elen; j++)
{
if (edges[i].weight > edges[j].weight)
{
// 交换"边i"和"边j"
swap(edges[i], edges[j]);
}
}
}
cout<<"edges数组排序:"<<endl;
for(i=0;i<elen;i++)
{
cout<<edges[i].start<<"-->"<<edges[i].end<<"="<<edges[i].weight<<endl;
}
}
template <class T, class E>
int GraphMatrix<T, E>::getEnd(int vends[], int i)
{
if(vends[i]!=i)
{
return getEnd(vends,vends[i]);
}else
{
return i;
}
}
template <class T, class E>
void GraphMatrix<T, E>::unionn(int vends[],int x,int y)
{
vends[x] = y;
}
template <class T, class E>
void GraphMatrix<T, E>::kruskal()
{
int i,m,n,p1,p2;
int length;
int index = 0; // rets数组的索引
int vends[DefaultVertices]; // 用于保存"已有最小生成树"中每个顶点在该最小树中的终点。
for(int i=0;i<numEdges;i++)
{
vends[i]=i;
}
EData<T,E> rets[DefaultVertices]; // 结果数组，保存kruskal最小生成树的边
EData<T,E> *edges; // 图对应的所有边
// 获取"图中所有的边"
edges = getEdges();
// 将边按照"权"的大小进行排序(从小到大)
sortEdges(edges, numEdges);
for (i=0; i<numEdges; i++)
{
p1 = getPosition(edges[i].start); // 获取第i条边的"起点"的序号
p2 = getPosition(edges[i].end); // 获取第i条边的"终点"的序号
m = getEnd(vends, p1); // 获取p1在"已有的最小生成树"中的终点，找自己的老大
n = getEnd(vends, p2); // 获取p2在"已有的最小生成树"中的终点，找自己的老大
// 如果m!=n，意味着"边i"与"已经添加到最小生成树中的顶点"没有形成环路
if (m != n)//假如不在一个团体
{
unionn(vends,m,n); // 设置m在"已有的最小生成树"中的终点为n
rets[index++] = edges[i]; // 保存结果
}
}
delete[] edges;
// 统计并打印"kruskal最小生成树"的信息
length = 0;
for (i = 0; i < index; i++)
length += rets[i].weight;
cout << "Kruskal=" << length << ": ";
for (i = 0; i < index; i++)
cout << "(" << rets[i].start << "," << rets[i].end << ") ";
cout << endl;
}
template <class T, class E>
void GraphMatrix<T, E>::FindInAndOutDegree ()
{ //求出图G的各顶点的入度，存放在数组indegree[]中
int i,j;
indegree=new int[maxVertices];
outdegree=new int[maxVertices];
for ( i=0; i<numVertices; i++ )
indegree[i]=0;
outdegree[i]=0;
for ( i=0; i<numVertices; i++ )
{
for(j=0;j<numVertices; j++){
if(i!=j && getWeight(i,j)<maxWeight)
outdegree[i]++;//弧头顶点的出度加一
if(i!=j && getWeight(j,i)<maxWeight)
indegree[i]++;
}
cout<<getValue(i)<<"的出度:"<<outdegree[i]<<"-----入度："<<indegree[i]<<endl;
}
}
template <class T, class E>
void GraphMatrix<T, E>::Initial (STack& stack)
{
stack.Stackcount=-1;
}
template <class T, class E>
bool GraphMatrix<T, E>::StackEmpty (STack& stack)
{
return stack.Stackcount==-1;
}
template <class T, class E>
bool GraphMatrix<T, E>:: StackFull(STack& stack)
{
return stack.Stackcount==maxVertices-1;
}
template <class T, class E>
bool GraphMatrix<T, E>::Push (STack &stack,int &i)
{
if(!StackFull(stack)){
stack.Stackcount=stack.Stackcount+1;
stack.elem[stack.Stackcount]=i;
return true;
}else{
cout<<"Full"<<endl;
return false;
}
}
template <class T, class E>
bool GraphMatrix<T, E>::Pop (STack& stack,int &i)
{
if(!StackEmpty(stack)){
i=stack.elem[stack.Stackcount];
stack.Stackcount--;
return true;
}else{
cout<<"Empty"<<endl;
return false;
}
}
template <class T, class E>
bool GraphMatrix<T, E>::Gettop (STack& stack,int &i)
{
if (stack.Stackcount<=-1 )
return false;
else
{
i=stack.elem[stack.Stackcount];
return true;//显示栈顶元素
}
}
template <class T, class E>
bool GraphMatrix<T, E>::TopologicalSort ()
{
//有向网G采用邻接矩阵存储结构，求各顶点事件的最早发生时间ve，
//ToPoStack为拓扑序列顶点栈，IndegreeZeroStack为零入度顶点栈。
//若G无回路，则用栈返回G的一个拓扑序列，且函数返回True,否则返回False
int count=0; //计数器对输出顶点记数
int ch;
FindInAndOutDegree(); //求出图中各顶点的入度
Initial (IndegreeZeroStack); //堆栈初始化，存放入度为零的顶点
Initial (ToPoStack);
for (int i=0; i<numVertices; i++){
if (indegree[i]==0) {
Push (IndegreeZeroStack,i); //入度为零的顶点入栈
}
}
//cout<<S.Stackcount<<endl;
for (int i=0; i<numVertices; i++ ){
earlist[i]=0; //ve初始化
}
while (!StackEmpty (IndegreeZeroStack))
{
Pop (IndegreeZeroStack,ch); //顶点出S栈并入T栈，count记数
int i=ch;
Push (ToPoStack,ch);
count++;
// int i=getVertexPos(ch);//顶点ch对应的位置i号
for(int j=0;j<numVertices; j++){
if(i!=j && getWeight(i,j)<maxWeight){
if (!( --indegree[j] ))
Push (IndegreeZeroStack,j); //若入度为零，入栈
if (( earlist[i]+getWeight(i,j)) >earlist[j] )
earlist[j] =earlist[i]+getWeight(i,j);
//修改k号顶点的最早发生时间
//ve的求法：ve(j)=Max{ve(i)+dut(<i,j>)} <i,j>∈S,j=1,2,…,n-1
}
}
}
cout<<"到达各个状态的最早时间："<<endl;
for(int i=0;i<numVertices;i++)
{
cout<<getValue(i)<<":"<<earlist[i]<<endl;
}
if (count<(numVertices-1)){
cout<<"回路"<<endl;
return false; //如输出顶点数少于图中顶点数，则该图有回路
}
else {
return true;
}
}
template <class T, class E>
bool GraphMatrix<T, E>::CriticalPath ()
{
//G为有向网，输出G的各项关键活动
int ee,el;
int ch,dh;
if (!TopologicalSort ())
return false;
//利用拓扑排序求出各顶点的最早发生时间，并用返回拓扑序列，
//若返回False，表明该网有回路
cout<<"Critical Path:"<<endl ;
Gettop (ToPoStack,ch); //取得拓扑序列的最后一个顶点，即该网的汇点
int k=ch;//取得该点位置
latest[k]=earlist[k]; //汇点的latest=earlist
for(int j=0; j<numVertices; j++ )
if (j!=k)
latest[j]=maxWeight; //将其他的顶点的vl置为IFINITY
while ( !StackEmpty (ToPoStack) )//按拓扑逆序求各顶点的latest值
{
Pop (ToPoStack,dh);
int i=dh;//取得该点位置
for(int j=0;j<numVertices; j++){
if(i!=j && getWeight(i,j)<maxWeight){
if ((latest[j]-getWeight(i,j)) <latest[i] )latest[i] =latest[j]-getWeight(i,j);
//vl的求法：vl(i)=Min{vl(j)-dut(<i,j>)} <i,j>∈S,i=n-2,...0
}
}
}
for (int i=0; i<numVertices; i++ ) //求每条弧的最早开始时间ee和最迟开始时间el
for(int j=0;j<numVertices; j++){
if(i!=j && getWeight(i,j)<maxWeight){
ee=earlist[i];
el=latest[j]-getWeight(i,j);
if ( ee==el )
cout<<getValue(i)<<"->"<<getValue(j)<<":"<<getWeight(i,j)<<endl; //若ee=el，则该弧为关键活动
}
}
return true;
}
int main(int argc, const char * argv[]) {
GraphMatrix<char, int> st; // 声明对象
bool finished = false;
int choice;
char e1, e2, next;
int weight;
while(!finished) {
cout << "[1]创建基于邻接矩阵的图" << endl;
cout << "[2]输出图的所有顶点和边信息" << endl;
cout << "[3]取顶点v的第一个邻接顶点" << endl;
cout << "[4]取v的邻接顶点w的下一个邻接顶点" << endl;
cout << "[5]插入顶点" << endl;
cout << "[6]无向图插入边" << endl;
cout << "[7]有向图插入边" << endl;
cout << "[8]删除顶点" << endl;
cout << "[9]删除边" << endl;
cout << "[10]深度优先搜索DFS" << endl;
cout << "[11]广度优先搜索BFS" << endl;
cout << "[12]Floyd多源最短路径算法" << endl;
cout << "[13]Dijkstra最短路劲" << endl;
cout << "[14]Prim最小生成树算法" << endl;
cout << "[15]kruskal最小生成树算法" << endl;
cout << "[16]拓扑排序" << endl;
cout << "[17]关键路径算法" << endl;
cout << "[18]退出" << endl;
cout << "请输入选择[1-18]：";
cin >> choice;
switch(choice) {
case 1:
st.inputGraph();
break;
case 2:
st.outputGraph();
break;
case 3:
cout << "请输入顶点:";
cin >> e1;
e2 = st.getValue(st.getFirstNeighbor(st.getVertexPos(e1)));
if(e2)
cout << "顶点" << e1 << "的第一个邻接顶点为:" << e2 << endl;
else
cout << "顶点" << e1 << "没有邻接顶点！" << endl;
break;
case 4:
cout << "请输入顶点v和邻接顶点w:";
cin >> e1 >> e2;
next = st.getValue(st.getNextNeighbor(st.getVertexPos(e1), st.getVertexPos(e2)));
if(next)
cout << "顶点" << e1 << "的邻接顶点" << e2 << "的下一个邻接顶点为:" << next << endl;
else
cout << "顶点" << e1 << "的邻接顶点" << e2 << "没有下一个邻接顶点！" << endl;
break;
case 5:
cout << "请输入要插入的顶点：";
cin >> e1;
if(st.insertVertex(e1))
cout << "插入成功！" << endl;
else
cout << "表已满，插入失败！" << endl;
break;
case 6:
if(!st.isWeighted){
cout << "请这是个无权图只需输入边的信息（两个顶点）无需输入权值【顶点1 顶点2】" << endl;
cin >> e1 >> e2;
weight=1;
}else{
cout << "请这是个有权图需输入边的信息（两个顶点）及权值【顶点1 顶点2 权值】" << endl;
cin >> e1 >> e2 >> weight;
}
st.insertUEdge(st.getVertexPos(e1), st.getVertexPos(e2), weight);
break;
case 7:
if(!st.isWeighted){
cout << "请这是个无权图只需输入边的信息（两个顶点）无需输入权值【顶点1 顶点2】" << endl;
cin >> e1 >> e2;
weight=1;
}else{
cout << "请这是个有权图需输入边的信息（两个顶点）及权值【顶点1 顶点2 权值】" << endl;
cin >> e1 >> e2 >> weight;
}
st.insertEdge(st.getVertexPos(e1), st.getVertexPos(e2), weight);
break;
case 8:
cout << "请输入要删除的顶点：";
cin >> e1;
if(st.removeVertex(st.getVertexPos(e1)))
cout << "顶点" << e1 << "已删除!" << endl;
else
cout << "顶点" << e1 << "不在图中!" << endl;
break;
case 9:
cout << "请输入要删除的边的两个端点：" << endl;
cin >> e1 >> e2;
st.removeEdge(st.getVertexPos(e1), st.getVertexPos(e2));
break;
case 10:
st.DFS();
break;
case 11:
st.BFS();
break;
case 12:
if(st.isDirected || !st.isWeighted){
cout << "这是个无向或者无权图，最短路径算法针对的是带权有向图，无法进行求解" << endl;
break;
}
st.Floyd();
break;
case 13:
if(st.isDirected || !st.isWeighted){
cout << "这是个无向或者无权图，最短路径算法针对的是带权有向图，无法进行求解" << endl;
break;
}
st.Dijkstra(1);
break;
case 14:
if(!st.isWeighted){
cout << "这是个无权图，最小生成树算法针对的是带权无向图，无法进行求解" << endl;
break;
}
if(!st.isDirected){
cout << "这是个有向图，最小生成树算法针对的是带权无向图，无法进行求解" << endl;
break;
}
cout<<"请输入起始点："<<endl;
cin>>e1;
st.Prim(e1);
break;
case 15:
if(!st.isWeighted){
cout << "这是个无权图，最小生成树算法针对的是带权无向图，无法进行求解" << endl;
break;
}
if(!st.isDirected){
cout << "这是个有向图，最小生成树算法针对的是带权无向图，无法进行求解" << endl;
break;
}
st.kruskal();
break;
case 16:
st.TopologicalSort();
break;
case 17:
st.CriticalPath();
break;
case 18:
finished = true;
break;
default:
cout << "选择输入错误，请重新输入!" << endl;
}
}
return 0;
}
部分函数运行截图：
部分代码运行截图
小编写代码时也没去考虑使用C++提供的STL模板等，也许有些地方存在一些小问题，也请指正。
网友评论