1. 原理描述:
设图G的初始状态是所有顶点均为访问过。以G中任选一顶点V为起点,则描述为:首先访问出发点V,
接着依次访问V的所有邻接点W1,W2,...,Wi,然后再依次访问与W1,W2,...,Wi邻接的所有未曾访问过的
顶点。依次类推,直到图中所有和起点V有路径相同的顶点都已访问为止。此时从V开始搜索过程结束。
2. 算法设计基本步骤:
(1) 确定图的存储方式。
(2) 设计搜索过程中的操作,其中包括为输出问题解而进行的存储操作。
(3) 输出问题的解空间。
3. 一种实现:求从一个城市到另一个城市间经过的城市最少的路线。
package com.maozj.datastruct.graphic;
/**
* 图的广度优先搜索
*
* @author 毛正吉
*
*/
public class BreadthSearch {
public static void main(String[] args) {
BreadthSearch s = new BreadthSearch();
s.set(8);
s.search();
}
private int[][] jz;
private SQ[] sq;
private int qh;
private int qe;
private int[] visited;
public BreadthSearch() {
/** 存储图的邻接矩阵 */
jz = new int[][] { { 0, 1, 1, 1, 0, 1, 0, 0 },
{ 1, 0, 0, 0, 0, 1, 0, 0 }, { 1, 0, 0, 1, 1, 0, 0, 0 },
{ 1, 0, 1, 0, 0, 0, 1, 0 }, { 0, 0, 1, 0, 0, 0, 1, 1 },
{ 1, 1, 0, 0, 0, 0, 0, 1 }, { 0, 0, 0, 1, 1, 0, 0, 1 },
{ 0, 0, 0, 0, 1, 1, 1, 0 } };
/** 队列集合 */
sq = new SQ[100];
visited = new int[100];
}
public void search() {
/** 队首 */
qh = 0;
/** 队尾 */
qe = 1;
sq[1] = new SQ();
sq[1].city = 1;
sq[1].pre = 0;
visited[1] = 0;
/** 当队列不为空 */
while (qh != qe) {
/** 节点出队 */
qh = qh + 1;
/** 扩展节点 */
for (int i = 0; i < 8; i++) {
if (jz[sq[qh].city][i] == 1 && visited[i] == 0) {
/** 节点入队 */
qe++;
sq[qe] = new SQ();
sq[qe].city = i;
sq[qe].pre = qh;
visited[i] = 1;
if (sq[qe].city == 7) {
out();
return;
}
}
}
}
System.out.println("No avaliable way");
}
/** 输出路径 */
public void out() {
System.out.print(sq[qe].city);
while (sq[qe].pre != 0) {
qe = sq[qe].pre;
System.out.print("---" + sq[qe].city);
}
}
public void set(int n) {
for (int i = 0; i < n; i++) {
visited[i] = 0;
}
}
}
class SQ {
int city;
int pre;
}
分享到:
相关推荐
邻接表表示的图的深度优先搜索和广度优先搜索程序
广度优先搜索和宽度优先搜索的动画演示,均为gif图,大家可以自行看看,理解思路或者放Ppt里很好用,怎么分数是5分,编辑不了了? 请管理员修改为1分,谢谢
BFS DFS 深度优先搜索 广度优先搜索 图 输出所有路径 输出最短路径 随便输出一条可能的路径
数据结构图的邻接矩阵,邻接表存储表示,图的深度优先搜索遍历,广度优先搜索遍历 数据结构图的邻接矩阵,邻接表存储表示,图的深度优先搜索遍历,广度优先搜索遍历.rar
选择某种图的存储结构,在此基础上实现图的深度优先搜索和广度优先搜索;实验环境:Visual C++ 6.0,Windows 2000。
二叉树的深度优先搜索与广度优先搜索的非递归方法实现
①使用深度优先搜索来解决八数码问题 ②使用广度优先搜索来解决八数码问题 ③使用过程式表示和实现八数码问题 以及相关代码详细注释 过程式知识表示是将有关某一问题领域的知识, 连同如何使用这些知识的方法,均...
以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。 注: 1.代码共182行。 2.代码经过多次编译运行,无错误。
采用邻接表存储图,,输出深度优先搜索序列和广度优先序列。
图深度优先搜索C++,详细,无错误,精练,准确
数据结构——有向图广度优先搜索
图的遍历,深度优先搜索,广度优先搜索,生成最小生成树C++
图的应用——深度优先/广度优先搜索遍历 要求:以邻接矩阵或邻接表为存储结构(学号为单号的同学以邻接矩阵为存储结构,双号的同学以邻接表为存储结构)建立无向连通图,从键盘上输入指定的顶点为起始点,实现图...
数据结构类模板无向图邻接矩阵和深度及广度优先搜索遍历
数据结构课程中的深度优先搜索算法、广度优先搜索算法的C语言程序,在Turbo C 2.0上调试通过。
数据结构课程中的深度优先搜索算法、广度优先搜索算法的C语言程序,在Turbo C 2.0上调试通过。
无向图的宽度优先搜索算法和深度优先搜索算法,c++实现
根据有向图广度优先搜索遍历算法.ppt
数据结构试验中最难的一部分,此代码是我按照书中代码编写的,其中没有bug,方便同学借鉴!