案例6-1.4 地下迷宫探索 (30分)--深度优先遍历

 

 

 解题思路：基本方法是用深度遍历思路

1、设y超点为a，则a入栈

2、栈非空，寻找起点a相邻节点，

    1）超点a存在相邻最小编号b节点,则再以b为起点，重复步骤1，2

    2）若超点a不存在相邻节点，则弹出栈顶元素a后，若此时栈不空，则置下一次起点为栈顶元素c，重复步骤1，2

  解法一、

#include <stdio.h>
#include <malloc.h>
#define ERROR -1
#define MaxVex 1000+1
#include <string.h>
typedef enum {false,true
             } bool;
int G[MaxVex][MaxVex];
int Nv,Ne;
int visit[MaxVex]= {0};
int Out[10000]= {0};
typedef struct {
    int *Data;
    int Top;
    int MaxSize;
}*Stack;
Stack S;
Stack CreateStack(int size) {
    Stack S=(Stack)malloc(sizeof(Stack));
    S->Data=(int *)malloc(sizeof(int)*size);
    S->MaxSize=size;
    S->Top=-1;
    return S;
}

bool IsEmpty(Stack S) {
    if(S->Top==-1)
        return true;
    return false;
}
bool IsFull(Stack S) {
    if(S->Top==S->MaxSize-1)
        return true;
    return false;
}
bool Push(Stack S,int x) {
    if(IsFull(S))
        return false;
    S->Data[++S->Top]=x;
    return true;
}
int Pop(Stack S) {
    if(IsEmpty(S))
        return ERROR;
    return S->Data[S->Top--];
}
int GetTop(Stack S) {
    if(IsEmpty(S))
        return ERROR;
    return S->Data[S->Top];
}
void Init() {//图初始化
    memset(G,0,sizeof(G));
    int i;
    int v1,v2;
    for(i=0; i<Ne; i++) {
        scanf("%d %d",&v1,&v2);
        G[v1][v2]=1;
        G[v2][v1]=G[v1][v2];
    }
}
int cnt=0,count=1;//count统计入栈顶点个数
void NON_DFS(int k) {
    int i;
    Push(S,k);
    visit[k]=1;
    Out[cnt++]=k;
    while(!IsEmpty(S)) {
        for(i=1; i<=Nv; i++) {
            if(!visit[i]&&G[k][i]) {
                Push(S,i);
                count++;
                visit[i]=1;
                Out[cnt++]=i;
                k=i;
                break;
            }
        }
        if(i>Nv) {
            Pop(S);
            if(!IsEmpty(S)) {
                k=GetTop(S);
                Out[cnt++]=k;
            }
        }
    }
}

int main() {
    int v;
    scanf("%d %d %d",&Nv,&Ne,&v);
    int i;
    for(i=1; i<=Nv; i++) {
        visit[i]=0;
    }
    S=CreateStack(MaxVex);
    Init();
    NON_DFS(v);
    for(i=0; i<cnt; i++) {
        if(i)
            printf(" ");
        printf("%d",Out[i]);
    }
    if(count!=Nv) {
        printf(" 0");
    }
    return 0;
}

解法二、用数组表示栈

#include <stdio.h>
#include <string.h>
#define MaxV 1000+1

int G[MaxV][MaxV];
int visit[MaxV];
int Nv,Ne,S;
int cnt=0;

int Stack[MaxV];
int Top=-1;

void Initial() {
    int i;
    memset(G,0,sizeof(G));
    scanf("%d %d %d",&Nv,&Ne,&S);

    for(i=0; i<Ne; i++) {
        int v1,v2;
        scanf("%d %d",&v1,&v2);
        G[v1][v2]=1;
        G[v2][v1]=G[v1][v2];
    }
    memset(visit,0,sizeof(visit));
}
void DFS() {
    visit[S]=1;
    Stack[++Top]=S;
    printf("%d",S);
    cnt++;
    int i;
    while(1) {
        int flag=0;
        for(i=1; i<=Nv; i++) {
            if(!visit[i]&&G[S][i]) {
                flag=1;
                visit[i]=1;
                Stack[++Top]=i;
                cnt++;
                printf(" %d",i);
                S=i;
                break;
            }
        }
        if(!flag) {
            Top--;
            if(Top==-1)
                break;
            S=Stack[Top];
            printf(" %d",S);
        }
    }
    if(cnt!=Nv)
    printf(" 0");
    
}

int main(int argc,char **argv) {
    Initial();
    DFS();
    return 0;
}