基于图的深度优先搜索和广度优先搜索java实现

 为了解15puzzle问题，了解了一下深度优先搜索和广度优先搜索。先来讨论一下深度优先搜索(DFS)，深度优先的目的就是优先搜索距离起始顶点最远的那些路径，而广度优先搜索则是先搜索距离起始顶点最近的那些路径。我想着深度优先搜索和回溯有什么区别呢？百度一下，说回溯是深搜的一种，区别在于回溯不保留搜索树。那么广度优先搜索(BFS)呢?它有哪些应用呢？答：最短路径，分酒问题，八数码问题等。言归正传，这里笔者用java简单实现了一下广搜和深搜。其中深搜是用图+栈实现的，广搜使用图+队列实现的，代码如下：

       1.新建一个表示“无向图”类NoDirectionGraph

package com.wly.algorithmbase.datastructure;

/**
 * 无向图
 * @author wly
 *
 */
public class NoDirectionGraph {

	private int mMaxSize; //图中包含的最大顶点数
	private GraphVertex[] vertexList; //顶点数组
	private int[][] indicatorMat; //指示顶点之间的连通关系的邻接矩阵
	private int nVertex; //当前实际保存的顶点数目

	public NoDirectionGraph(int maxSize) {
		mMaxSize = maxSize;
		vertexList = new GraphVertex[mMaxSize];
		indicatorMat = new int[mMaxSize][mMaxSize];
		nVertex = 0;
		//初始化邻接矩阵元素为0
		for(int j=0;j<mMaxSize;j++) {
			for(int k=0;k<mMaxSize;k++) {
				indicatorMat[j][k] = 0;
			}
		}
	}

	public void addVertex(GraphVertex v) {
		if(nVertex < mMaxSize) {
			vertexList[nVertex++] = v;

		} else {
			System.out.println("---插入失败，顶点数量已达上限!");
		}
	}

	/**
	 * 修改邻接矩阵，添加新的边
	 * @param start
	 * @param end
	 */
	public void addEdge(int start,int end) {
		indicatorMat[start][end] = 1;
		indicatorMat[end][start] = 1;
	}

	/**
	 * 打印邻接矩阵
	 */
	public void printIndicatorMat() {

		for(int[] line:indicatorMat) {
			for(int i:line) {
				System.out.print(i + " ");
			}
			System.out.println();
		}
	}

	/**
	 * 深度优先遍历
	 * @param vertexIndex 表示要遍历的起点,即图的邻接矩阵中的行数
	 */
	public void DFS(int vertexIndex) {
		ArrayStack stack = new ArrayStack();
		//1.添加检索元素到栈中
		vertexList[vertexIndex].setVisited(true);
		stack.push(vertexIndex);
		int nextVertexIndex = getNextVertexIndex(vertexIndex);
		while(!stack.isEmpty()) { //不断地压栈、出栈，直到栈为空(检索元素也没弹出了栈)为止
			if(nextVertexIndex != -1) {
				vertexList[nextVertexIndex].setVisited(true);
				stack.push(nextVertexIndex);
				stack.printElems();
			} else {
				stack.pop();
			}
			//检索当前栈顶元素是否包含其他未遍历过的节点
			if(!stack.isEmpty()) {
				nextVertexIndex = getNextVertexIndex(stack.peek());
			}
		}
	}

