【算法总结】图论-拓扑排序一、概念设有一个有向无环图（DAG图），对其进行拓扑排序即求其中结点的一个拓扑序列，对于所有的有向边（U，V）（由U指向V），在该序列中结点U都排列在结点V之前。满足该要求的结点序列，被称为满足拓扑次序的序列。求这个序列的过程，被称为拓扑排序。由满足拓扑次序序列的特征我们也能得出其如下特点：若...

【算法总结】图论-最短路径一、概念最短路径问题。即寻找图中某两个特定结点间最短的路径长度。所谓图上的路径，即从图中一个起始结点到一个终止结点途中经过的所有结点序列，路径的长度即所经过的边权和。 二、Floyd算法用邻接矩阵保存原图，那么此时邻接矩阵中edge[i][j]的值即表示从结点i到结点j，中间不经过任...

【算法总结】图论-最小生成树一、概念在一个无向连通图中，如果存在一个连通子图包含原图中所有的结点和部分边，且这个子图不存在回路，那么我们称这个子图为原图的一棵生成树。在带权图中，所有的生成树中边权的和最小的那棵（或几棵）被称为最小生成树。定理：在要求解的连通图中，任意选择一些点属于集合A，剩余的点属于集合B，必定存在一...

【算法总结】图论-并查集一、概念：并查集并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结...

【算法总结】图论-预备知识 邻接矩阵：用一个二维数组来表示图的相关信息，如edge[i][j]表示结点i和结点j之间的关系（以及权重）——在表示的图为稠密图，且频繁地判断特定结点对是否相邻时，使用邻接矩阵较为适宜。邻接链表：链式存储结构，为图的每个顶点建立一个单链表，第i个单链表中保存...

Dijkstra算法是图论中经典的最短路径算法之一，主要用于解决单源最短路径问题。单源最短路径问题,即求某个源节点到其他各个节点的最短路径。Dijkstra算法采用了贪心算法的思想，如图求1号节点到其他各个节点最短路径。首先从1号节点出发，扩展已知的最短路径集合，每次优先“松弛”最近的节点所相连...

Floyd算法是图论中经典的多源最短路径算法，即求任意两点之间的最短路径。 它可采用动态规划思想，因为它满足最优子结构性质，即最短路径序列的子序列也是最短路径。  举例说明最优子结构性质，上图中1号到5号的最短路径序列<1,2,4,5>，其子序列<1,2,4>也是最...

概述（总）DFS是算法中图论部分中最基本的算法之一。对于算法入门者而言，这是一个必须掌握的基本算法。它的算法思想可以运用在很多地方，利用它可以解决很多实际问题，但是深入掌握其原理是我们灵活运用它的关键所在。含义特点DFS即深度优先搜索，有点类似广度优先搜索，也是对一个连通图进行遍历的算法。它的思想是从一个顶点V0开始，...

简介：求最短路径算法中最具代表性的是Dijkstra算法。Dijkstra算法的思想是基于贪心策略的。概述其过程是通过设置顶点集合S并不断地做贪心选择来扩充集合。贪心选择的标准是每次都选择从源节点到该节点的路径长度最短。 难点：网络上博客中大多数人写的最短路径算法大多都是只能寻找到最短的一条路径。但是很多时候...

转自:https://blog.csdn.net/liangzhaoyang1/article/details/51602926  设G是所有边权均不相同的无向联通图。证明一：首先，易证图G中权值最小的边一定是最小生成树中的边。(否则最小生成树加上权值最小的边后构成一个环，去掉环中任意一条非此边则形...