一、拓扑排序 什么是拓扑排序?简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。 回顾离散数学中关于偏序和全序的定义: 若集合X上的关系R是自反的,反对称的和传递的,则称R是集合X上的偏序关系。 设R是集合X上的偏序,如果对每个x,y∈X必有xRy或yRx,则称R是集合X上的全序关系。 直观地看,偏序指集合中仅有部分成员之间可比较,而全序指集合中全体成员之间均可比较下图所示的两个有向图,图中弧(x,y)表示x≤y,则(a)表示偏序,(b)表示全序。若在(a)的有向图上人为地加一个表示v…

2015年4月12日 0条评论 3点热度 阅读全文

/** * C++: Dijkstra算法获取最短路径(邻接表) * * @author judyge * @date 2014/04/24 */ #include <iomanip> #include <iostream> #include <vector> using namespace std; // 示例类:边的结构体(用来演示) class EData { public: char start; // 边的起点 char end; // 边的终点 int weight;…

2015年4月12日 0条评论 6点热度 阅读全文