Algorithms / Topological order 위상정렬(2)

// Graph. Topological order 위상정렬 폐쇄로(루프발생)

 

#include <stdio.h>
#define N 8

int a[N+1][N+1] =
{
{0,0,0,0,0,0,0,0,0},
{0,0,0,1,0,0,0,0,0},
{0,1,0,0,0,1,0,0,0},
{0,0,0,0,1,0,0,1,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,1,0,1,0,0},
{0,0,0,0,0,0,0,1,1},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,1,0}};

int v[N+1]; //visit
int s[N+1];

void visit(int);

int main(void) {
 
 int i;

 for(i=1; i<=N; i++)
  v[i]=0;

 for(i=1;i<=N;i++)
  if(v[i]==0)
   visit(i);

 for(i=N;i>=1;i--)
  printf("%d ", s[i]);

 printf("\n");
 return 0;
}

void visit(int i) {
 int j;
 static int sp = 1;
 v[i]=1;
 for(j=1; j<=N; j++) {
  if(a[i][j] == 1 && v[j] == 0)
   visit(j);
  if(a[i][j] == 1 && v[j] == 1) {
   printf("%d 와 %d 의 근처에 루프가 있습니다.\n", i, j);
  }
 }
 v[i]=2;
 s[sp++]=i;
}