1.概述
深度优先搜索遍历图的过程是一个递归过程,我们可以用递归算法来实现。在算法中为了避免在访问过某顶点后又沿着某条回路回到该顶点这种重复访问的情况出现,就必须在图的遍历过程中对每一个访问过的顶点进行标识，这样才可以避免一个顶点被重复访问的情况出现。所以我们在遍历算法中对n个顶点的图设置了一个长度为n的访问标志数组visited[n],每个数组元素被初始化为0,一旦某个顶点i被访问则相应的visited[i]就置1来做为访问过的标志。
参考代码
1 #include<stdio.h> 2 #include<stdlib.h> 3 #define MAXSIZE 30 4 5 typedef struct node//邻接表结点 6 { 7 int adjvex;//邻接点域 8 struct node *next;//指向下一个邻接边结点的指针域 9 }EdgeNode;//邻接表结点类型 10 11 typedef struct vnode//顶点表结点 12 { 13 int vertex;//顶点域 14 EdgeNode *firstedge;//指向邻接表的第一个邻接边结点的指针域 15 }VertexNode;//顶点表结点类型 16 17 void CreatAdjlist(VertexNode g[],int e,int n)//建立无向图的邻接表，n为顶点数，e为边数，g[]存储n个顶点表结点 18 { 19 EdgeNode *p; 20 int i,j,k; 21 printf("Input date of vetex(0~n-1): "); 22 for(i=0;i<n;i++)//建立有n个顶点的顶点表 23 { 24 g[i].vertex=i;//读入顶点i信息 25 g[i].firstedge=NULL;//初始化指向顶点i的邻接表表头指针 26 } 27 for(k=1;k<=e;k++)//输入e条边 28 { 29 printf("Input edge of(i,j):"); 30 scanf("%d,%d",&i,&j); 31 p=(EdgeNode *)malloc(sizeof(EdgeNode)); 32 p->adjvex=j;//在顶点Vi的邻接表中添加邻接点为j的结点 33 p->next=g[i].firstedge;//插入是在邻接表表头进行的 34 g[i].firstedge=p; 35 p=(EdgeNode *)malloc(sizeof(EdgeNode)); 36 p->adjvex=i;//在顶点Vj的邻接表中添加邻接点为i的结点 37 p->next=g[j].firstedge;//插入是在邻接表表头进行的 38 g[j].firstedge=p; 39 } 40 } 41 42 int visited[MAXSIZE];//MAXSIZE为大于或等于无向图顶点个数的常量 43 void DFS(VertexNode g[],int i)//从指定的顶点i开始深度优化搜索 44 { 45 EdgeNode *p; 46 printf("%4d",g[i].vertex);//输出顶点i信息，即访问顶点i 47 visited[i]=1; 48 p=g[i].firstedge;//根据顶点i的指针firstedge查找其邻接表的第一个邻接边结点 49 50 while(p!=NULL)//当邻接结点不为空时 51 { 52 if(!visited[p->adjvex])//如果邻接的这个边结点未被访问过 53 DFS(g,p->adjvex);//对这个边结点进行深度优先搜索 54 p=p->next;//查找顶点i的下一个邻接边结点 55 } 56 } 57 58 void DFSTraverse(VertexNode g[],int n)//深度优先搜索遍历以邻接表存储的图，其中g为顶点表，n为顶点个数 59 { 60 int i; 61 for(i=0;i<n;i++) 62 visited[i]=0;//访问标志置0 63 for(i=0;i<n;i++)//对n个顶点的图查找未访问过的顶点并由该顶点开始遍历 64 if(!visited[i])//当visited[i]等于0时即该顶点i未访问过 65 DFS(g,i);//从未访问过的顶点i开始遍历 66 } 67 68 void main() 69 { 70 int e,n; 71 VertexNode g[MAXSIZE];//定义顶点表结点类型数组g 72 printf("Input number of node: ");//输入图中结点个数 73 scanf("%d",&n); 74 printf("Input number of edge: ");//输入图中边的个数 75 scanf("%d",&e); 76 printf("Make adjlist: "); 77 CreatAdjlist(g,e,n);//建立无向图的邻接表 78 printf("DFSTraverse: "); 79 DFSTraverse(g,n);//深度优先遍历以邻接表存储的无向图 80 printf(" "); 81 }
说明：
分析：
由CreatAdjlist（g,e,n)建立无向图邻接表知道,g[i].firstedge->next=g[i].firstedge,g[j].firstedge->next=g[j].firstedge;这个数据类型好像一个链表从"头部插入”且满足"后进先出"的特性；深度遍历首先遍历连接起来的图，如果图连接中断，开始新的结点遍历。根据下图简单分析图的深度遍历过程:
1以"0"顶点遍历,由于"0"顶点连接的边有"3"和"1"顶点,由于顶点"3"是"后入"链表的,所以首先遍历;
2以顶点"3"遍历,找到与"3"顶点相连接的边有"0"和"4"顶点,由于"0"顶点已经遍历过了,所以访问"4"顶点；
3以顶点"4"遍历,找到与顶点"4"相连的边有"2"和"3"顶点 ,由于顶点"2"是"后入"链表的,所以首先遍历;
4以顶点"2"遍历,找到与顶点"2"相连的边有"4"和"3"顶点 ,由于"4"和"3"顶点已经访问过,继而回到原处 ;
5从新的顶点"1"开始遍历,找到与顶点"1"相连的边有"5"和"0"顶点,由于顶点"5"是"后入"链表的，所以首先遍历;
6最后从顶点"5"开始遍历,发现0~5结点都已经遍历过，遍历结束；