자료구조 :: 그래프(3) 깊이 우선 탐색 : 한붓 그리기

# 오일러의 한붓 그리기

한붓 그리기 알고리즘
(1) 한번 지나간 간선을 지워가면서 이동할 수 있는 정점까지 이동한다.
(2) 도착한 정점이 시작점이고 모든 간선이 지워졌으면(지나갔으면), 지금까지의 경로가 하나의 해가된다.
(3) 더 이상 이동할 정점이 없으면 온 길을 되살려 하나씩 되돌아가면서 다음에 이동할 수 있는 위치를 찾는다.

#include <stdio.h> 
#define VERTEX 4// 정점의 갯수
#define EDGE 6// 간선의 갯수
#define START 1

int success, // 성공 여부 판단
    v[EDGE+1], // 지나간 간선을 저장할 스택
    n; // 통과한 간선의 수

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

void visit(int i) 
{ 
int k; 
    v[n]=i; 

if(n==0 && i==START) 
    { 
        printf("해 %d : ",++success); 
for(k=0;k<=EDGE;k++) 
            printf("%d",v[k]); 
        printf("\n"); 
    } 
else
    { 
for(k=1;k<=VERTEX;k++) 
        { 
if(a[i][k]!=0) // 간선 존재 여부 판단
            { 
                a[i][k]--;    a[k][i]--;  
                n--; 
                visit(k); 
                a[i][k]++;    a[k][i]++; 
                n++; 
            } 
        } 
    } 
} 

int main() 
{ 
    success=0; n=EDGE; 
    visit(START); 
if(success==0) 
        printf("해가 없음\n"); 
}