图的深度优先遍历:释义详见百度百科

  基本思想: 深度优先遍历图的方法是,从图中某顶点v出发:
    (1)访问顶点v;
    (2)依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;
    (3)若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止.

深度优先遍历

1.邻接表

数据结构如下:

#include <stdio.h>
#include <stdlib.h>
#define maxsize 1010   //一般顶点超过1000的建议用邻接表
typedef struct ArcNode {    //边结点
    int adjvex;        //序号
    struct ArcNode *next;
}ArcNode;
typedef struct VNode{    //顶点
    ArcNode *firstarc;
    int no;
}VNode;
typedef struct Graph {      //图
    VNode VNodeList[maxsize];
    int node;    //顶点数
    int edge;    //边数
}Graph;

建立邻接表

void createGraph(Graph *G){
    int start;
    int end;
    ArcNode *e;

    scanf("%d%d",&(G->node),&(G->edge));        //输入边数和结点数

    for(int i = 0; i < G->node; i++){//输入顶点
        scanf("%d",&(G->VNodeList[i].no));
        G->VNodeList[i].firstarc = NULL;
    }

    for(int i = 0; i < G->edge; i++){
        scanf("%d%d",&start,&end);

        //插入该点指向的边表
        e =(ArcNode*)malloc(sizeof(ArcNode));//分配空间
        e->adjvex = end;
        e->next = G->VNodeList[start].firstarc;
        G->VNodeList[start].firstarc = e;//类似于链表的前插

        //无向图才有下方
        e =(ArcNode*)malloc(sizeof(ArcNode));//分配空间
        e->adjvex = start;
        e->next = G->VNodeList[end].firstarc;
        G->VNodeList[end].firstarc = e;//类似于链表的前插
    }
}

递归

//邻接表递归
 int visited[maxsize] = {0};    //直接赋值
 void DFS(Graph *g, int v){
    ArcNode *arc = g->VNodeList[v].firstarc;
    visited[v]=1; 
    printf("访问结点:%d\n",g->VNodeList[v].no);
    while(arc != null){        //找到未访问的点
        if(visited[arc->adjvex] == 0)
            DFS(g,arc->adjvex);
        arc = arc->next;
    }
 }

 void DFSTraverse(Graph *g){
    if(g == NULL) return;   //判空
    //memset(visited, 0, sizeof(visited));
    //或者在此之前将visited赋值完毕
    for(int i=0;i < g->node; i++){
        if(visited[i] == 0)
            DFS(g,i);
    }
 }

非递归

// 邻接表非递归
 int visited[maxsize] = {0};
 void DFSNonRecursion(Graph *g, int v){
    int stack[maxsize];        //工作栈
    int top = -1;    //栈顶指针
    int j;        //获取栈顶    
    ArcNode *p;        //边结点

    //memset(visited,0,sizeof(visited));  //或在此赋值
    printf("访问结点:%d\n", g->VNodeList[v].no);   //访问结点
    visited[v] = 1;    //置已访问
    stack[++top] = v;   //入栈
    while (top != -1) {
        j = stack[top];        //栈顶访问
        p = g->VNodeList[j].firstarc;    //连接的第一个边结点
        while (p != NULL) {
            while (p != NULL && visited[p->adjvex] == 1)  //非空且已经访问
                p = p->next;
            if(p == NULL)    //如果当前已为空,则表示与当前结点邻接的所有结点访问完毕
                break;
            stack[++top] = p->adjvex;  //序号入栈
            visited[p->adjvex] = 1;
            printf("访问结点:%d\n", g->VNodeList[p->adjvex].no);      //访问且置为已访问
            p = g->VNodeList[p->adjvex].firstarc;    //找到与该结点第一个邻接的下一个顶点
        }
        --top;
    }

    return;
}

2.邻接矩阵

数据结构如下:

 #include <stdio.h>
 #define max 100
 typedef struct{
    int vertex;    //顶点数
    int edge;    //边数
    int VertexList[max];    //顶点数组
    int EdgeList[max][max];    //边数组
 }Graph

建立邻接矩阵

 //建立图的邻接矩阵
void CreateGraph(Graph *G){
    scanf("%d%d", &G->vertex,&G->edge);   //输入顶点数、边数

    for (int i=0; i < G->vertex; i++){
        scanf("%d",&(G->VertexList[i]));
    }

    for (int i=0; i < G->vertex; i++){
        for (int j=0; j<G->vertex; j++)
            G->EdgeList[i][j] = -1;        //初始化置为-1不可达
    }

    int start, end, weight;
    for (int k=0; k < G->edge; k++){    //赋值边数组
        scanf("%d%d%d", &start,&end,&weight);
        G->EdgeList[start][end] = weight;
        //如果是无向图,才有下面这一句
        G->EdgeList[end][start] = G->EdgeList[start][end];
    }
}

递归

int visited[max] = {0}
void DFS(Graph* G, int v){
    visited[v] = 1;            //置已访问且输出
    printf("访问结点:%d\n", G->VertexList[v]);
    for (int j=0; j < G->vertex; j++){        //如果有边,且还未访问,访问之
        if (G->EdgeList[v][j] != -1  &&  visited[j] == 0)
            DFS(G, j);
    }
}

void DFSTraverse(Graph* G){
    //memset(visited,0,sizeof(visited));  //或者在这里初始化visited数组
    for (int i=0; i < G->vertex; i++){        //遍历
        if (visited[i] == 0)
            DFS(G, i);
    }
}

非递归

int visited[max] = {0}
void DFS(Graph* G,int v){
   //memset(visited,0,sizeof(visited));  //或者在这里初始化访问数组
   int stack[max];
   int top = -1;
   printf("访问结点:%d\n", G->VertexList[v]);    //输出结点
   visited[v] = 1     //置已访问该结点

   stack[++top] = v;     //入栈    

   while(top != -1){    //栈不空
       int data = s[top];    //取栈顶
       int i;
       for(i = 0; i < G->vertex; i++){
           if(G->EdgeList[data][i] != 0 && visited[i] == 0){    //如果有边且还未访问
                printf("访问结点:%d\n", G->VertexList[i]);
                visited[i] = 1;       //输出且置为已访问
                s[++top] = i;      //入栈
                break;    //跳出
           }
       }
       if(i == G->vertex)    //data相邻的结点都访问结束了,弹出
           --top;
   }
}

参考原文