	/**
	 * 得到当前顶点的下一个顶点所在行
	 * @param column
	 * @return
	 */
	public int getNextVertexIndex(int column) {
		for(int i=0;i<indicatorMat[column].length;i++) {
			if(indicatorMat[column][i] == 1 && !vertexList[i].isVisited()) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * 广度优先遍历
	 * @param vertexIndex 表示要遍历的起点,即图的邻接矩阵中的行数
	 */
	public void BFS(int vertexIndex) {
		ChainQueue queue = new ChainQueue();
		vertexList[vertexIndex].setVisited(true);
		queue.insert(new QueueNode(vertexIndex));
		int nextVertexIndex = getNextVertexIndex(vertexIndex);
		while(!queue.isEmpty()) {
			if(nextVertexIndex != -1) {
				vertexList[nextVertexIndex].setVisited(true);
				queue.insert(new QueueNode(nextVertexIndex));
			} else {
				queue.remove();
			}
			if(!queue.isEmpty()) {
				nextVertexIndex = getNextVertexIndex(queue.peek().data);
				queue.printElems();
			}
		}
	}
}

       2.然后是一个用数组模拟的栈ArrayStack

package com.wly.algorithmbase.datastructure;

/**
 * 使用数组实现栈结构
 * @author wly
 *
 */
public class ArrayStack {

	private int[] tArray;
	private int topIndex = -1; //表示当前栈顶元素的索引位置
	private int CAPACITY_STEP = 12; //数组容量扩展步长

	public ArrayStack() {
		/***创建泛型数组的一种方法***/
		tArray = new int[CAPACITY_STEP];
	}

	/**
	 * 弹出栈顶元素方法
	 * @return
	 */
	public int pop() {
		if(isEmpty()) {
			System.out.println("错误，栈中元素为空，不能pop");
			return -1;
		} else {
			int i = tArray[topIndex];
			tArray[topIndex--] = -1; //擦除pop元素
			return i;
		}
	}

	/**
	 * 向栈中插入一个元素
	 * @param t
	 */
	public void push(int t) {
		//检查栈是否已满
		if(topIndex == (tArray.length-1)) {
			//扩展容量
			int[] tempArray = new int[tArray.length + CAPACITY_STEP];
			for(int i=0;i<tArray.length;i++) {
				tempArray[i] = tArray[i];
			}
			tArray = tempArray;
			tempArray = null;
		} else {
			topIndex ++;
			tArray[topIndex] = t;
		}
	}

	/**
	 * 得到栈顶元素，但不弹出
	 * @return
	 */
	public int peek() {
		if(isEmpty()) {
			System.out.println("错误，栈中元素为空，不能peek");
			return -1;
		} else {
			return tArray[topIndex];
		}
	}

	/**
	 * 判断当前栈是否为空
	 * @return
	 */
	public boolean isEmpty() {
		return (topIndex < 0);
	}

	/**
	 * 打印栈中元素
	 */
	public void printElems() {
		for(int i=0;i<=topIndex;i++) {
			System.out.print(tArray[i] + " ");
		}
		System.out.println();
	}
}

       3.在一个用链表模拟的队列ChainQueue

package com.wly.algorithmbase.datastructure;

/**
 * 使用链表实现队列
 *
 * @author wly
 *
 */
public class ChainQueue {
	private QueueNode head; // 指向队列头节点
	private QueueNode tail; // 指向队列尾节点
	private int size = 0; // 队列尺寸

	public ChainQueue() {

	}

	/**
	 * 插入新节点到队列尾
	 */
	public void insert(QueueNode node) {

		// 当然也可以这么写,添加tail.prev = node
		if (head == null) {
			head = node;
			tail = head;
		} else {
			node.next = tail;
			tail.prev = node; // 双向连接，确保head.prev不为空
			tail = node;
		}
		size++;
	}

	/**
	 * 移除队列首节点
	 */
	public QueueNode remove() {
		if (!isEmpty()) {
			QueueNode temp = head;
			head = head.prev;
			size--;
			return temp;
		} else {
			System.out.println("异常操作，当前队列为空!");
			return null;
		}
	}

	/**
	 * 队列是否为空
	 *
	 * @return
	 */
	public boolean isEmpty() {
		if (size > 0) {
			return false;
		} else {
			return true;
		}
	}

	/**
	 * 返回队列首节点，但不移除
	 */
	public QueueNode peek() {
		if (!isEmpty()) {
			return head;
		} else {
			System.out.println();
			System.out.println("异常操作，当前队列为空!");
			return null;
		}
	}

	/**
	 * 返回队列大小
	 *
	 * @return
	 */
	public int size() {
		return size;
	}

	/**
	 * 打印队列中的元素
	 */
	public void printElems() {
		QueueNode tempNode = head;
		while(tempNode != null) {
			System.out.print(tempNode.data + " ");
			tempNode = tempNode.prev;
		}
		System.out.println();
	}
}

/**
 * 节点类
 *
 * @author wly
 *
 */
class QueueNode {
	QueueNode prev;
	QueueNode next;

	int data;

	public QueueNode(int data) {
		this.data = data;
	}

	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}

	@Override
	public String toString() {
		// TODO Auto-generated method stub
		super.toString();
		return data + "";
	}
}

