广度优先搜索(宽度优先搜索,BFS)和深度优先搜索(DFS)算法的应用非常广泛,本篇文章主要介绍BFS与DFS的原理、实现和应用。 深度优先搜索 图的深度优先搜索(Depth First Search),和树的先序遍历比较类似。 它的思想:假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点,然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到,则另选一个未被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问…

2021年11月2日 0条评论 6点热度 阅读全文

过程其实很简单: 先在先序子序列中找到当前子树的根节点,即先序子序列的第一个节点就是当前子树根节点 在中序子序列中找到当前根节点的位置,并返回下标 根据中序子序列中的当前子树根节点的位置,得到子树的左子树和右子树 根据当前子树的左右子树,分别得到其在先序子序列和中序子序列中的开始索引和结束索引 根据得到的索引,判断左右子树是否为空,如果不为空则返回第一步继续执行,如果为空直接返回。 在二叉链表构建完成后,通过广度优先便利来验证构建的二叉树是否正确。 // p126-6_根据先序中序序列建立二叉链表.cpp : 此文…

2021年7月6日 0条评论 5点热度 阅读全文

A*算法求解N数码问题的设计与实现 Table of Contents 任务要求: 1. 关于A*算法: 2. 算法复杂度: 3. Solution: 4. CODE 任务要求: 以八数码问题为例实现A*算法的求解程序(编程语言不限),要求设计两种以上的不同估价函数; 在求解八数码问题的A*算法程序中,设置相同的初始状态和目标状态,针对不同的估价函数,求得问题的解,并比较它们对搜索算法性能的影响,包括扩展节点数、生成节点数等; 对于八8数码问题,设置与上述2相同的初始状态和目标状态,用宽度优先搜索算法(即令估计代价…

2020年5月8日 0条评论 4点热度 阅读全文

前言 我们在一个数组中想查找某个对象item我们改如何操作呢?很简单一层遍历就可以搞定了,如下: - (NSInteger)searchNormal:(NSArray *)array item:(NSString *)item{ for(int i = 0;i<array.count;i++){ if(array[i] == item){ return i; } } return -1; } 但是我们有没有更优的算法来查找呢? 在数据结构的书中我们可以找到“哨兵查找法”,但是什么又是“哨兵查找法”呢?什么又是…

2019年10月21日 0条评论 17点热度 阅读全文

//牛客编程题:十六进制转十进制(多组输入),例如:输入 0xA,输出 10 /*分两步,1)判断标识符“0x”,如果本身输出不合法,无需做转化,2)按 输入十六进制从后往前(低位到高位)依次判断每个字符代表的数值大小,再 乘以16的位数的几次方(相当于十进制,百位千位对应于10的二次和三次方) 直到“0x”处停止,累加输出对应的十进制数*/ #include <iostream> #include <vector> #include <string> #include <…

2017年7月12日 0条评论 10点热度 阅读全文

// 上机作业.cpp : 定义控制台应用程序的入口点。 // /* *********英语单词小助手*********** 作者:yangliu 版本:v1.0 创建时间:2017/3/11 主要功能: 1.词库维护:可以增加、删除、修改和查询单词(中英文查询) 2.单词预览:将文件中的单词在屏幕上显示中英文词义。 3.单词背诵与检测(中英):随机显示中文词汇,用户需输入正确的英文可得十分。 4.单词背诵与检测(英中):随机显示英文词汇,用户需输入正确的中文可得十分。 5.成绩查询:显示中英、英中单词检测的成绩与…

2017年5月22日 0条评论 8点热度 阅读全文

电话号码对应的字符组合:在电话或者手机上,一个数字如2对应着字母ABC,7对应着PQRS。那么数字串27所对应的字符的可能组合就有3*4=12种(如AP,BR等)。现在输入一个3到11位长的电话号码,请打印出这个电话号码所对应的字符的所有可能组合和组合数。   /* File name:电话号码对应的字符组合.cpp Author:杨柳 Date:2017/5/23 IDE:DEV-c++ */ /* 0:"" 1:"" 2:ABC 3:DEF 4:GHI 5:JKL 6:MNO 7:PQRS 8:TUV…

2017年5月17日 0条评论 10点热度 阅读全文

该算法由荷兰的一个牛人计算机科学家Edsger Wybe Dijkstra在1956年发现。   这套算法主要解决计算从一个点到其它的点的最短距离,而不是Floyd-Warshall算法的任意两点距离。  如图,现要计算出,从1号点到其它各点的最短距离,首先我还是转化成矩阵 由此可见1号点到其它点的初始距离为:   0 1 12 ∞ ∞ ∞    很明显2号点是离1号点最近的点,那么1号点到2号点的最短距离肯定就是直达了。那我就将2号点作为“换乘点”,来计算下距离:…

2016年8月5日 0条评论 9点热度 阅读全文