拓扑排序的原理和达成
发布时间：2021-11-15 15:56:04 所属栏目：教程 来源：互联网
导读：定义 在图论中，由一个有向无环图组成的序列，只要满足下面两种情况则称为拓扑排序： 每个顶点只允许访问一次； 若顶点A在图中存在到达顶点B的路径，则不会存在顶点B到顶点A的路径，也就是说这条路径是单向的； 可以从这副图中发现，如果按照DFS的思想，那么
|
定义 在图论中，由一个有向无环图组成的序列，只要满足下面两种情况则称为拓扑排序： 每个顶点只允许访问一次； 若顶点A在图中存在到达顶点B的路径，则不会存在顶点B到顶点A的路径，也就是说这条路径是单向的； 可以从这副图中发现，如果按照DFS的思想，那么其访问结点的结果为 5,2,3,1,0,4，但是如果是拓扑排序的话，访问结点的结果为5,4,2,0,1,3，类似于多叉树的BFS 问题 拓扑排序可用来解决什么问题呢？比如说课程排序，编译依赖，类似凡是涉及到相关顺序的时间安排；还可以用来判断一幅有向图是否无环。 思路 根据前面提供的思想，首先想到的就是BFS，但是需要在BFS的基础上进行判断，只有入度为0的结点才能加入到队列中，其中每访问一个结点，则将该结点的入度减一。（因为多叉树的结点不可能存在环，所以其的BFS就不用担心入度的问题） 如果是按照DFS的思想，则需要在等待迭代完结点的连接邻接点后再把当前结点压入栈中。 实现 #include <iostream> #include <list> #include <stack> #include <queue> #include <vector> using namespace std; /** * 构建邻接矩阵 */ class Graph { public: Graph(int v); ~Graph(); list<int>* adj; //邻接表 vector<int> nums; //统计结点的入度 int V; //顶点数目 // 添加一条从start为起始点，end为终点的边 void addEdge(int start, int end); void bfs_topological_sort(); void dfs_topological_sort(); protected: void _bfs_topological_sort(vector<int> &result, queue<int>& queue); void _dfs_topological_sort(int v, bool visited[], stack<int>& stack); }; Graph::Graph(int v) : V(v) { adj = new list<int>[V]; nums.assign(v, 0); } Graph::~Graph() { } void Graph::addEdge(int start, int end) { this->adj[start].push_back(end); this->nums[end]++; } void Graph::_bfs_topological_sort(vector<int> &result, queue<int> &queue) { while (!queue.empty()) { int v = queue.front(); queue.pop(); result.push_back(v); for (auto itr = this->adj[v].begin(); itr != this->adj[v].end(); ++itr) { this->nums[*itr]--; //*itr结点的入度减1，也就是说删掉 v 到 *itr 的有向边 if (!this->nums[*itr]) { queue.push(*itr); } } } // 判断是否有环（正常情况下所有结点此时的入度都为0） for (int i = 0; i < V; i++) { if (this->nums[i] != 0) { cout << "have a ring"<< endl; } } } void Graph::bfs_topological_sort() { queue<int> queue; // 计算所有的入度为0的结点，作为起点 for (int i = V - 1; i >= 0; i--) { if (!this->nums[i]) { queue.push(i); } } vector<int> result; this->_bfs_topological_sort(result, queue); for (auto itr = result.begin(); itr != result.end(); itr++) { cout << *itr << "->"; } } void Graph::_dfs_topological_sort(int v, bool *visited, stack<int> &stack) { if (visited[v]) return ; visited[v] = true; for (auto itr = this->adj[v].begin(); itr != this->adj[v].end(); ++itr) { if (!visited[*itr]) { _dfs_topological_sort(*itr, visited, stack); } else { // 判断是否有环，不用可以删掉（用邻接矩阵表示更简单，临街表还是需要遍历才能知道是否两点之间是否连接） for (auto vitr = this->adj[*itr].begin(); vitr != this->adj[*itr].end(); ++vitr) { if (*vitr == v) { cout << "ring is "<< *itr << "->"<< v << endl; } } } } // 访问完结点所有的临街结点之后才加入到栈中 stack.push(v); } void Graph::dfs_topological_sort() { stack<int> stack; bool visited[V]; memset(visited, false, sizeof(visited)); for (int i = V - 1; i >= 0; i--) { if (!visited[i]) { _dfs_topological_sort(i, visited, stack); } } while (!stack.empty()) { int v = stack.top(); stack.pop(); cout << v << "->"; } }; int main() { // 构建邻接矩阵 Graph g(6); //6个结点 g.addEdge(5, 2); g.addEdge(5, 0); g.addEdge(4, 0); g.addEdge(4, 1); g.addEdge(2, 3); g.addEdge(3, 1); g.addEdge(1, 3); g.bfs_topological_sort(); g.dfs_topological_sort(); return 0; } 上面图的表现形式为邻接表，基本算法是用 BFS 和 DFS 来实现的；  （编辑：济南站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
