图论（算法）--C++学习（5）-创新互联

图论（持续更新）

拓扑排序
- 介绍
- - 例图
  - 代码实现
  - 排序结果
最小生成树
- 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;
	}


}

排序结果

在这里插入图片描述

最小生成树 Prim 介绍

该算法从一个起点开始不断向外扩张，扩张方式为每次去找遍历过的节点到未遍历节点的最短路径。直到所有的节点全被遍历。

图例

在这里插入图片描述

代码

#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;
}

结果

在这里插入图片描述

Kruscal 介绍

实际上采用贪心思想，每次从所有剩余的边中找到最短的边，选边时主要通过判断该边两个节点是否处于同一状态下，判断该边是否会造成环路，进而选择是否选择该边加入树中

图例

在这里插入图片描述

代码

#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;
}

结果

在这里插入图片描述

最短路径 Dijkstra 介绍

该方法主要是解决单源最短路径问题，思想为贪心思想，过程和最小生成树中的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;

}

结果

在这里插入图片描述

Floyd 介绍图例代码结果

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网站栏目：图论（算法）--C++学习（5）-创新互联
链接URL：http://chengdu.cdxwcx.cn/article/dhsijs.html

甜橘子，专注成都网站制作网站设计与营销型网站建设与优化

首页

网站建设

网站制作案例

解决方案

网站设计报价

网站制作动态

关于我们

联系我们

成都网站建设设计将想法与焦点和您一起共享

图论（算法）--C++学习（5）-创新互联

其他资讯

阿里云服务器如何下载软件阿里云服务器安装yum

sap分销系统多少钱的简单介绍

360云网络安全服务器 360云端服务

帝国cms导航如何换链接帝国cms自定义页面

linux怎么加命令行 linux怎么命令行查看cpu使用率

甜橘子，专注成都网站制作网站设计与营销型网站建设与优化

成都网站建设设计 将想法与焦点和您一起共享

图论（算法）--C++学习（5）-创新互联

其他资讯

阿里云服务器如何下载软件 阿里云服务器安装yum

sap分销系统多少钱的简单介绍

360云网络安全服务器 360云端服务

帝国cms导航如何换链接 帝国cms自定义页面

linux怎么加命令行 linux怎么命令行查看cpu使用率

成都网站建设设计将想法与焦点和您一起共享

阿里云服务器如何下载软件阿里云服务器安装yum

帝国cms导航如何换链接帝国cms自定义页面