       4.测试一下Test_BFS_DFS

package com.wly.algorithmbase.search;

import com.wly.algorithmbase.datastructure.GraphVertex;
import com.wly.algorithmbase.datastructure.NoDirectionGraph;

/**
 * 基于图的深度优先搜索
 * @author wly
 *
 */
public class Test_BFS_DFS {

	public static void main(String[] args) {

		//初始化测试数据
		NoDirectionGraph graph = new NoDirectionGraph(7);
		graph.addVertex(new GraphVertex("A"));
		graph.addVertex(new GraphVertex("B"));
		graph.addVertex(new GraphVertex("C"));
		graph.addVertex(new GraphVertex("D"));
		graph.addVertex(new GraphVertex("E"));
		graph.addVertex(new GraphVertex("F"));
		graph.addVertex(new GraphVertex("G"));
		graph.addEdge(0, 1);
		graph.addEdge(0, 2);
		graph.addEdge(1, 3);
		graph.addEdge(1, 4);
		graph.addEdge(3, 6);
		graph.addEdge(2, 5);

		System.out.println("--图的邻接矩阵--");
		graph.printIndicatorMat();

		//测试深搜
		System.out.println("--深度优先搜索--");
		graph.DFS(0);

		 graph = new NoDirectionGraph(7);
			graph.addVertex(new GraphVertex("A"));
			graph.addVertex(new GraphVertex("B"));
			graph.addVertex(new GraphVertex("C"));
			graph.addVertex(new GraphVertex("D"));
			graph.addVertex(new GraphVertex("E"));
			graph.addVertex(new GraphVertex("F"));
			graph.addVertex(new GraphVertex("G"));
			graph.addEdge(0, 1);
			graph.addEdge(0, 2);
			graph.addEdge(1, 3);
			graph.addEdge(1, 4);
			graph.addEdge(3, 6);
			graph.addEdge(2, 5);
		System.out.println("--广度优先搜索--");
		graph.BFS(0);

	}
}

       这里测试的图结构如下:

       运行结果如下:

--图的邻接矩阵--
0 1 1 0 0 0 0
1 0 0 1 1 0 0
1 0 0 0 0 1 0
0 1 0 0 0 0 1
0 1 0 0 0 0 0
0 0 1 0 0 0 0
0 0 0 1 0 0 0
--深度优先搜索--
0 1
0 1 3
0 1 3 6
0 1 4
0 2
0 2 5
--广度优先搜索--
0 1
0 1 2
1 2
1 2 3
1 2 3 4
2 3 4
2 3 4 5
3 4 5
3 4 5 6
4 5 6
5 6
6

       这里需要说明一下上面深搜和广搜的运行结果，其中0,1,2,3…分别对应着A,B,C,D...有点绕哈，，见谅~~

       O啦~~~

       转载请保留出处:http://blog.csdn.net/u011638883/article/details/17169071

       谢谢!!

时间： 2024-08-31 06:17:45

基于图的深度优先搜索和广度优先搜索java实现的相关文章

图的遍历之深度优先搜索和广度优先搜索

深度优先搜索的图文介绍 1. 深度优先搜索介绍 图的深度优先搜索(Depth First Search),和树的先序遍历比较类似. 它的思想:假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点,然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和v有路径相通的顶点都被访问到.  若此时尚有其他顶点未被访问到,则另选一个未被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止. 显然,深度优先搜索是一个递归的过程. 2. 深度优先搜索图解 2.

python 广度优先搜索 遍历图中的点

问题描述 python 广度优先搜索 遍历图中的点 mapmodel=[ [0,1,1,-1,1], [1,0,-1,1,-1], [1,-1,0,-1,1], [-1,1,-1,0,-1], [1,-1,1,-1,0] ] flag=[1,0,0,0,0] def dfs(current,sumpoint): if sumpoint==5: print sumpoint,flag for i in range(5): if mapmodel[current][i]==1 and flag[i]

【算法导论】图的广度优先搜索遍历（BFS）

