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

这篇文章将为大家详细讲解有关Java如何实现基于图的深度优先搜索和广度优先搜索，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。

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

package com.wly.algorithmbase.datastructure;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("---插入失败，顶点数量已达上限!");}}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();}}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());}}}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;}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;public class ArrayStack {private int[] tArray;private int topIndex = -1;//表示当前栈顶元素的索引位置 private int CAPACITY_STEP = 12;//数组容量扩展步长 public ArrayStack() {tArray = new int[CAPACITY_STEP];}public int pop() {if(isEmpty()) {System.out.println("错误，栈中元素为空，不能pop");return -1;} else {int i = tArray[topIndex];tArray[topIndex--] = -1;//擦除pop元素 return i;}}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;}}public int peek() {if(isEmpty()) {System.out.println("错误，栈中元素为空，不能peek");return -1;} else {return tArray[topIndex];}}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;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;}}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;}}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();}}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;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如何实现基于图的深度优先搜索和广度优先搜索”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。