PTA拓扑排序 实现拓扑排序算法

觉得很有必要聊一下这道题, 迄今为止, 唯一一次提交了 13 次才 AC 的题目. 心中有火, 必须喷一下.

题目描述

试实现拓扑排序算法。函数void FindInDegree(ALGraph G,int indegree[])实现图中各个顶点入度的统计；函数int TopologicalSort(ALGraph G , int topo[])获取拓扑序列。

函数接口定义：

void FindInDegree(ALGraph G,int indegree[]);
int TopologicalSort(ALGraph G , int topo[]);

其中 G 是基于邻接表及逆邻接表存储表示的有向图，indegree存放个顶点的入度，topo存放拓扑序列。

裁判测试程序样例：

#include <iostream>
using namespace std;

#define MVNum 100 
typedef char VerTexType;

typedef struct ArcNode{
    int adjvex;          
    struct ArcNode *nextarc;
}ArcNode; 

typedef struct VNode{ 
    VerTexType data; 
    ArcNode *firstarc; 
}VNode, AdjList[MVNum];

typedef struct{ 
    AdjList vertices; //邻接表
	AdjList converse_vertices;//逆邻接表
    int vexnum, arcnum; 
}ALGraph;

int CreateUDG(ALGraph &G);//创建图，实现细节隐藏
void FindInDegree(ALGraph G,int indegree[]);
int TopologicalSort(ALGraph G , int topo[]); 

int main(){
	ALGraph G;
	CreateUDG(G);
	int *topo = new int [G.vexnum];
	if(TopologicalSort(G , topo)){
		for(int j = 0 ; j < G.vexnum; j++){
			if(j != G.vexnum - 1)
				cout << G.vertices[topo[j]].data << ",";
			else
				cout << G.vertices[topo[j]].data ;
		}
	}
	else
		cout << "Ring in net";
	return 0;
}
/* 请在这里填写答案 */

输入样例：

第1行输入结点数vexnum和边数arcnum。第2行输入vexnum个字符表示结点的值，接下来依次输入arcnum行，每行输入2个字符v和u，表示v到u有一条有向边。

6 9
1 2 3 4 5 6
1 2
1 3
1 4
3 2
3 5
4 5
4 3
6 4
6 5

输出样例：

输出拓扑序列。

6,1,4,3,2,5 

不好的地方

拓扑排序, 思路很简单, 就是每次从图里面选入度为 0 的节点. 具体参见我的另外一篇文章, 图算法

第一点, 题目没有给出是哪种拓扑排序, 按道理来说用 stack 和 queue 得到的拓扑排序序列都不能算错

第二点, 题目描述错误
这个存放拓扑序列是几个意思, 描述为存放顶点序列在 vertices 里面的位置还好一点吧

第三点, 我觉得可以不需要逆邻接表, 有点多余

第四点, 函数设计要求不规范

AC代码

int find(ALGraph& g, char t) {
	for (int i = 0; i != g.vexnum; i++) {
		if (g.vertices[i].data == t)
			return i;
	}
	return -1;
}
void FindInDegree(ALGraph G, int indegree[]) {
	for (int i = 0; i != G.vexnum; i++) {
		for (auto p = G.vertices[i].firstarc; p; p = p->nextarc) {
			indegree[p->adjvex]++;
		}
	}
}
#include<stack>
int TopologicalSort(ALGraph G, int topo[]) {
	int indegree[1000]{0};	
	FindInDegree(G, indegree);
	int count = 0;
	stack<VNode> st;
	for (int i = 0; i != G.vexnum; i++) {
		if (indegree[i] == 0)			
			st.push(G.vertices[i]);
	}
	while (!st.empty()) {		
		auto temp = st.top(); st.pop();
		topo[count++]=find(G,temp.data);
		for (auto p = temp.firstarc; p; p = p->nextarc) {
			indegree[p->adjvex]--;
			if (indegree[p->adjvex] == 0)				
				st.push(G.vertices[p->adjvex]);
		}
	}
	if (count < G.vexnum)
		return 0;
	else
		return 1;
}

欢迎给出更好的解法