图论（算法）--C++学习（5）-创新互联
图论（持续更新）
文章标题：图论（算法）--C++学习（5）-创新互联
分享路径：http://hbruida.cn/article/dhsijs.html
- 拓扑排序
- 介绍
- 例图
- 代码实现
- 排序结果
- 最小生成树
- Prim
- 介绍
- 图例
- 代码
- 结果
- Kruscal
- 介绍
- 图例
- 代码
- 结果
- 最短路径
- Dijkstra
- 介绍
- 图例
- 代码
- 结果
- Floyd
- 介绍
- 图例
- 代码
- 结果
该算法主要对图中各节点的先后顺序进行排列。在日常生活中，在做一些事时，需要一定的先后顺序，在做某件事时总是需要其他事情做完为前提，而如果把事情当作图中的节点，那么就组成了一个有向图。一般来说拓扑排序可以给出事件的顺序，但是当存在矛盾的情况，也就是事件的前提条件存在环路，那么拓扑排序就无法实现。
例图
#include#include#includeusing namespace std;
//拓扑排序 grid:邻接矩阵 result:排序结果数组 return:排顺序是否成功bool
bool Topological_Sort(vector>&grid,vector&result)
{int n = grid.size();//节点数量
vectorinDegree(n, 0);//保存所有节点的入度，初始值0
queueq;//入度为0入队
//遍历邻接矩阵，查找所有节点的入度
for (int i = 0; i< n; i++)
{for (int j = 0; j< n; j++)
{ if (grid[i][j] != 0)
{ inDegree[j]++;
}
}
}
//首先找到入度为0的节点保存到队列中
for (int i = 0; i< n; i++)
{if (inDegree[i] == 0)
{ q.push(i);
//inDegree[i] = -1;//-1表示已经排序不再遍历
}
}
//找到下一个入度为空的节点
while (!q.empty())
{int t = q.front();
result.emplace_back(t);//将出队列结果保存下来
q.pop();
for (int k = 0; k< n; k++)
{ if (grid[t][k] != 0)
{ inDegree[k]--;
if (inDegree[k] == 0)
{q.push(k);
}
}
}
}
//判断所有的节点是否全部排序，如果存在入度不为0的情况说明存在环路，排序失败
for (int i = 0; i< n; i++)
{if (inDegree[i] != 0)
{ return false;
}
}
return true;
}
int main()
{//邻接矩阵
vector>grid = {{0,0,0,0,0,0},
{1,0,1,0,0,1},
{0,0,0,0,0,1},
{0,0,1,0,0,0},
{0,1,1,0,0,0},
{0,0,0,0,0,0} };
//结果数组
vectorresult;
//打印结果
if (Topological_Sort(grid, result))
{for (int i = 0; i< result.size(); i++)
{ cout<cout<< "图中有环路，排序失败！"<< endl;
}
} 
该算法从一个起点开始不断向外扩张，扩张方式为每次去找遍历过的节点到未遍历节点的最短路径。直到所有的节点全被遍历。
图例
#include#include#include#include
using namespace std;
//在无向图中使用Prim算法，查找最小生成树，并记录
bool Prim(vector>&grid, vector>&tree)
{int n = grid.size();
//vector>tree(n, vector(n,0));
unordered_setdict;//用来记录被遍历的节点 一般来说大家都使用数组
vector>min_distant(n,pair(INT_MAX,INT_MAX));//用来记录指向该节点的最短边，以及起始节点
//以节点0为起始节点
dict.emplace(0);
//更新已遍历节点到未遍历节点的最短边
for (int i = 0; i< n; i++)
{if (min_distant[i].first >grid[0][i])
{ min_distant[i].first = grid[0][i];
min_distant[i].second = 0;
}
}
//还需要查找n-1个节点
for (int i = 1; i< n; i++)
{int edge = INT_MAX;
int p = -1;
//找到已遍历到未遍历节点的最短边
for (int j = 0; j< n; j++)
{ if (dict.count(j) == 0 && edge>min_distant[j].first)
{ edge = min_distant[j].first;
p = j;
}
}
//找不到 构建失败
if (p == -1) return false;
//根据找到的最短边和节点更新dict和min_distant
dict.emplace(p);
tree[min_distant[p].second][p] = edge;
//更新到未遍历节点的最小距离
for (int j = 0; j< n; j++)
{ if (dict.count(j) == 0 && min_distant[j].first >grid[p][j])
{ min_distant[j].first = grid[p][j];
min_distant[j].second = p;
}
}
}
}
int main()
{vector>grid =
{{INT_MAX,INT_MAX,8,12,3,INT_MAX},
{INT_MAX,INT_MAX,3,7,6,INT_MAX},
{8,3,INT_MAX,4,INT_MAX,1},
{12,7,4,INT_MAX,2,4},
{3,6,INT_MAX,2,INT_MAX,5},
{INT_MAX,INT_MAX,1,4,5,INT_MAX},
};
vector>tree(grid.size(), vector(grid.size(), 0));
if(!Prim(grid, tree)) cout<<"失败"<for (int j = 0; j< 6; j++)
{ cout<< tree[i][j]<< " ";
}
cout<< endl;
}
return 0;
} 
实际上采用贪心思想，每次从所有剩余的边中找到最短的边，选边时主要通过判断该边两个节点是否处于同一状态下，判断该边是否会造成环路，进而选择是否选择该边加入树中
图例
#include#include#include
using namespace std;
bool Kruscal(vector>&grid,vector>&tree)
{int n = grid.size();
vector>edges;
//记录所有的边
for (int i = 0; i< n; i++)
{for (int j = 0; j< n; j++)
{ if (grid[i][j] != INT_MAX)
{ vectort = {i,j,grid[i][j]};
edges.push_back(t);
}
}
}
//根据权值将所有的边进行升序排序
sort(edges.begin(), edges.end(), [](vectora, vectorb) {return a[2]< b[2]; });
vectorbook(n);//记录对应节点的状态
for (int i = 0; i< n; i++)//起始时各节点状态各不相同
{book[i] = i;
}
int point_num = n, edge_num = 0;//点数和边数
for (int i = 0; i< edges.size(); i++)
{vectortemp = edges[i];
if (book[temp[0]] != book[temp[1]])//如果边的两个点不在同一状态下说明，该边不会导致树形成环，则将该边记录下来
{ edge_num++;
tree.push_back(temp);//记录边
int q = book[temp[1]];
//改变节点两个状态为同一状态
for (int j = 0; j< n; j++)
{ if (book[j] == q)
{book[j] = book[temp[0]];
}
}
}
if (point_num - edge_num == 1)
{ break;
}
}
//判断是否成功
if (point_num - edge_num == 1)
{return true;
}
return false;
}
int main()
{vector>grid =
{{INT_MAX,INT_MAX,8,12,3,INT_MAX},
{INT_MAX,INT_MAX,3,7,6,INT_MAX},
{8,3,INT_MAX,4,INT_MAX,1},
{12,7,4,INT_MAX,2,4},
{3,6,INT_MAX,2,INT_MAX,5},
{INT_MAX,INT_MAX,1,4,5,INT_MAX},
};
vector>tree;
if(!Kruscal(grid, tree)) cout<<"失败"<for (int j = 0; j< 3; j++)
{ cout<< tree[i][j]<< " ";
}
cout<< endl;
}
return 0;
}
该方法主要是解决单源最短路径问题，思想为贪心思想，过程和最小生成树中的Prim算法很像，都维护一个最短长度的表，不过两个表的意义不同，Prim维护的是已遍历节点到未遍历节点中最短的边权重，而Dijkstra维护的是点到源点的最短路径 当然两者都是每次去取出最小的值进行操作。
每次Dijkstra找到一条路径，首先将该点状态更新为已遍历，然后比较未遍历节点经过该点到达源点的路径和已有路径哪个更优，进行更新。在更新时，还要将该点作为未遍历节点的前驱节点，更新前驱节点表。
#include#include#include
using namespace std;
//单源最短路径 当然如果没有end的话， pre_node:前驱节点 可以返回所有节点和start节点的最短距离
vectorDijkstra(vector>&grid, vector&pre_node,int start)
{int n = grid.size();//节点数
vectorbook(n,0);//用来记录遍历过的节点
vectordistant(n, INT_MAX);//start到达指定节点的最小距离，最后的结果也会出现在这个数组中
//初始化 从start向外出发
book[start] = 1;
pre_node[start] = -1;
int pre = start;
//更新距离和前驱节点
for (int i = 0; i< n; i++)
{distant[i] = grid[start][i];
pre_node[i] = start;
}
//还需要找n-1个节点
for (int i = 1; i< n; i++)
{//找到未到达节点到上一节点的最短的路径的节点
int d = INT_MAX,p=-1;
for (int j = 0; j< n; j++)
{ if (book[j] == 0 && distant[j]< d)
{ d = distant[j];
p = j;
}
}
//更新节点状态
book[p] = 1;
//根据新加入的节点，更新到所有未遍历节点的距离
for (int j = 0; j< n; j++)
{ //grid[p][j]!=INT_MAX非常重要 d+INT_MAX会导致数据超出int表示范围（上溢）
if (book[j] == 0 && grid[p][j]!=INT_MAX &&d + grid[p][j]< distant[j])
{ distant[j] = d + grid[p][j];
pre_node[j] = p;
}
}
}
return distant;
}
int main()
{vector>grid=
{{INT_MAX,1,2,3,INT_MAX,INT_MAX},
{1,INT_MAX,INT_MAX,2,1,INT_MAX},
{2,INT_MAX,INT_MAX,INT_MAX,3,INT_MAX},
{3,2,INT_MAX,INT_MAX,INT_MAX,2},
{INT_MAX,1,3,INT_MAX,INT_MAX,1},
{INT_MAX,INT_MAX,INT_MAX,2,1,INT_MAX}
};
vectorresult;
vectorpre_node(grid.size(),0);
result=Dijkstra(grid,pre_node, 0);
cout<< "单源最短路径"<< endl;
for (int i = 0; i< result.size(); i++)
{cout<< result[i]<< " ";
}
cout<< endl;
cout<< "前驱节点"<< endl;
for (int i = 0; i< result.size(); i++)
{cout<< pre_node[i]<< " ";
}
return 0;
} 
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
文章标题：图论（算法）--C++学习（5）-创新互联
分享路径：http://hbruida.cn/article/dhsijs.html
