-->
当前位置:首页 > 题库 > 正文内容

程序填空题:The topological sort with a stack

Luz3年前 (2022-01-18)题库942
The following program implements the topological sort algorithm with a **stack**. Please fill in the blanks.

c++
void Topsort(int a[NUM][NUM], int TopNum[NUM])
// a[NUM][NUM] is adjacency matrix of the graph with NUM vertices
// TopNum[NUM] stores the topological orders
{ int S[NUM], Indegree[NUM]; //S[NUM] is a stack
int Counter = 0, top, n, i, j;
int V;
top= -1;
n=NUM;
for (j=0; j<n; j++) {
Indegree[j]=0;
for (i=0; i<n; i++)
if () Indegree[j]++;
if ( Indegree[j] == 0 ) S[++top]=j;
}
while (top>=0) {
V = S[top--];
TopNum[ V ] = ++ Counter; /* assign next */
for (j=0; j<n; j++)
if ( a[V][j]!=0)
if (== 0 ) S[++top]=j;
} /* end-while */
if ( Counter!=n ) printf( "Graph has a cycle" );
}








答案:
第1空:a[i][j]!=0

第2空:--Indegree[j]

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。