知道域名怎么进入网站,网页设计代码中字体的颜色如何改,广州做网站服务,月子会所网站建设方案深度优先搜素#xff08;DFS#xff09;
深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中#xff0c;当一个超链被选择后#xff0c;被链接的HTML文件将执行深度优先搜索#…深度优先搜素DFS
深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的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;pG-adjlist[v].edgenext;while (p){ if(!visited[p-adjvex]) DFS(G,p-adjvex);pp-next;}
} //从第v个顶点出发DFSvoid DFSTraverse(AdjMatrix *G)
{printf(广度优先搜索顺序);for(int v0;vG-n;v)visited[v]0;for(int v0;vG-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 (i0;iG-n;i) { //fflush(stdin); //如果 stream 指向输入流如 stdin那么 fflush 函数的行为是不确定的。//故而使用 fflush(stdin) 是不正确的。getchar(); printf(请输入第%d个顶点的信息:,i1);G-adjlist[i].vertexgetchar();G-adjlist[i].edgenextNULL; } //前插法 printf(建立边表\n); for (k0;kG-e;k) { printf(输入有连接的顶点序号); scanf(%d%d,i,j); //对于直接相连的进行编入(即对输入“0 1”时在0对应的边表中编入1) i-1;j-1; s(EdgeNode*)malloc(sizeof(EdgeNode)); s-adjvexj;//边表赋值 s-nextG-adjlist[i].edgenext; G-adjlist[i].edgenexts; //对于间接相连的进行编入(即对输入“0 1”时在1对应的边表中编入0)s(EdgeNode*)malloc(sizeof(EdgeNode)); s-adjvexi; s-nextG-adjlist[j].edgenext; G-adjlist[j].edgenexts; }
}
void DispGraph(AdjMatrix *G)
{int i;for (i0;iG-n;i) { printf(%d-,i1); while(1) { if(G-adjlist[i].edgenextNULL){printf(^);break; }printf(%d-,G-adjlist[i].edgenext-adjvex1); G-adjlist[i].edgenextG-adjlist[i].edgenext-next; } printf(\n); }
}
void DFS(AdjMatrix *G, int v)
{EdgeNode *p;printf(-%c,G-adjlist[v].vertex);visited[v]1;pG-adjlist[v].edgenext;while (p){ if(!visited[p-adjvex]) DFS(G,p-adjvex);pp-next;}
} //从第v个顶点出发DFS
void DFSTraverse(AdjMatrix *G)
{printf(广度优先搜索顺序);for(int v0;vG-n;v)visited[v]0;for(int v0;vG-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
