首页 > 代码库 > 学习笔记：图的DFS和BFS的两种搜索办法
学习笔记：图的DFS和BFS的两种搜索办法
在学习图结构的过程中，DFS和BFS是两种不同的遍历方式，其寻找元素具有不同的优点和缺陷。
BFS被称作广度优先算法， 在遍历整个图的过程中，BFS将采用入队的方式进行，值得一提的是，这和树结构中的层序遍历有很大的相似之处。
在层序遍历中，将父亲节点入队后，在父亲节点出队后，将其儿子节点入队。
同理在图的BFS遍历中，先让BFS的首元素入队，在收元素入队后将他的儿子节点入队，放能够实现BFS搜索，他们的整体思想是一样的。
1 void TraversalGraph_BFS(LGraph Graph,Vertex vertex){ 2 Visit(vertex); 3 VISIT[vertex]=1; 4 enqueue(queue,vertex); 5 while(!isEmpty(queue)){ 6 DelQueue(queue); 7 for(w=Graph->G[vertex].FirstNode;w;w=w->Next){ 8 if(!Visit[w]){ 9 Visit[w];10 Visit[w->vertex]=1;11 enqueue(queue,w);12 }13 }14 }15 }
DFS又被称作深度优先算法，与BFS不同的是，DFS会首先遍历其儿子节点，这样有点类似在树结构中的前序遍历。
在理解方面相比比较容易，DFS采用了递归的思路，在用链表实现DFS时，思路是当遇到一个没有遍历的节点，则进入该节点，然后同理往下递归，直到某个节点无法在继续则返回。
1 void TraversalGraph_DFS(LGraph Graph,Vertex vertex,void(*Visit)(Vertex)){2 PtrToAdjVNode W;3 Visit(vertex);4 Visit[vertex]=1;5 for(w=Graph->G[vertex].FirstNode;w;w=w->Next){6 if(!Visit[w->vertex])7 TraversalGraph_DFS(Graph,w->Vertex)8 }9 }
下面是程序结构体的前置定义
1 #include<stdio.h> 2 #include<stdlib.h> 3 4 typedef struct Enode *PtrToEnode; 5 typedef int Vertex; 6 typedef int WeightType; 7 typedef DataType Data; 8 struct Enode{ 9 Vertex v1,v2;10 WeightType Weight;11 };12 typedef PtrToEnode Edge;13 14 typedef struct AdjVNode *PtrToAdjVNode;15 struct AdjVNode{16 Vertex vertex;17 WeightType Weight;18 PtrToAdjVNode Next;19 };20 21 typedef struct HeadNode *PtrToHead;22 struct HeadNode{23 PtrToAdjVNode FirstNode;24 DataType Data;25 }HeadNode[Max];26 27 typedef struct Graph *PtrToGNode;28 struct Graph{29 int Ne;30 int Nv;31 HeadNode G;32 };33 typedef *PtrToGNode LGraph;34 35 LGraph creatGraph(int MaxNumb){36 LGraph Graph;37 Graph=(LGraph)malloc(sizeof(struct Graph));38 Graph->Ne=0;39 Graph->Nv=MaxNumb;40 for(i=0;i<Graph->Nv;i++){41 Graph->G[i].FirstNode=NULL;42 }43 return(Graph);44 }45 46 void Insert(LGraph Graph,Edge E){47 AdjVNode NewNode;48 NewNode=(PtrToAdjVNode)malloc(sizeof(struct AdjVNode))49 NewNode->Weight=E->W;50 NewNode->vertex=E->v151 Graph->G[E->v2].Next=NewNode->Next;52 Graph->G[E->v2].Next=NewNode;53 }54 55 void Visit(LGraph Graph){56 printf("Now VISIT %d",V);57 }
学习笔记：图的DFS和BFS的两种搜索办法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。