devbox
Li_阴宅
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

33 邻接表：BFS实现拓扑排序_邻接表求拓扑排序

作者：Li_阴宅 | 2024-07-23 16:34:48

赞

踩

邻接表求拓扑排序

33 邻接表：BFS实现拓扑排序

作者: 冯向阳时间限制: 1S章节: DS:图

截止日期: 2022-06-30 23:55:00

问题描述 :

目的：使用C++模板设计并逐步完善图的邻接表抽象数据类型（ADT）。

内容：（1）请参照图的邻接矩阵模板类原型，设计并逐步完善图的邻接表ADT。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。）

（2）设计并实现一个算法，基于广度优先搜索的思想，对于给定的有向图（网），实现拓扑排序。如排序成功，返回true；否则返回false。无论排序是否成功，都请给出最终的排序结果。图的存储结构采用邻接表。将其加入到ADT中。

注意：DG（有向图）, DN（有向网）, UDG（无向图）, UDN（无向网）

提示：可以利用广度优先搜索（BFS）的思想来实现。和普通的广度优先搜索不同的是，一个结点只有当所有可以到达该结点的其它结点都已被访问后才可以被访问。BFS通常借助一个队列来实现，队列中存放的是可以被访问的结点。实现拓扑排序的过程如下：

（1）计算每个结点的入度，保存在数组inDegree中；

（2）检查inDegree中的每个元素，将入度为0的结点入队；

（3）不断从队列中将入度为0的结点出队，输出此结点，并将其对应的visit值赋为1，同时将该结点的入度不为0的后继结点的入度减1；如果某个邻接点的入度为0且未被访问过，则将其入队；

（4）重复步骤3，直到队列为空。如拓扑序列包含了图的全部结点，则排序成功，否则失败。

参考函数原型：

（1）重载形式1

//拓扑排序（仅提供拓扑排序是否成功） 

template<class TypeOfVer, class TypeOfEdge>

bool adjlist_graph<TypeOfVer, TypeOfEdge>::TopSort();

（2）重载形式2

//拓扑排序（不仅提供拓扑排序是否成功，排序序列存储在引用参数topsort[]中） 

template<class TypeOfVer, class TypeOfEdge>

bool adjlist_graph<TypeOfVer, TypeOfEdge>::TopSort(int &num, int topsort[]);

辅助函数：

//求有向图指定顶点的入度 

template<class TypeOfVer, class TypeOfEdge>

int adjlist_graph<TypeOfVer, TypeOfEdge>::Get_InDegree(int u);

图的邻接表模板类原型参考如下：

/* 边表的结点定义 */

template<class TypeOfEdge>

struct edgeNode

{

    int data;

    TypeOfEdge weight;

    edgeNode<TypeOfEdge> *next;

    edgeNode(const int &d, edgeNode<TypeOfEdge> *ptr = NULL) //构造函数，用于构造其他结点（无权图） 

    //函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面

    {

        next = ptr;

        data = d;

    }

    edgeNode(const int &d, const TypeOfEdge &w, edgeNode<TypeOfEdge> *ptr = NULL) //构造函数，用于构造其他结点（带权图） 

    //函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面

    {

        next = ptr;

        data = d;

        weight = w;

    }

    int getData(){ return data;}  //取得结点的序号（顶点集） 

    TypeOfEdge getWeight(){ return weight;}  //取得边集中对应边的权值 

    void SetLink( edgeNode<TypeOfEdge> *link ){ next = link; }  //修改结点的next域 

    void SetData( int value ){ data = value; }   //修改结点的序号（顶点集） 

    void SetWeight(TypeOfEdge value ){ weight = value; }   //修改边集中对应边的权值   

};

//图的邻接表类

template<class TypeOfVer, class TypeOfEdge>

struct verNode

{

    TypeOfVer ver;

    edgeNode<TypeOfEdge> *head;

    

    verNode(edgeNode<TypeOfEdge> *h = NULL){head = h;} 

