通过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_VERTS20; 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 i0;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 i0;i运行程序打印信息如下dfs : A B C D E F G bfs : A B D F C E G到这个地步, 仅是运用了一个类, 便达成了图数据结构的构建以及搜索这一行为, 相对而言是颇为简洁, 然而, 这样的一种方式, 仅适宜于简单的无向图, 稍微复杂些的带权图, 就并非如此简单罢了。
