西宁网站建设公司排行,广告设计主要做什么,网站功能建设特点,怎么做自己的微信公众号图的存储方式
1. 邻接表#xff08;记录关于某点的直接相邻点#xff09;
2. 邻接矩阵#xff08;一定是正方形的矩阵#xff0c;对点进行编号#xff0c;点到点的权值由距震中的值表示#xff0c;无直接相连记为正无穷#xff09; 图的模板
unordered_mapint,No…图的存储方式
1. 邻接表记录关于某点的直接相邻点
2. 邻接矩阵一定是正方形的矩阵对点进行编号点到点的权值由距震中的值表示无直接相连记为正无穷 图的模板
unordered_mapint,Node
unordered_setEdge
Node类值、入度、出度、点发散出去的边连接的邻居、属于该点的边
Edge类权值距离、起始点from、终止点to 图的宽度优先遍历 使用unordered_set来进行去重放置重复点进队列 图的深度优先遍历 拓扑排序
有向无环图先处理入度为0的点然后将该点及其影响擦掉继续寻找入度为0的点周而复始。 无向图生成最小生成树K算法 P算法
保证连通性且整体边权值最小
K算法从边的角度出发
1. 对所有边排序从最小开始考虑
2. 如果加上该边没有形成环则加上若形成环则考虑下一条边
怎么考虑会不会形成环假设所有点一开始自己是个集合都不连通判断是否有环看一条边的from和to在不在一个集合若不在将两个点所在集合合并。
P算法
1. 所有边都被锁定
2. 从某点出发将该点直接相连的所有边解锁选权值最小的边且左右两侧不在一个模型内将邻点加入周而复始。 Dijkstra算法要求没有累加权值为负数的环
规定出发点 该点到所有点的最短距离
1. 初始化到自己0到别的点正无穷
2. 从当前最小值对应的点出发看其所有的边发现了更短的距离则改写
3. 周而复始即可直到所有点都作为出发点被遍历到
