深度优先(DFS)、广度优先(BFS)、一致代价(UCS)搜索算法的实现（附代码）

2024-07-03 19:42| 来源: 网络整理| 查看: 265

Introduction 一、深度优先搜索算法从一个顶点v出发，首先将v标记为已遍历的顶点，然后选择一个邻接于v的尚未遍历的顶点u，如果u不存在，本次搜素终止。如果u存在，那么从u又开始一次DFS。如此循环直到不存在这样的顶点。假设我们建立如下树在这里插入图片描述搜索过程如下：首先编码，令S=1、a=2、b=3、c=4、d=5、e=6、f=7、g=8、h=9、r=10、p=11、q=12 重复点不再搜索，所以12个点最多24步搜索完毕代码主要部分为

建立结构体，包含序号、状态、发现时刻、完成时刻、上下节点字符与数字的互相转换函数DFS函数：根据判断下一个节点是否被发现过来搜索，若搜索过将会被标记，若没有节点将返回上一节点，并寻找新的节点在这里插入图片描述

并对节点路径显示

DFS实现代码 #include #include #include #include #include using namespace std; struct Node{//节点结构体 int Num;//节点序号，与节点一一对应 int State;//三种状态，0表示未被发现，1表示正在处理，2表示处理完成 int Find;//发现节点的时刻 int Solve;//完成对节点处理的时刻 vector next;//存储所有的邻接节点 Node* pre; Node(int x):State(0),Num(x),Find(0),Solve(0),pre(NULL){ } }; void insert(Node* L,Node* n) { L->next.push_back(n); } void display(Node* L)//显示该节点的所有邻接节点 { int n=L->next.size(); for(int i=0;i{5,6,11},{2},{2},{2},{3,4,6},{9,10},{4,8},{8},{11,12},{7},{12},{12}}; cout

【本文地址】

公司简介

联系我们