学习C++拓扑排序

大概意思就是必须过了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");}运行结果。