    TypeOfVer getVer(){ return ver;}  //取得结点值（顶点集） 

    edgeNode<TypeOfEdge> *getHead(){ return head;}  //取得对应的边表的头指针 

    void setVer(TypeOfVer value){ ver = value;}  //设置结点值（顶点集） 

    void setHead(edgeNode<TypeOfEdge> *value){ head = value;}  //设置对应的边表的头指针

};

template <class TypeOfVer, class TypeOfEdge>

class adjlist_graph{

    private:

       int Vers;           //顶点数 

       int Edges;          //边数 

       verNode<TypeOfVer,TypeOfEdge> *verList;

       

       string GraphKind;     //图的种类标志 

       

       bool Delete_Edge( int u, int v ); 

       bool DFS(int u, int &num, int visited[]); //DFS遍历（递归部分）

       bool CheckRoute(int u, int v, int visited[]); //检查两个结点之间是否有路径存在（递归部分）

    public:

       adjlist_graph( const string &kd, int vSize, const TypeOfVer d[]); //构造函数构造一个只有结点没有边的图。 

       adjlist_graph( const string &kd, int vSize, int eSize, const TypeOfVer d[], int **e); 构造函数构造一个无权图。5个参数的含义：图的类型、结点数、边数、结点集和边集 

       adjlist_graph( const string &kd, int vSize, int eSize, const TypeOfVer d[], int **e, const TypeOfEdge w[]); //构造函数构造一个有权图。

       bool GraphisEmpty() { return Vers == 0; }  //判断图空否

       string GetGraphKind(){ return GraphKind; }

       bool GetVer(int u, TypeOfVer &data); //取得G中指定顶点的值 

       int GetFirstAdjVex(int u, int &v); //返回G中指定顶点u的第一个邻接顶点的位序（顶点集）。若顶点在G中没有邻接顶点，则返回-1

       int GetNextAdjVex(int u, int v, int &w); //返回G中指定顶点u的下一个邻接顶点（相对于v）的位序（顶点集）。若顶点在G中没有邻接顶点，则返回false

       bool PutVer(int u, TypeOfVer data); //对G中指定顶点赋值 

       bool InsertVer(const TypeOfVer &data); //往G中添加一个顶点 

       int LocateVer(TypeOfVer data); //返回G中指定顶点的位置 

       bool ExistEdge(int u, int v);

       bool PrintVer();  //输出顶点集 

       bool PrintAdjList();  //输出邻接矩阵 

       int GetVerNum(){ return Vers;}    //取得当前顶点数 

       int GetEdgeNum(){ return Edges;}  //取得当前边数   

       int Get_Degree(int u); //求指定顶点的（出）度（无向图/网：度； 有向图/网：出度 ）

       int Get_InDegree(int u); //求有向图指定顶点的入度

       bool GetWeight(int u, int v, int &w); //对于有权图，取两端点为v1和v2的边上的权值。获取成功，返回true；否则，返回false

       bool Insert_Edge(int u, int v); //无权图插入一条边

       bool Insert_Edge(int u, int v, TypeOfEdge w); //有权图插入一条边

       bool DeleteVer(const TypeOfVer &data); //往G中删除一个顶点 

       bool DeleteEdge( int u, int v ); //删除边 (外壳：有向（删除1条边）， 无向（删除2条边））

       void DFS_Traverse(int u); //DFS遍历（外壳部分）

       void BFS_Traverse(int u); //BFS遍历

       bool CheckRoute(int u, int v); //检查两个结点之间是否有路径存在（外壳部分）

       bool TopSort(); //拓扑排序

       ~adjlist_graph(); //析构函数 

};

输入说明 :

建图的输入数据格式参见建图的算法说明。（以有向图为例，调用重载形式2的函数）

第一行：图的类型

第二行：结点数

第三行：结点集

第四行：边数

第五行：边集

输出说明 :

第一行：顶点集

第二行：邻接表

空行

第三行：拓扑排序结果

第四行：true（排序成功）/false（排序失败）

输入范例 :

