[데이터 구조] 그림 의 DFS 는 스 택 으로 재 귀 하 는 C 언어 를 간단하게 제거 합 니 다.

#include 
#include 

#define MAXSIZE 100
#define ElemType char
#define BOOL int
#define TRUE 1
#define FALSE 0

typedef struct{
    int data[MAXSIZE];
    int top;    //    
}Stack;

static void InitStack(Stack *s);   //    
static void Push(Stack *s, ElemType e);    //    
static void Pop(Stack *s, ElemType *e); //    
static BOOL IsEmpty(Stack s);  //    

static void InitStack(Stack *s){
    s->top = -1;
}

static void Push(Stack *s, ElemType e){
    ++s->top;
    s->data[s->top] = e;
}

static void Pop(Stack *s, ElemType *e){
    *e = s->data[s->top];
    --s->top;
}

static BOOL IsEmpty(Stack s){
    if (s.top <= -1){
        return TRUE;
    }else{
        return FALSE;
    }
}

#include 
#include 
#define INFINTE 65535
#define MAXSIZE 100
#include "stack.c"

typedef char VertexType;                //          
typedef int EdgeType;                   //             

typedef struct graph{
    VertexType vexs[MAXSIZE];            //   
    EdgeType   arc[MAXSIZE][MAXSIZE];       //    
    int numNodes, numEdges;
}Graph;

int visited[200];

void CreateGraph(Graph* graph); //   
VertexType* FirstAdjVex(Graph graph, VertexType data);  //       
VertexType* NextAdjVex(Graph graph, VertexType data, VertexType adj);   //       
void DFSTraversal(Graph graph); //      
void DFSByStack(Graph graph, VertexType vex);

int main(){
    int i, j;
    Graph graph;
    CreateGraph(&graph);
    //      
    for (i = 0; i < graph.numNodes; ++i){
        for (j = 0; j < graph.numNodes; ++j){
            printf("%d ", graph.arc[i][j]);
        }
        printf("
");
    }

    VertexType* adj = FirstAdjVex(graph, 'A');
    VertexType x = *adj;
    printf("%c ", x);
    adj = NextAdjVex(graph, 'A', x);
    x = *adj;
    printf("%c ", x);
    x = *adj;
    adj = FirstAdjVex(graph, 'D');
    printf("%c
", *adj);
    for (i = 0; i < 200; ++i){
        visited[i] = 0;
    }
    DFSTraversal(graph);
    return 0;
}

void CreateGraph(Graph* graph){
    int i, j;
    //          0(0    ，1    )
    for (i = 0; i < graph->numNodes; ++i){
        for (j = 0; j < graph->numNodes; ++j){
            graph->arc[i][j] = 0;
        }
    }
    //printf("      ,   ：");
    //scanf("%d %d", &graph->numNodes, &graph->numEdges);
    //getchar();
    graph->numNodes = 6;
    graph->numEdges = 6;
    /*
    for (i = 0; i < graph->numNodes; ++i){
        printf("     ：");
        scanf("%c", &graph->vexs[i]);
        getchar();  //     
    }
    */
    graph->vexs[0] = 'A';
    graph->vexs[1] = 'B';
    graph->vexs[2] = 'C';
    graph->vexs[3] = 'D';
    graph->vexs[4] = 'E';
    graph->vexs[5] = 'F';
    VertexType start, end;
    /*
    for (i = 0; i < graph->numEdges; ++i){
        printf("     ，   ：");
        scanf("%c %c", &start, &end);
        getchar();  //     
        int startIndex, endIndex;
        for (j = 0; j < graph->numNodes; ++j){  //     ,  
            if (start == graph->vexs[j]){
                startIndex = j;
            }
            if (end == graph->vexs[j]){
                endIndex = j;
            }
        }
        graph->arc[startIndex][endIndex] = 1;
        //      ，      
        graph->arc[endIndex][startIndex] = 1;
    }
    */
    graph->arc[0][2] = 1;
    graph->arc[0][3] = 1;
    graph->arc[3][1] = 1;
    graph->arc[2][4] = 1;
    graph->arc[3][5] = 1;
    graph->arc[4][5] = 1;
    //      ，       
    /*
    graph->arc[2][0] = 1;
    graph->arc[3][0] = 1;
    graph->arc[1][3] = 1;
    graph->arc[4][2] = 1;
    graph->arc[5][3] = 1;
    graph->arc[5][4] = 1;
    */

}


VertexType* FirstAdjVex(Graph graph, VertexType vex){
    //   data    
    int i, j;
    for (i = 0; i < graph.numNodes; ++i){
        if (graph.vexs[i] == vex){
            for (j = 0; j < graph.numNodes; ++j){
                if (graph.arc[i][j] == 1){  //        
                    return &(graph.vexs[j]);
                }
            }
        }
    }
    return NULL;    //       
}


VertexType* NextAdjVex(Graph graph, VertexType vex, VertexType adj){
    int vexIndex, adjIndex, i;
    for (i = 0; i < graph.numNodes; ++i){
        if (graph.vexs[i] == vex){
            vexIndex = i;
        }
        if (graph.vexs[i] == adj){
            adjIndex = i;
        }
    }
    for (i = adjIndex + 1; i < graph.numNodes; ++i){  //           
        if (graph.arc[vexIndex][i] == 1){
            return &(graph.vexs[i]);
        }
    }
    return NULL;    //       
}

/*        */
void DFSTraversal(Graph graph){
    int i;
    for (i = 0; i < graph.numNodes; ++i){
        if (visited[graph.vexs[i]] != 1) {
            DFSByStack(graph, graph.vexs[i]);
        }
    }
}

void DFSByStack(Graph graph, VertexType vex){
    VertexType x;
    VertexType *p;
    Stack stack;
    InitStack(&stack);
    Push(&stack, vex);
    visited[vex] = 1;
    printf("%c ", vex);
    while (!IsEmpty(stack)){
        ElemType e;
        Pop(&stack, &e);    //  
        for (p = FirstAdjVex(graph, e); p != NULL; p=NextAdjVex(graph, e, x)){
            x = *p;
            if (visited[x] != 1){    //    
                Push(&stack, e);
                Push(&stack, x);//           
                printf("%c ", x);
                visited[x] = 1;
                break;
            }
        }
    }

}