189 8069 5689

图论(算法)--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)-创新互联
文章网址:http://jkwzsj.com/article/dhsijs.html

其他资讯