IoC控制反转  1996年，Michael Mattson在一篇有关探讨面向对象框架的文章中，首先提出了IOC(Inversion of Control)这个概念。IOC理论提出的观点：借助于“第三方”实现具有依赖关系的对象之间的解耦。全部对象的控制权全部上缴给“第三方”IOC ...

  Kruskal算法是一步步将森林中的树进行合并；而Prim算法是通过每次增加一条边来建立一棵树。   Prim算法基本思想：首先选择任意一个顶点，从该顶点开始构造生成树；接下来要找出一条边添加到生成树，这需要枚举每一个树顶点到每一个非树顶点的所有边，然后找 ...

最小生成树：在含有n个顶点的连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通图的最小生成树。   Kruskal算法基本思想：首先按照边的权值进行从小到大排序，每次从剩余的边中选择权值较小的且边的两个顶点不在同一个集合内 ...

介绍  不相交集（Disjoint-set）也称并查集（Union-find set），对于n个不同且不相交元素， 不相交集为支持以下两种操作的数据结构。 找出给定元素所属的集合 合并两个集合 操作不相交集的操作： MAKE-SET(x)：建立一个有唯一元素x的集合，并且x ...

Dijkstra算法虽然好，但是不能解决带负权边的图。   想想Floyd-Warshall和Dijkstra算法，它们都是基于这样的事实：求两点之间的最短路径，看能否可以在路径中添加k个顶点来缩短路径。Dijkstra则是通过对dis数组进行V(顶点个数)轮松弛，得到单源最 ...

  迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。  Dijkstra算法每次找到离源点最近的一个顶点，然后以该顶点为中心进行扩展， ...

  Floyd-Warshall 算法采用动态规划方案来解决在一个有向图 G = (V, E) 上每对顶点间的最短路径问题，即全源最短路径问题（All-Pairs Shortest Paths Problem），其中图G允许存在权值为负的边，但不存在权值为负的回路。Floyd-W ...

  从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被 ...

  假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被 ...

定义  拓扑排序(Topological Order)是指：将一个有向无环图(Directed Acyclic Graph, DAG)进行排序而得到一个有序的线性序列。拓扑排序不必是唯一的，任何合理的排序都是可以的。 算法步骤 构造一个队列Q和拓扑排序的结果队列T； 把所有没有依 ...