스 택 을 사용 하여 DFS 구현 (비 재 귀적 DFS)

사진 발췌: 클릭 하여 링크 열기
#include 
#include 

#define N 4 //       

int a[N][N] = {{-1,1,1,-1},{1,-1,-1,1},{1,-1,-1,1},{-1,1,1,-1}}; //    ,-1  
int label[N] = {0}; //    ,0   

//       
struct Stack
{
    int a[4]; //     
    int top; //    
};
typedef struct Stack Stack;

void addStack(Stack *s, int data) //  
{
    s->top++;
    s->a[s->top] = data;
}

int delStack(Stack *s) //  
{
    return s->a[s->top--];
}

int getTop(Stack *s) //      
{
    return s->a[s->top];
}

//       DFS
void dfs(int start)
{
    Stack *s = (Stack *)malloc(sizeof(Stack));
    s->top = -1;
    printf("%d ", start);
    label[start] = 1;
    addStack(s, start);
    while(s->top != -1)
    {
        int tmp = getTop(s);
        int i;
        for(i=0; i<4; i++)
        {
            if(a[tmp][i] == 1 && label[i] == 0)
            {
                printf("%d ", i);
                label[i] = 1;
                addStack(s, i);
                break; //     break,     DFS
            }
        }
        if(i == 4)
            delStack(s);
    }
    free(s);
}

int main()
{
    dfs(0);
    return 0;
}

좋은 웹페이지 즐겨찾기