DG
8
A B C D E F G H
10
0 2
0 6
1 6
1 7
2 3
3 4
3 6
5 4
6 5
7 5

-------------------

A B C D E F G H

A->6->2->nullptr
B->7->6->nullptr
C->3->nullptr
D->6->4->nullptr
E->nullptr
F->4->nullptr
G->5->nullptr
H->5->nullptr

A->B->C->H->D->G->F->E
true

-------------------

这个真的有点t   m难 我也是抄抄补补 

反正我懒得去想了   等有时间再想 最近要考试了 事情有点多 见谅

AC代码

-------------

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <queue>
  10. #include <sstream>
  11. #include <stack>
  12. #include <map>
  13. #include <ctime>
  14. #include <array>
  15. #include <set>
  16. #include <list>
  17. using namespace std;
  18. //边的定义
  19. template<class TypeOfEdge>
  20. struct Edge_pair
  21. {
  22. 	int point = 0;
  23. 	TypeOfEdge length = 0;
  24. 	//=================
  25. };
  26. //顶点的定义 
  27. template<class TypeOfVer, class TypeOfEdge>
  28. struct verNode
  29. {
  30. 	TypeOfVer ver_data;
  31. 	list<Edge_pair<TypeOfEdge> > group;
  32. 	//构造函数，默认会讲头指针设为空.
  33. 	verNode()
  34. 	{
  35. 		group.clear();
  36. 		//ver_data = 0;
  37. 	}
  38. 	//取得结点值（顶点） 估计是为了安全吧？？？
  39. 	TypeOfVer getVer()
  40. 	{
  41. 		return ver_data;
  42. 	}
  43. 	//取得对应的边表
  44. 	list<Edge_pair<TypeOfEdge> > getHead()
  45. 	{
  46. 		return group;
  47. 	}
  48. 	//设置结点值（顶点集） 估计是为了安全吧？？？
  49. 	void setdata(TypeOfVer value)
  50. 	{
  51. 		ver_data = value;
  52. 		return;
  53. 	}
  54. 	//=====================================================
  55.  
  56. 	void creat_Point(int new_point, TypeOfEdge new_length)
  57. 	{
  58. 		Edge_pair<TypeOfEdge> Next_p;
  59. 		Next_p.point = new_point;
  60. 		Next_p.length = new_length;
  61. 		group.insert(group.begin(), Next_p);
  62. 		return;
  63. 	}
  64. 	//删除指定位置顶点
  65. 	void del_Point(int n)
  66. 	{
  67.  
  68. 		return;
  69. 	}
  70. };
  71.  
  72. template <class TypeOfVer, class TypeOfEdge>//顶点元素类型，边权值类型
  73. class adjlist_graph {
  74. private:
  75. 	int Vers;//顶点数 
  76. 	int Edges;//边数 
  77. 	vector<verNode<TypeOfVer, TypeOfEdge> >ver;//顶点存储
  78. 	string GraphKind;//图的种类标志 
  79. 	bool have_dir = false, have_w = false;//图类型参数
  80.  
  81. 	vector<TypeOfVer> dfs_map;
  82. 	vector<bool> dfs_vis;
  83. 	//======================================================================
  84. 	bool Delete_Edge(int u, int v)//删除一条边
  85. 	{
  86. 		return false;
  87. 	}
  88. 	bool DFS(int t)//DFS遍历（递归部分）
  89. 	{
  90. 		dfs_map.push_back(ver[t].ver_data);
  91. 		dfs_vis[t] = true;
  92. 		for (auto i = ver[t].group.begin(); i != ver[t].group.end(); i++)
  93. 			if (dfs_vis[i->point] == false)
  94. 				DFS(i->point);
  95. 		return true;
  96. 	}
  97.  
  98. public:
  99. 	//一个空的构造函数
  100. 	adjlist_graph()
  101. 	{
  102. 		Edges = 0;
  103. 		Vers = 0;
  104. 	}
  105. 	//假的析构函数 
  106. 	~adjlist_graph()
  107. 	{
  108. 		;//你电脑内存就640K吗？
  109. 	}
  110. 	//判断图空否
  111. 	bool GraphisEmpty()
  112. 	{
  113. 		return Vers == 0;
  114. 	}
  115. 	//获取图的类型
  116. 	string GetGraphKind()
  117. 	{
  118. 		return GraphKind;
  119. 	}
  120. 	//取得当前顶点数 
  121. 	int GetVerNum()
  122. 	{
  123. 		return Vers;
  124. 	}
  125. 	//取得当前边数 
  126. 	int GetEdgeNum()
  127. 	{
  128. 		return Edges;
  129. 	}
  130. 	//自动建立临接表
  131. 	bool Auto_build(void)
  132. 	{
  133. 		//DG（有向图）, DN（有向网）, UDG（无向图）, UDN（无向网）
  134. 		/*第一行：图的类型  DN UDN
  135. 		第二行：结点数
  136. 		第三行：结点集
  137. 		第四行：无边标记
  138. 		第五行：边数
  139. 		第六行：边集
  140. 		第七行：权集*/
  141.  
  142. 		/*第一行：图的类型  DG UDG
  143. 		第二行：结点数
  144. 		第三行：结点集
  145. 		第四行：边数
  146. 		第五行：边集*/
  147. 		cin >> GraphKind;//图的类型 
  148. 		cin >> Vers;//结点数
  149. 		ver.resize(Vers);//开辟节点空间
  150. 		for (int i = 0; i < Vers; i++)//结点集
  151. 		{
  152. 			TypeOfVer now;
  153. 			cin >> now;
  154. 			ver[i].setdata(now);
  155. 		}
  156.  
  157.  
  158. 		cin >> Edges;//边数
  159. 		vector<int> x_p, y_p, w_p;
  160. 		for (int i = 0; i < Edges; i++)
  161. 		{
  162. 			int c_x, c_y;
  163. 			cin >> c_x >> c_y;
  164. 			x_p.push_back(c_x);
  165. 			y_p.push_back(c_y);
  166. 		}
  167. 		//图的类型识别
  168.  
  169. 		if (GraphKind == "DG")//DG（有向图）
  170. 			have_dir = true, have_w = false;
  171. 		if (GraphKind == "DN")//DN（有向网）
  172. 			have_dir = true, have_w = true;
  173. 		if (GraphKind == "UDG")//UDG（无向图）
  174. 			have_dir = false, have_w = false;
  175. 		if (GraphKind == "UDN")//UDN（无向网）
  176. 			have_dir = false, have_w = true;
  177.  
  178. 		if (have_w)
  179. 			for (int i = 0; i < Edges; i++)
  180. 			{
  181. 				int c_w;
  182. 				cin >> c_w;
  183. 				w_p.push_back(c_w);
  184. 			}
  185.  
  186.  
  187. 		for (int i = 0; i < Edges; i++)
  188. 		{
  189. 			if (have_dir)
  190. 				if (have_w)
  191. 					ver[x_p[i]].creat_Point(y_p[i], w_p[i]);
  192. 				else
  193. 					ver[x_p[i]].creat_Point(y_p[i], 0);
  194. 			else
  195. 				if (have_w)
  196. 					ver[x_p[i]].creat_Point(y_p[i], w_p[i]), ver[y_p[i]].creat_Point(x_p[i], w_p[i]);
  197. 				else
  198. 					ver[x_p[i]].creat_Point(y_p[i], 0), ver[y_p[i]].creat_Point(x_p[i], 0);
  199. 		}
  200. 		return 1;
  201. 	}
  202. 	//取得G顶点的组
  203. 	vector<TypeOfVer> GetVer(void)
  204. 	{
  205. 		vector<TypeOfVer> head_group;
  206. 		for (int i = 0; i < Vers; i++)
  207. 		{
  208. 			head_group.push_back(ver[i].getVer());
  209. 		}
  210. 		return head_group;
  211. 	}
  212. 	//输出邻接表 
  213. 	bool Print_photo()
  214. 	{
  215. 		int i;
  216. 		for (i = 0; i < Vers; i++)
  217. 		{
  218. 			cout << ver[i].getVer();
  219. 			if (ver[i].group.size() != 0)
  220. 				cout << "->";
  221. 			else
  222. 			{
  223. 				cout << "->nullptr" << endl;
  224. 				continue;
  225. 			}
  226. 			vector<Edge_pair<TypeOfEdge> > out_lis;
  227. 			out_lis.clear();
  228. 			for (auto j = ver[i].group.begin(); j != ver[i].group.end(); j++)
  229. 			{
  230. 				out_lis.push_back(*j);
  231. 			}
  232. 			int j;
  233. 			for (j = 0; j < out_lis.size() - 1; j++)
  234. 				if (have_w)
  235. 					cout << out_lis[j].point << "(" << out_lis[j].length << ")" << "->";
  236. 				else
  237. 					cout << out_lis[j].point << "->";
  238. 			if (have_w)
  239. 				cout << out_lis[j].point << "(" << out_lis[j].length << ")" <<"->nullptr" << endl;
  240. 			else
  241. 				cout << out_lis[j].point <<"->nullptr" << endl;
  242. 		}
  243. 		return 1;
  244. 	}
  245. 	//往G中添加一个顶点 
  246. 	bool InsertVer(const TypeOfVer& data)
  247. 	{
  248. 		verNode<TypeOfVer, TypeOfEdge> new_e;
  249. 		new_e.setdata(data);
  250. 		ver.push_back(new_e);
  251. 		Vers++;
  252. 		return true;
  253. 	}
  254. 	//寻找顶点位置
  255. 	int Look_Ver(const TypeOfVer& data)
  256. 	{
  257. 		int i;
  258. 		for (i = 0; i < Vers; i++)
  259. 			if (ver[i].ver_data == data)
  260. 				return i;
  261. 		return -1;
  262. 	}
  263. 	//删除一个顶点
  264. 	bool del_Point(int place)
  265. 	{
  266. 		int need_del = 0;
  267. 		if (!(0 <= place && place < Vers))
  268. 			return false;
  269. 		int i;
  270. 		for (i = 0; i < Vers; i++)
  271. 		{
  272. 			for (auto j = ver[i].group.begin(); j != ver[i].group.end(); j++)
  273. 			{
  274. 				if (j->point == place)
  275. 				{
  276. 					need_del++;
  277. 					ver[i].group.erase(j);
  278. 					break;
  279. 				}
  280. 			}
  281. 			for (auto j = ver[i].group.begin(); j != ver[i].group.end(); j++)
  282. 			{
  283. 				if (j->point > place)
  284. 					j->point--;
  285. 			}
  286. 		}
  287. 		need_del += ver[place].group.size();
  288. 		ver.erase(ver.begin() + place);
  289. 		Vers--;
  290. 		if (have_dir)
  291. 			Edges -= need_del;
  292. 		else
  293. 			Edges -= (need_del / 2);
  294. 		return true;
  295. 	}
  296. 	//无权图插入一条边
  297. 	bool Insert_Edge(int u, int v)
  298. 	{
  299. 		if (!(0 <= u && u < Vers))
  300. 			return false;
  301. 		if (!(0 <= v && v < Vers))
  302. 			return false;
  303. 		for (auto i = ver[u].group.begin(); i != ver[u].group.end(); i++)
  304. 		{
  305. 			if (i->point == v)
  306. 				return false;
  307. 		}
  308. 		for (auto i = ver[v].group.begin(); i != ver[v].group.end(); i++)
  309. 		{
  310. 			if (i->point == u)
  311. 				return false;
  312. 		}
  313. 		if (u == v)
  314. 			return false;
  315. 		if (have_dir)
  316. 		{
  317. 			Edges++;
  318. 			ver[u].creat_Point(v, 1);
  319. 			return true;
  320. 		}
  321. 		else
  322. 		{
  323. 			Edges++;
  324. 			ver[u].creat_Point(v, 1);
  325. 			ver[v].creat_Point(u, 1);
  326. 			return true;
  327. 		}
  328. 		return true;
  329. 	}
  330. 	//有权图插入一条边
  331. 	bool Insert_Edge(int u, int v, TypeOfEdge w)
  332. 	{
  333. 		if (!(0 <= u && u < Vers))
  334. 			return false;
  335. 		if (!(0 <= v && v < Vers))
  336. 			return false;
  337. 		for (auto i = ver[u].group.begin(); i != ver[u].group.end(); i++)
  338. 		{
  339. 			if (i->point == v)
  340. 				return false;
  341. 		}
  342. 		for (auto i = ver[v].group.begin(); i != ver[v].group.end(); i++)
  343. 		{
  344. 			if (i->point == u)
  345. 				return false;
  346. 		}
  347. 		if (u == v)
  348. 			return false;
  349. 		if (have_dir)
  350. 		{
  351. 			Edges++;
  352. 			ver[u].creat_Point(v, w);
  353. 			return true;
  354. 		}
  355. 		else
  356. 		{
  357. 			Edges++;
  358. 			ver[u].creat_Point(v, w);
  359. 			ver[v].creat_Point(u, w);
  360. 			return true;
  361. 		}
  362. 		return true;
  363. 	}
  364. 	//删除边 (外壳：有向（删除1条边）， 无向（删除2条边））
  365. 	bool del_Edge(int u, int v)
  366. 	{
  367. 		if (!(0 <= u && u < Vers))
  368. 			return false;
  369. 		if (!(0 <= v && v < Vers))
  370. 			return false;
  371. 		if (u == v)
  372. 			return false;
  373. 		bool ok = true;
  374. 		if (have_dir)
  375. 			for (auto i = ver[u].group.begin(); i != ver[u].group.end(); i++)
  376. 			{
  377. 				if (i->point == v)
  378. 				{
  379. 					ver[u].group.erase(i);
  380. 					Edges--;
  381. 					return true;
  382. 				}
  383. 			}
  384. 		else
  385. 		{
  386. 			for (auto i = ver[u].group.begin(); i != ver[u].group.end(); i++)
  387. 			{
  388. 				if (i->point == v)
  389. 				{
  390. 					ver[u].group.erase(i);
  391. 					break;
  392. 				}
  393. 			}
  394. 			for (auto i = ver[v].group.begin(); i != ver[v].group.end(); i++)
  395. 			{
  396. 				if (i->point == u)
  397. 				{
  398. 					ver[v].group.erase(i);
  399. 					Edges--;
  400. 					return true;
  401. 				}
  402. 			}
  403. 		}
  404.  
  405. 		return false;
  406. 	}
  407. 	//返回G中指定顶点u的第一个邻接顶点的位序（顶点集）。若顶点在G中没有邻接顶点，则返回-1
  408. 	int GetFirst_AdjVex(int u)
  409. 	{
  410. 		if (ver[u].group.empty())
  411. 			return -1;
  412. 		return ver[u].group.begin()->point;
  413. 	}
  414. 	//返回G中指定顶点u的下一个邻接顶点（相对于v）的位序（顶点集）。若顶点在G中没有邻接顶点，则返回false
  415. 	int GetNext_AdjVex(int u, int v)
  416. 	{
  417. 		if (ver[u].group.size() == 1)
  418. 			return -1;
  419. 		for (auto i = ver[u].group.begin(); i != ver[u].group.end(); i++)
  420. 		{
  421. 			if (i->point == v)
  422. 			{
  423. 				if ((++i) == ver[u].group.end())
  424. 					return -1;
  425. 				return i->point;
  426. 			}
  427. 		}
  428. 		return -1;
  429. 	}
  430.  
  431. 	//是否存在边
  432. 	bool look_Edge(int u, int v)
  433. 	{
  434. 		if (!(0 <= u && u < Vers))
  435. 			return false;
  436. 		if (!(0 <= v && v < Vers))
  437. 			return false;
  438. 		if (u == v)
  439. 			return false;
  440. 		for (auto i = ver[u].group.begin(); i != ver[u].group.end(); i++)
  441. 		{
  442. 			if (i->point == v)
  443. 				return true;
  444. 		}
  445. 		for (auto i = ver[v].group.begin(); i != ver[v].group.end(); i++)
  446. 		{
  447. 			if (i->point == u)
  448. 				return true;
  449. 		}
  450. 		return false;
  451. 	}
  452. 	//两个顶点之间的边的权值 失败返回-1
  453. 	int Get_legthOfEdge(int u, int v)
  454. 	{
  455. 		if (!have_w)
  456. 			return -1;
  457. 		if (!(0 <= u && u < Vers))
  458. 			return -1;
  459. 		if (!(0 <= v && v < Vers))
  460. 			return -1;
  461. 		if (u == v)
  462. 			return -1;
  463. 		for (auto i = ver[u].group.begin(); i != ver[u].group.end(); i++)
  464. 		{
  465. 			if (i->point == v)
  466. 				return i->length;
  467. 		}
  468. 		return -1;
  469. 	}
  470. 	//获取一个顶点的入度
  471. 	int Search_enterDegree(int p)
  472. 	{
  473. 		if (!(0 <= p && p < Vers))
  474. 			return -1;
  475. 		if (!have_dir)//is 无向图
  476. 			return ver[p].group.size();
  477. 		int cnt = 0;
  478. 		for (int i = 0; i < Vers; i++)
  479. 		{
  480. 			if (i != p)
  481. 				for (auto j = ver[i].group.begin(); j != ver[i].group.end(); j++)
  482. 				{
  483. 					if (j->point == p)
  484. 						cnt++;
  485. 				}
  486. 		}
  487. 		//cnt += ver[p].group.size();
  488. 		return cnt;
  489. 	}
  490. 	//获取一个顶点的出度
  491. 	int Search_outDegree(int p)
  492. 	{
  493. 		if (!(0 <= p && p < Vers))
  494. 			return -1;
  495. 		return ver[p].group.size();
  496. 	}
  497. 	bool look_haveDir(void)
  498. 	{
  499. 		return have_dir;
  500. 	}
  501. 	//DFS遍历（外壳部分）
  502. 	void DFS_Traverse(int star)
  503. 	{
  504. 		dfs_map.clear();
  505. 		dfs_vis.clear();
  506. 		for (int i = 0; i < Vers; i++)
  507. 			dfs_vis.push_back(false);
  508. 		DFS(star);
  509. 		int i;
  510. 		for (i = 0; i < dfs_map.size() - 1; i++)
  511. 			cout << dfs_map[i] << "->";
  512. 		cout << dfs_map[i] << endl;
  513. 		return;
  514. 	}
  515. 	//BFS遍历
  516. 	void BFS_Traverse(int star)
  517. 	{
  518. 		vector<TypeOfVer> bfs_lis;
  519. 		vector<bool>bfs_vis;
  520.  
  521. 		bfs_lis.clear();
  522. 		bfs_vis.clear();
  523. 		for (int i = 0; i < Vers; i++)
  524. 			bfs_vis.push_back(false);
  525.  
  526. 		queue<int> Q;
  527. 		Q.push(star);
  528. 		bfs_vis[star] = true;
  529. 		bfs_lis.push_back(ver[star].ver_data);
  530.  
  531. 		int now;
  532. 		while (!Q.empty())
  533. 		{
  534. 			now = Q.front();
  535. 			Q.pop();
  536. 			for (auto i = ver[now].group.begin(); i != ver[now].group.end(); i++)
  537. 				if (bfs_vis[i->point] == false)
  538. 				{
  539. 					bfs_lis.push_back(ver[i->point].ver_data);
  540. 					bfs_vis[i->point] = true;
  541. 					Q.push(i->point);
  542. 				}
  543. 		}
  544. 		int i;
  545. 		for (i = 0; i < bfs_lis.size() - 1; i++)
  546. 			cout << bfs_lis[i] << "->";
  547. 		cout << bfs_lis[i] << endl;
  548.  
  549. 		return;
  550. 	}
  551. 	//是否有路径
  552. 	bool Search_way(int star, int v)
  553. 	{
  554. 		vector<bool>bfs_vis;
  555.  
  556. 		bfs_vis.clear();
  557. 		for (int i = 0; i < Vers; i++)
  558. 			bfs_vis.push_back(false);
  559.  
  560. 		queue<int> Q;
  561. 		Q.push(star);
  562. 		bfs_vis[star] = true;
  563.  
  564. 		int now;
  565. 		while (!Q.empty())
  566. 		{
  567. 			now = Q.front();
  568. 			if (now == v)
  569. 				return true;
  570. 			Q.pop();
  571. 			for (auto i = ver[now].group.begin(); i != ver[now].group.end(); i++)
  572. 				if (bfs_vis[i->point] == false)
  573. 				{
  574. 					bfs_vis[i->point] = true;
  575. 					Q.push(i->point);
  576. 				}
  577. 		}
  578. 		return false;
  579. 	}
  580. 	//拓扑排序并判断有无回路 0 有 1 无
  581. 	bool TopologicalSort(void)
  582. 	{
  583. 		if (Edges == 0)
  584. 			return 0;
  585. 		int i, j;
  586. 		//将各个顶点的入度存在indegree
  587. 		vector<int> indegree;
  588. 		indegree.clear();
  589. 		//------
  590. 		for (i = 0; i < Vers; i++)
  591. 			indegree.push_back(Search_enterDegree(i));
  592. 		//------
  593. 		//入度为0，进栈。
  594. 		queue<int> S;
  595. 		//------
  596. 		for (i = 0; i < indegree.size(); i++)
  597. 			if (indegree[i] == 0)
  598. 				S.push(i);
  599. 		//------
  600. 		vector<int> sort_list;//the way of sort
  601. 		//BFS
  602. 		while (!S.empty())
  603. 		{
  604. 			int now;
  605. 			now = S.front();
  606. 			S.pop();
  607. 			sort_list.push_back(now);
  608. 			int next_p;
  609. 			next_p = GetFirst_AdjVex(now);//获取now的第一个相邻的点
  610. 			while (next_p != -1)
  611. 			{
  612. 				--indegree[next_p];
  613. 				if (indegree[next_p] == 0)
  614. 					S.push(next_p);
  615. 				/*if (indegree[next_p] == -1)
  616. 					S.push(next_p);*/
  617. 				next_p = GetNext_AdjVex(now, next_p);
  618. 			}
  619. 		}
  620. 		if (sort_list.size() == 0)
  621. 			return 0;
  622. 		//------
  623. 		for (i = 0; i < sort_list.size() - 1; i++)
  624. 			cout << ver[sort_list[i]].ver_data << "->";
  625. 		cout << ver[sort_list[i]].ver_data << endl;
  626. 		//------
  627. 		if (sort_list.size() < Vers)
  628. 			return 0;
  629. 		return 1;
  630. 	}
  631. };
  632.  
  633.  
  634. int main()
  635. {
  636. 	int i;
  637. 	adjlist_graph<string, int> a;
  638. 	a.Auto_build();
  639. 	vector <string> ans;
  640. 	ans = a.GetVer();
  641. 	for (i = 0; i < ans.size() - 1; i++)
  642. 		cout << ans[i] << " ";
  643. 	cout << ans[i] << endl;
  644. 	cout << endl;
  645. 	a.Print_photo();
  646. 	cout << endl;
  647. 	if (a.TopologicalSort())
  648. 		cout << "true" << endl;
  649. 	else
  650. 		cout << "false" << endl;
  651.  
  652.  
  653. 	return 0;
  654. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Li_阴宅/article/detail/870684
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号