Java实现图数据结构，深度优先搜索竟能这么玩！快来看
通过Java实现图的数据结构, 前面自定义了顶点, 还自定义了栈与队列来实现搜索算法, 相对麻烦。要知道, 除邻接矩阵外, 可通过一个数组表示顶点集合。另外, 深度优先搜索得以递归调用实现, 而广度优先搜索必须经队列实现, 可直接用java.util工具包下面的队列替代, 如此图的实现便相对简单许多。
点的集合, 是图基本组成中不能少的一部分, 邻接矩阵, 也是图基本组成中不能少的一部分, 除此之外, 我们需定义边的数量, 以及用于广度优先搜索的队列。如下列图形所展示的那样, 这些是图的构成以及搜索所需的必不可少的属性, 于构造函数之中, 我们对这些属性进行初始化。
接着添加两个方法，分别是在图中添加顶点和边的信息。
有现成图的结构了, 在此处能够构建一个简易图, 是毫无方向的图。如下面所展示的图形那样, 顶点有七个, 边有六条。
深度优先搜索的想法是, 先从一个顶点着手进行遍历开端, 接着逐个遍历该顶点能够抵达的尽可能远的边直至尽头, 每一回皆是深入到不存在边可通达的顶点才停下。实际上能够借助递归方式来操作, 就以上面图像为例, 要是从A顶点开启遍历程序, 那么就逐个遍历BC DE FG, 当遍历B这个顶点之际且尚未完成, 会随着接着深入遍历到C顶点，当遍历D这个顶点之时且进行中, 会随着接着遍历E顶点, 同样的道理, 当遍历F这个顶点之际且未完结, 又会深入遍历到G顶点完成遍历过程。
广度优先搜索直观之处在于, 先对近处节点遍历, 接着对远处节点遍历, 一开始会遍历BCD, 后续一轮会遍历CEG。在此过程中无法使用递归, 需借助队列以保存早前遍历的顶点信息。当当前节点不存在邻接边时, 便以队列头部元素为起点展开同样的遍历, 直至队列中所有元素弹出, 也就是队列为空时遍历结束。
下面给出完整代码：
package com.xxx.algorithm.wh.graph2; import java.util.LinkedList; import java.util.Queue; public class Graph { private final int MAX_VERTS=20; private char[] vertexs; private int[][] matrix; private int nVerts; private Queue q; public Graph(){ vertexs = new char[MAX_VERTS]; matrix = new int[MAX_VERTS][MAX_VERTS]; for(int i=0;i(); } public void addEdge(int start,int end){ matrix[start][end] = 1; matrix[end][start] = 1; } public void addVertex(char label){ vertexs[nVerts++] = label; } public void deepFirstSearch(int v){ System.out.print("dfs : "); boolean visited[] = new boolean[MAX_VERTS]; for(int i=0;i运行程序，打印信息如下：
dfs : A B C D E F G bfs : A B D F C E G
到这个地步, 仅是运用了一个类, 便达成了图数据结构的构建以及搜索这一行为, 相对而言是颇为简洁, 然而, 这样的一种方式, 仅适宜于简单的无向图, 稍微复杂些的带权图, 就并非如此简单罢了。