国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 編程 > C++ > 正文

學習C++拓撲排序

2019-11-08 03:19:57
字體:
來源:轉載
供稿:網友

大概意思就是必須過了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");}運行結果。


發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表

圖片精選

主站蜘蛛池模板: 明溪县| 林周县| 积石山| 乌苏市| 合肥市| 九江县| 安顺市| 永年县| 仪征市| 阜阳市| 盐边县| 石嘴山市| 东山县| 昌乐县| 永兴县| 兰考县| 绵阳市| 湖南省| 扎兰屯市| 乌审旗| 安顺市| 景东| 孟州市| 尚义县| 成安县| 梅河口市| 阳春市| 迁西县| 青田县| 苍山县| 东兰县| 垫江县| 怀集县| 许昌市| 阿尔山市| 乌拉特前旗| 泗阳县| 中山市| 罗城| 祁连县| 清原|