连通图遍历策略之深度优先搜索(c语言)

深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

深度优先搜索类似于树的前序遍历 我们依据邻接表进行遍历，还需要运用递归的思想，这类似于堆栈的遍历方式。

同样以如下连通图为例：构建其对应的邻接表：对应邻接表采用深度优先搜素的遍历顺序如下：注：蓝线划去的代表该顶点的visit[i]=1，无需多次遍历。

深度优先搜索步骤：

从某一顶点出发进行访问，该点首先被读入，visit[i]置为1
依次访问该点的一个邻接点
若该邻接点还有临界，那么访问该邻接点的一个邻接点；若没有，则返回上一步进行搜索

** 深度优先搜索函数代码：**

void DFS(AdjMatrix *G, int v)
{
   EdgeNode *p;
   printf("->%c",G->adjlist[v].vertex);
   visited[v]=1;
    p=G->adjlist[v].edgenext;
    while (p)
    {  
		if(!visited[p->adjvex]) DFS(G,p->adjvex);
			p=p->next;
    }
}   //从第v个顶点出发DFS

void DFSTraverse(AdjMatrix *G)
{
	printf("广度优先搜索顺序");
    for(int v=0;v<G->n;++v)
		visited[v]=0;
     for(int v=0;v<G->n;++v)
        if(!visited[v]) DFS(G,v);//递归调用
            printf("\n\n"); 
}

具体代码如下：

#include <stdio.h>  
#include <stdlib.h>  
#define  MaxVertices 100
#define MAX_VERTEX_NUM 10
typedef struct node{   //边表 
   int adjvex;
   node* next;  
}EdgeNode;  
  
typedef struct{     //顶点表  
   int vertex;  
   EdgeNode* edgenext;  
}VertexNode;  
  
typedef VertexNode AdjList[MaxVertices];  
  
typedef struct{   
    AdjList adjlist;  
    int n,e;  
}AdjMatrix;  
int visited[MAX_VERTEX_NUM];
void CreateGraph(AdjMatrix* G)  
{  
    int i,j,k,w,v;  
    EdgeNode *s;  
    printf("输入顶点数和边数（中间以空格分开）：");  
    scanf("%d%d",&G->n,&G->e);  
  
    printf("建立顶点表\n"); 
    for (i=0;i<G->n;i++)  
    {  
		//fflush(stdin);  
		//如果 stream 指向输入流（如 stdin），那么 fflush 函数的行为是不确定的。
		//故而使用 fflush(stdin) 是不正确的。
		getchar(); 
		printf("请输入第%d个顶点的信息:",i+1);
		G->adjlist[i].vertex=getchar();
		G->adjlist[i].edgenext=NULL;  
    }  
	//前插法 
    printf("建立边表\n");  
    for (k=0;k<G->e;k++)  
    {  
       printf("输入有连接的顶点序号：");  
       scanf("%d%d",&i,&j);  
       //对于直接相连的进行编入(即对输入“0 1”时，在0对应的边表中编入1) 
       i-=1;j-=1; 
       s=(EdgeNode*)malloc(sizeof(EdgeNode));  
       s->adjvex=j;//边表赋值 
       s->next=G->adjlist[i].edgenext;  
       G->adjlist[i].edgenext=s;  
       //对于间接相连的进行编入(即对输入“0 1”时，在1对应的边表中编入0)
       s=(EdgeNode*)malloc(sizeof(EdgeNode));  
       s->adjvex=i;  
       s->next=G->adjlist[j].edgenext;  
       G->adjlist[j].edgenext=s;  
    }  
}   
void DispGraph(AdjMatrix *G)
{
	int i;
	for (i=0;i<G->n;i++)  
    {  
        printf("%d->",i+1);  
        while(1)  
        {             
			if(G->adjlist[i].edgenext==NULL)
            {
            	printf("^");
				break;	
			}
            printf("%d->",G->adjlist[i].edgenext->adjvex+1);  
            G->adjlist[i].edgenext=G->adjlist[i].edgenext->next;  
 
        }  
        printf("\n");  
    }  
} 
void DFS(AdjMatrix *G, int v)
{
   EdgeNode *p;
   printf("->%c",G->adjlist[v].vertex);
   visited[v]=1;
    p=G->adjlist[v].edgenext;
    while (p)
    {  
		if(!visited[p->adjvex]) DFS(G,p->adjvex);
			p=p->next;
    }
}   //从第v个顶点出发DFS
void DFSTraverse(AdjMatrix *G)
{
	printf("广度优先搜索顺序");
    for(int v=0;v<G->n;++v)
		visited[v]=0;
     for(int v=0;v<G->n;++v)
        if(!visited[v]) DFS(G,v);//递归调用
            printf("\n\n"); 
}//DFSTraverse
int main()  
{  
    freopen("1.txt","r",stdin);
    AdjMatrix* G= (AdjMatrix*)malloc(sizeof(AdjMatrix));  
    CreateGraph(G); 
	DFSTraverse(G); 
    DispGraph(G); 
}

测试数据如下： 注：由于测试输入数据较多，程序可以采用文件输入

5 7 1 2 3 4 5 1 2 1 3 1 4 2 3 2 4 3 5 4 5

n.xuanrui

退无可退，一往无前

连通图遍历策略之深度优先搜索(C语言)