大概意思就是必須過了A才能到B這種關系。每到一個點 必須有前提條件醬紫
思路是找到入度為0的點。加入一個棧或者隊列這些容器
然后 挨個找與之相連系的點 。
然后由于這個頂點已經被用了 那么被指向這些點的入度就可以-1
然后當有一個度變成0了,就把他加入容器里,接著循環找入度為0的頂點。
有點像BFS。
這每一個入度為0的頂點。就是拓撲排序出來的順序了。
完整馬 我寫的這個是不能有環的馬
#ifndef H_HPP#define H_HPP#include <iostream>#include <algorithm>#include <queue>using namespace std;std::queue<int>myQ;template<typename T>struct Node{ int Edge; Node<T>*pNext;};template<typename T>struct Head{ int data; Node<T>*pnode;};template<typename T>class G{ int m;//這個馬里面默認6 8了哈 int n; Head<T>*pHead; public: G(); ~G(); void show(); void topological_sort(); };template<typename T>G<T>::G(){ m = 6; n = 8; pHead = new Head<T>[m]; for (int i = 0; i < m; i++) { pHead[i].data = 0; pHead[i].pnode = nullptr;//初始化鄰接表 } for (int i = 0; i < n; i++) { int a, b;//a->b std::cout << "input /n"; std::cin >> a >> b; Node<T>*p = new Node<T>; p->Edge = b-1;//指向的點 p->pNext = pHead[a - 1].pnode; pHead[a - 1].pnode = p; pHead[b - 1].data++;//有點指向他 所以入度++ } show(); topological_sort();}template<typename T>G<T>::~G(){ for (int i = 0; i < m; i++) { Node<T>*p = pHead[i].pnode; while (p) { Node<T>*d = p; p = p->pNext; delete d; d = nullptr; } } delete[]pHead;}template<typename T>void G<T>::topological_sort(){ for (int i = 0; i < m; i++) { if (pHead[i].data==0) { myQ.push(i); } } while (myQ.size()!=0) { int key = myQ.front(); myQ.pop(); std::cout << key+1 <<std::endl; for (Node<T>*p = pHead[key].pnode; p; p = p->pNext) { int k = p->Edge; pHead[k].data--; if (pHead[k].data==0) { myQ.push(k); } } }}template<typename T>void G<T>::show(){ for (int i = 0; i < m; i++) { cout << "DATA = "<<pHead[i].data<<" Vertex is "<<i + 1 << " connect "; for (Node<T>*p = pHead[i].pnode; p; p = p->pNext) { int k = p->Edge; cout << k+1<<" "; } cout << endl; }}#endif //H_HPP#include "h.hpp"int main(){ G<int> g; system("pause");}運行結果。
新聞熱點
疑難解答
圖片精選