昆明购物网站建设,上海工程有限公司,深圳定制网站制作费用,有网站可以接设计的单子做吗文章目录1. 拓扑排序2. 算法实现2.1 Kahn算法2.2 DFS算法2.3 时间复杂度3. 应用4. 类似题目练习一个项目往往会包含很多代码源文件。编译器在编译整个项目时#xff0c;需按照依赖关系#xff0c;依次编译每个源文件。比如#xff0c;A.cpp依赖B.cpp#xff0c;那在编译时需按照依赖关系依次编译每个源文件。比如A.cpp依赖B.cpp那在编译时编译器需要先编译B.cpp才能编译A.cpp。编译器通过分析源文件或者编译配置文件比如Makefile文件来获取这种局部的依赖关系。那编译器又该如何通过源文件两两之间的局部依赖关系确定一个全局的编译顺序呢1. 拓扑排序 可以把源文件与源文件之间的依赖关系抽象成一个有向图。每个源文件对应图中的一个顶点源文件之间的依赖关系就是顶点之间的边。如果a先于b执行也就是说b依赖于a那么就在顶点a和顶点b之间构建一条从a指向b的边。而且这个图不仅要是有向图还要是一个有向无环图也就是不能存在像a-b-c-a这样的循环依赖关系。
数据结构如下
#include list
using namespace std;
class Graph
{int v;//顶点个数listint *adj;//邻接表
public:Graph(int vn){v vn;adj new listint [v];}~Graph(){delete [] adj;}void addEdge(int s, int t)//s先于t,边s-t{adj[s].push_back(t);}
};2. 算法实现
2.1 Kahn算法
Kahn 算法是贪心思想如果 s 需要先于 t 执行就添加一条 s 指向 t 的边。如果某个顶点入度为0也就表示没有任何顶点必须先于这个顶点执行那么这个顶点就可以执行了。先从图中找出一个入度为0的顶点将其输出并删除这个顶点也就是把这个顶点可达的顶点的入度都减1。我们循环执行上面的过程直到所有的顶点都被输出。最后输出的序列就是满足局部依赖关系的拓扑排序。
/*** description: 拓扑排序有向无环图* author: michael ming* date: 2019/7/29 0:36* modified by: */
#include list
#include iostream
#include queueusing namespace std;
class G_Node //节点类
{
public:char info;//节点存储信息int indegree;//节点入度G_Node(char ch /):info(ch),indegree(0){};
};
class Graph //图类
{int v; //顶点个数listG_Node* *adj; //邻接表G_Node *pGNode;//节点
public:Graph(int vn){v vn;adj new listG_Node* [v];pGNode new G_Node [v];cout 请顺序输入节点的信息 endl;char ch;for(int i 0; i v; i)cin pGNode[i].info;}~Graph(){delete [] pGNode;delete [] adj;}int findIdx(char ch){for(int i 0; i v; i){if(pGNode[i].info ch)return i;}return -1;}void addEdge(char s, char t)//s先于t,边s-t{int i findIdx(s), j findIdx(t);if(i ! -1 j ! -1){adj[i].push_back(pGNode[j]);pGNode[j].indegree;}}void topoSortByKahn(){int i, j, k;queueG_Node* nodeQueue;//坑要存指针在里面后面才能修改入度否则修改的是副本G_Node *frontNode;listG_Node*::iterator it;for(i 0; i v; i){if(pGNode[i].indegree 0)nodeQueue.push(pGNode[i]);//找到所有入度为0的入队}while(!nodeQueue.empty()){frontNode nodeQueue.front();i findIdx(frontNode-info);nodeQueue.pop();cout frontNode-info -;//输出入度为0的出队for(it adj[i].begin(); it ! adj[i].end(); it){(*it)-indegree--;//该节点后面跟着的所有节点入度-1if((*it)-indegree 0)//入度如果等于0nodeQueue.push(*it);//入队一会可以打印了}}}
};
int main()
{Graph grp(6);grp.addEdge(a,b);grp.addEdge(b,e);grp.addEdge(b,d);grp.addEdge(d,c);grp.addEdge(d,f);grp.topoSortByKahn();return 0;
}2.2 DFS算法
构造逆邻接表。邻接表中边 s-t 表示 s 先于 t 执行也就是 t 要依赖 s。在逆邻接表中边 s-t 表示 s 依赖于 ts 后于 t 执行。递归处理每个顶点。对顶点 i 先输出它可达的所有顶点也就是先把它依赖的所有的顶点输出了然后再输出自己。
在上面程序代码中添加
listG_Node* *reverseadj; //逆邻接表
reverseadj new listG_Node* [v];void addEdge(char s, char t)//s先于t,边s-t
{int i findIdx(s), j findIdx(t);if(i ! -1 j ! -1){adj[i].push_back(pGNode[j]);//s-t邻接表pGNode[j].indegree;reverseadj[j].push_back(pGNode[i]);//逆邻接表}}void topoSortByDFS()
{cout topoSortByDFS: endl;bool *visited new bool [v];memset(visited,0,v*sizeof(bool));for(int i 0; i v; i) //深度优先遍历{if(visited[i] false){visited[i] true;dfs(i, reverseadj, visited);}}delete [] visited;
}
void dfs(int i, listG_Node* *reverseadj, bool *visited)
{int idx;for(auto it reverseadj[i].begin(); it ! reverseadj[i].end(); it){idx findIdx((*it)-info);if(visited[idx] true)continue;visited[idx] true;dfs(idx,reverseadj,visited);}cout pGNode[i].info -;
}2.3 时间复杂度
Kahn代码中每个顶点被访问了一次每个边也都被访问了一次所以Kahn算法的时间复杂度就是OVEV表示顶点个数E表示边的个数。DFS算法中每个顶点被访问两次每条边都被访问一次所以时间复杂度也是OVE。注意这里的图可能不是连通的有可能是有好几个不连通的子图构成所以E并不一定大于VV E的大小关系不定。所以在表示时间复杂度的时候V、E都要考虑在内。
3. 应用
拓扑排序应用非常广泛。凡是需要通过局部顺序来推导全局顺序的一般都能用拓扑排序来解决。拓扑排序还能检测图中环的存在。对于Kahn算法来说如果最后输出出来的顶点个数少于图中顶点个数图中还有入度不是0的顶点那就说明图中存在环。关于图中环的检测递归那节讲过一个例子在查找最终推荐人的时候可能会因为脏数据造成存在循环推荐比如用户A推荐了用户B用户B推荐了用户C用户C又推荐了用户A。如何避免这种脏数据导致的无限递归 这就是环的检测问题。因为我们每次都只是查找一个用户的最终推荐人所以我们并不需要动用复杂的拓扑排序算法而只需要记录已经访问过的用户ID当用户ID第二次被访问的时候就说明存在环。
4. 类似题目练习
LeetCode 207. 课程表拓扑排序 LeetCode 210. 课程表 II拓扑排序 LeetCode 269. 火星词典拓扑排序 LeetCode 851. 喧闹和富有拓扑排序 LeetCode 1136. 平行课程拓扑排序 LeetCode 1203. 项目管理两次拓扑排序 LeetCode 5665. 从相邻元素对还原数组拓扑排序 LeetCode 5699. 从第一个节点出发到最后一个节点的受限路径数迪杰斯特拉 拓扑排序
