Java如何实现基于图的深度优先搜索和广度优先搜索

这篇文章将为大家详细讲解有关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;j2.然后是一个用数组模拟的栈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;i3.在一个用链表模拟的队列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
关于“Java如何实现基于图的深度优先搜索和广度优先搜索”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。            
            
                            

                文章标题：Java如何实现基于图的深度优先搜索和广度优先搜索                

                文章转载：http://scyanting.com/article/ihisoc.html

Java如何实现基于图的深度优先搜索和广度优先搜索

其他资讯