图的深度优先遍历(DFS)—递归算法

实验环境：win10, DEV C++5.11

实验要求：

　　实现图的深度优先遍历

实验代码：

#include <iostream>

#define maxSize 255

#include "stdlib.h"

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

/*the definition of struct*/

typedef struct ArcNode{

    int adjvex;

    struct ArcNode * nextarc;

    int info;

}ArcNode;

typedef struct{

    char data;

    ArcNode *firstarc;

}VNode;

typedef struct{

    VNode adjlist[maxSize];

    int n,e;

}AGraph;

/*to create the adjoin graph*/

void createGraph(AGraph &G){

    G.adjlist[].data='a';

    G.adjlist[].data='b';

    G.adjlist[].data='c';

    G.adjlist[].data='d';

    G.adjlist[].data='e';

    G.adjlist[].data='f';

    G.n=;

    G.adjlist[].firstarc=(ArcNode *)malloc(sizeof(ArcNode));

    G.adjlist[].firstarc->adjvex=;

    G.adjlist[].firstarc->nextarc=(ArcNode *)malloc(sizeof(ArcNode));

    G.adjlist[].firstarc->nextarc->adjvex=;

    G.adjlist[].firstarc->nextarc->nextarc=NULL;

    G.adjlist[].firstarc=(ArcNode *)malloc(sizeof(ArcNode));

    G.adjlist[].firstarc->adjvex=;

    G.adjlist[].firstarc->nextarc=(ArcNode *)malloc(sizeof(ArcNode));

    G.adjlist[].firstarc->nextarc->adjvex=;

    G.adjlist[].firstarc->nextarc->nextarc=NULL;

    G.adjlist[].firstarc=(ArcNode *)malloc(sizeof(ArcNode));

    G.adjlist[].firstarc->adjvex=;

    G.adjlist[].firstarc->nextarc=(ArcNode *)malloc(sizeof(ArcNode));

    G.adjlist[].firstarc->nextarc->adjvex=;

    G.adjlist[].firstarc->nextarc->nextarc=(ArcNode *)malloc(sizeof(ArcNode));

    G.adjlist[].firstarc->nextarc->nextarc->adjvex=;

    G.adjlist[].firstarc->nextarc->nextarc->nextarc=NULL;

    G.adjlist[].firstarc=(ArcNode *)malloc(sizeof(ArcNode));

    G.adjlist[].firstarc->adjvex=;

    G.adjlist[].firstarc->nextarc=(ArcNode *)malloc(sizeof(ArcNode));

    G.adjlist[].firstarc->nextarc->adjvex=;

    G.adjlist[].firstarc->nextarc->nextarc=(ArcNode *)malloc(sizeof(ArcNode));

    G.adjlist[].firstarc->nextarc->nextarc->adjvex=;

    G.adjlist[].firstarc->nextarc->nextarc->nextarc=NULL;

    G.adjlist[].firstarc=(ArcNode *)malloc(sizeof(ArcNode));

    G.adjlist[].firstarc->adjvex=;

    G.adjlist[].firstarc->nextarc=(ArcNode *)malloc(sizeof(ArcNode));

    G.adjlist[].firstarc->nextarc->adjvex=;

    G.adjlist[].firstarc->nextarc->nextarc=(ArcNode *)malloc(sizeof(ArcNode));

    G.adjlist[].firstarc->nextarc->nextarc->adjvex=;

    G.adjlist[].firstarc->nextarc->nextarc->nextarc=NULL;

    G.adjlist[].firstarc=(ArcNode *)malloc(sizeof(ArcNode));

    G.adjlist[].firstarc->adjvex=;

    G.adjlist[].firstarc->nextarc=NULL;

    G.e=;

}

int isVisit[maxSize]={};

void visit(AGraph &G,int v){

    printf("%c",G.adjlist[v].data);

}

/*deepth first search using recursive*/

void DFS(AGraph &G,int v){

    ArcNode *p;

    isVisit[v]=;

    visit(G,v);

    p=G.adjlist[v].firstarc;

    while(p!=NULL){

        if(isVisit[p->adjvex]==)

            DFS(G,p->adjvex);

        p=p->nextarc;

    }

}

//for finding the adjoin arc of the vertex

//void searchG(AGraph &G,int i){

//    ArcNode * p=G.adjlist[i].firstarc;

//    while(p!=NULL){

//        printf("%c",G.adjlist[p->adjvex].data);

//        p=p->nextarc;

//    }

//}

int main(int argc, char** argv) {

    AGraph G;

    createGraph(G);

    //searchG(G,1);

    printf("the deepth searth using recursive:\n");

    DFS(G,);

    getchar();

    return ;

}

运行结果：