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

  基本思想: 深度优先遍历图的方法是,从图中某顶点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;
  }
}

参考原文