文章
77
粉丝
9
获赞
2
访问
7.4k
1)存在拓扑序列的前提是图中没有出现环路,而出现唯一拓扑序列的前提是,在去除入度为0的顶点时,只存在一个入度为0的顶点;若在去除入度为0的顶点过程中发现环路或是发现多个入度为0的顶点则返回0;如果遍历结束都没有函数返回,则返回1
2)
int InDegree[MAXV]; //事先保存了各个顶点的入度
bool IsSearch[MAXV]; //记录已经访问过的顶点,防止重复访问
Queue Q;
int IsFailed;
void topology(MGraph G, int v) {
InitQueue(Q);
int tempV;
int count=0; //记录当前入度为0的顶点数
for (int i=0; i<G.numVertices; i++) {
if (!G.Edge[v][i]) {
InDegree[i]--;
}
if (!G.Edge[v][i] && IsSearch[i] == false) {
IsSearch[i] = true;
EnQueue(Q, i);
}
}
if (count==0) {
return;
}
if (count>1) {
IsFailed = true;
return;
}
while (!IsEmpty(Q)) {
DeQueue(Q, tempV);
topology(G, tempV);
}
}
int uniquely(MGraph G) {
InitQueue(Q);
for (int i=0; i<G.numVertices; i++) {
if (!InDegree[i]) {
topology(G, i);
IsSearch[i] = true;
...
登录后发布评论
暂无评论,来抢沙发