C로 그래프 그리기... ( 깊이 우선 탐색 알고리즘 )

그래프란 마디를 가지에 연결한 것이다.  쉽게 풀면 점을 선으로 연결한것이 그래프...


그래프를 데이터로 하여 표현하기 위해서 인접 행렬을 많이 사용...

그래프란.. 단방향 그래프와  양방향 그래프, 무방향(방향이 없는) 그래프로 나타 낼수 있다.


depth first search   깊이 우선 탐색 알고리즘

시발점은 출발하여 번호가 빠른 순서로 진행하는 위치를 조사하고 나아가는곳 까지 진행한다.

나아갈 장소가 없었으면 나아갈 장소가 있는 곳까지 되돌아가 다시 나아갈 곳까지 진행한다.

나아갈 장소가 전혀 없으면 끝낸다. ( 온길은 되돌아 간다. )

#include <stdio.h>

#define N 8

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

int v[N+1];

void visit(int);
void main(void)
{
     int i;

    for(i=1;i<=N;i++)
   {
        v[i]=0;
   }
    visit(1);
}
void visit(int i)
{
    int j;
    v[i]=1;
    for(j=1;j<=N;J++)
    {
        if(a[i][j]==1 && v[j] == 0)
        {
            printf(" %d -> %d ", i , j );
            visit(j);
        }
    }
}

==================================================================================
ret
1->2 2->3 3->7 7->6 6->5 5->4 6->8