程序填空题:The topological sort with a stack
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]
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]