       图的存储方法:邻接矩阵.邻接表        例如:有一个图如下所示(该图也作为程序的实例): 则上图用邻接矩阵可以表示为: 用邻接表可以表示如下: 邻接矩阵可以很容易的用二维数组表示,下面主要看看怎样构成邻接表:         邻接表存储方法是一种顺序存储与链式存储相结合的存储方法.在这种方法中,只考虑非零元素,所以在图中的顶点很多而边很少时,可以节省存储空间.         邻接表存储结构由两部分组成:对于每个顶点vi, 使用一个具有两个域的结构体数组来存储,这个数组称为顶

图的广度优先搜索（BFS）

把以前写过的图的广度优先搜索分享给大家(C语言版) #include<stdio.h> #include<stdlib.h> #define MAX_VERTEX_NUM 20 #define MAXQSIZE 100 #define OK 1 typedef char VertexType; typedef int QElemType; typedef struct ArcNode//边结点 { int adjvex; struct ArcNode *nextarc; }ArcN

c++-图的广度优先搜索问题，我的代码超出时间限制求修改或给出新的答案，谢谢！

问题描述 图的广度优先搜索问题,我的代码超出时间限制求修改或给出新的答案,谢谢! Description 读入图的邻接矩阵以及一个顶点的编号(图中顶点的编号为从1开始的连续正整数.顶点在邻接矩阵的行和列上按编号递增的顺序排列.邻接矩阵中元素值为1,表示对应顶点间有一条边,元素值为0,表示对应顶点间没有边),输出从该顶点开始进行广度优先搜索(Breadth-First Search, BFS)的顶点访问序列.假设顶点数目<=100,并且,对于同一顶点的多个邻接顶点,按照顶点编号从小到大的顺序进行搜

【算法导论】图的深度优先搜索遍历（DFS）

        关于图的存储在上一篇文章中已经讲述,在这里不在赘述.下面我们介绍图的深度优先搜索遍历(DFS).         深度优先搜索遍历实在访问了顶点vi后,访问vi的一个邻接点vj:访问vj之后,又访问vj的一个邻接点,依次类推,尽可能向纵深方向搜索,所以称为深度优先搜索遍历.显然这种搜索方法具有递归的性质.图的BFS和树的搜索遍历很类似,只是其存储方式不同.         其基本思想为:从图中某一顶点vi出发,访问此顶点,并进行标记,然后依次搜索vi的每个邻接点vj:若vj未被访

数据结构实验图论一：基于邻接矩阵的广度优先搜索遍历

数据结构实验图论一:基于邻接矩阵的广度优先搜索遍历 Time Limit: 1000MS Memory Limit: 65536KB Problem Description 给定一个无向连通图,顶点编号从0到n-1,用广度优先搜索(BFS)遍历,输出从某个顶点出发的遍历序列.(同一个结点的同层邻接点,节点编号小的优先遍历) Input 输入第一行为整数n(0< n <100),表示数据的组数. 对于每组数据,第一行是三个整数k,m,t(0<k<100,0<m<(k-1)

【算法小总结】广度优先搜索剖析

广度优先搜索 以前一直用搜索用的都是深搜,因为听说有很多题能用广搜就能用深搜什么的.今天老老实实的去看广搜了,结果发现我之前想的太天真的,DFS和BFS不仅在性质上不同,而且对于某些题和某些情况,用BFS比DFS要快(不是绝对).   今天好好说道说道这个BFS(广度优先搜索)   很多问题(如过迷宫问题),每走下一步,都要考虑很多种情况,这个时候,就要每一步每一步的去试探,去找到合适的方案,也是就是传说中的"搜索".   当然,想试探出结果,可以去将一种方案走到底,遇到不能走或者其他

算法起步之广度优先搜索

原文:算法起步之广度优先搜索           广度优先搜索算法是图的基本算法之一,图是用来保存过对多的关系的数据结构,相对于树一对多的关系更为复杂,所以难度也会比树结构难一点,图的存储一般有连接表表示跟链接矩阵表示,相比来说链接矩阵的方式更为常用,也就是用数组来存储.而广度优先搜索算法其实就是图的遍历过程,数组的遍历大家都会,数组的遍历我们是按照下标的顺序来遍历的,而图的遍历也有自己的方式,图是多对多的关系,我们可以按照各个节点直接的关联关系来遍历他们,这样便衍生出来深度优先跟广度优先,广度