这里就不再用书上的大堆废话的来说，广度优先搜索算法就是遍历一个图所有点的算法，也就说要对图中的每一个点进行访问，访问之后你才能对点进行操作。由于你对一个图进行操作，那么你必须对图上的每个点进行操作，所以如何访问图上的每一个点是一个图的基本问题，数据结构这里之所以是重点，除了其是图的根本还有其难度，广度优先搜索算法非常难写。网上搜了一大堆都不知道写什么的东西，书上伪代码众多，如何把伪代码转化成真正的代码其实是一个非常非常难的问题。首先，图上的点就不好表示，在Java中你怎么表示一个点？然后这个点构成的图怎么表示？其次再是算法。
之所以不讨论深度优先搜索是因为这个算法要用到迭代，当然据说用栈也可以实现，但遍历起来没有广度直观。
一、基本思想
一个图的如下所示：
我们已知的是：这个图的点集vexs，边集edges，那么如何求其各个连通分量。
不用编程求连通分量当然简单，你一画出这个图，然后一看就知道，连通分量分别是集合{A, C, D, F, B, G, E}、{X, Y}。-_-!似乎这还可以用来当做离散数学与数据结构的期末考试题唉，估计有人确实不知道连通分量是什么。这个也不好解释，明显的{A, C, D, F, B, G, E}、{X, Y}是两个独立的连通分量……
二、基本思想
至于Java中怎么实现求连通分量呢？这个就没有画图这么简单，首先你要用遍历一个图，遍历的时候，从某一点开始，如果你发现你遍历再也不下去了，那么这次遍历遇到的点的集合就是一个连通分量，然后对这个连通分量中所有的点打上已经访问的标记，之后再选一个还没有被遍历到的点开始遍历，和上面一样，通过遍历遇到的点又是另一个连通分量，再把这些点打上已经访问标记，直到所有点都被访问为止。
三、制作过程
1、首先，把这个图的点集与边集转化成邻接表的来表示，主要是邻接表表示图在程序中比较爽，邻接表中的顶点可以用一个数组存起来，之后每个顶点散发出一个链表，代表自己所连接的点。有人就开始向我吐槽了，尼玛，Java中不是没有指针的吗？怎么能够形成链表结构呢？其实你完全可以在这个点类成员中，声明一个点类成员的嘛……所以初始化的时候，有了这些成员变量：
// 邻接表中表对应的链表的顶点
private class ENode {
int ivex; // 该边所指向的顶点的位置
ENode nextEdge; // 指向下一条弧的指针
}
// 邻接表中表的顶点
private class VNode {
char data; // 顶点信息
ENode firstEdge; // 指向第一条依附该顶点的弧
};
private VNode[] mVexs; // 顶点数组
mVexs就是专门用来存放邻接表中的顶点数组，其实就是点集，顶点类是VNode，ENode是在顶点散发出来的链表中的点，里面的ivex是表示这个点在顶点数组mVexs的位置，主要是用来程序处理，到时候广度遍历的时候，能够一下子飞到这个点，读完它所散发出来的链表，其实就是第几个点。
2、建立邻接表
（1）首先你点集有多大，我的邻接表的顶点数组就要有多大，你边集有多大，意味着我要处理几次，处理点集非常简单，因为点集就是顶点数组，然后顶点数组在初始化的时候没有散发出任何链表，所以所有的顶点数组的指向都为空。对于边集，你首先要找到这条边两端的点，这两个点必须存在于顶点数组所散发的链表当中，找到各自在顶点数组的位置，比如边集中的第一个A与C，这个A等待链接在顶点数组中的C之后，这个C等待链接在顶点数组的A之后
/*
* 创建图(用已提供的矩阵)
*
* 参数说明： vexs -- 顶点数组 edges -- 边数组
*/
public ListUDG(char[] vexs, char[][] edges) {
// 初始化"顶点数"和"边数"
int vlen = vexs.length;
int elen = edges.length;
// 初始化"顶点"
mVexs = new VNode[vlen];
for (int i = 0; i < vlen; i++) {
mVexs[i] = new VNode();
mVexs[i].data = vexs[i];
mVexs[i].firstEdge = null;
}
// 初始化"边"
for (int i = 0; i < elen; i++) {
// 读取边的起始顶点和结束顶点
int p1 = getPosition(edges[i][0]);
int p2 = getPosition(edges[i][1]);
// 初始化node1
ENode node1 = new ENode();
node1.ivex = p2;
// 将node1链接到"p1所在链表的末尾"
if (mVexs[p1].firstEdge == null)
mVexs[p1].firstEdge = node1;
else
linkLast(mVexs[p1].firstEdge, node1);
// 初始化node2
ENode node2 = new ENode();
node2.ivex = p1;
// 将node2链接到"p2所在链表的末尾"
if (mVexs[p2].firstEdge == null)
mVexs[p2].firstEdge = node2;
else
linkLast(mVexs[p2].firstEdge, node2);
}
}
（2）找这个点在顶点数组的数组的位置int getPosition(char ch)，由于边集的中穿过来的是A与C这些字符，我们必须弄出一个方法，能看看A是在顶点数组的什么位置，C在顶点数组的什么位置，便于程序处理：
private int getPosition(char ch) {
for (int i = 0; i < mVexs.length; i++)
if (mVexs[i].data == ch)
return i;
return -1;
}
这个方法非常简单，遍历整个顶点数组，看那个顶点里面的内容就是我传过来的内容，然后返回一个i，就是顶点数组的第几个点嘛！
（3）把点连接到顶点散发的链表的最后位置void linkLast(ENode list, ENode node) ，如果顶点还没有指向任何东西，就不会考虑的，直接把顶点的firstEdge从null改成这个待连接的链表上的点，如果顶点有散发出链表，就执行下面的方法：
private void linkLast(ENode list, ENode node) {
ENode p = list;
while (p.nextEdge != null)
p = p.nextEdge;
p.nextEdge = node;
}
传过来的是顶点所指向的第一个结点list，还有待链接的一个链表上的点node，之后就没什么好说了，不懂回家打PP，数据结构中单链表的遍历、与单链表的最后添加一个元素，你好意思不会吗？那你数据结构不要想及格了，或者是，怎么能够及格的？这可是脑残题！
3、之后，整个邻接表就建立起来了，可以打印出来看一下：
/*
* 打印矩阵队列图
*/
public void print() {
System.out.printf("List Graph:\n");
for (int i = 0; i < mVexs.length; i++) {
System.out.printf("%d(%c): ", i, mVexs[i].data);
ENode node = mVexs[i].firstEdge;
while (node != null) {
System.out.printf("%d(%c) ", node.ivex, mVexs[node.ivex].data);
node = node.nextEdge;
}
System.out.printf("\n");
}
}
首先打印一个顶点数组中的顶点，之后遍历整个顶点数组散发出来的单链表，接着读一下个顶点数组中的顶点……
4、下面对这个邻接表进行BFS的广度优先搜索算法，并且求出各个连通分量。求连通分量在上面的基本思想已经说过了，这里主要是怎么实现BFS，也就是广度优先搜索。首先建立一个辅助队列，head,rear是这个队列的操作变量，具体翻翻数据结构的书籍，看怎么用数组操作队列的，以后有时间或许再给大家用Java做做。其实很容易理解，head与rear相等证明这个队列为空，入读移rear，出队移head，出一个移一次。回到正题，这个队列主要是用来存放顶点数组中散发的结点中未必访问的点。List<List<String>>
list = new ArrayList<List<String>>();主要用来存连通分量的数组，里面的List是用来存连通分量。
/*
* 广度优先搜索（类似于树的层次遍历）
*/
public List<List<String>> BFS() {
int head = 0;
int rear = 0;
int[] queue = new int[mVexs.length]; // 辅组队列
boolean[] visited = new boolean[mVexs.length]; // 顶点访问标记
for (int i = 0; i < mVexs.length; i++)
visited[i] = false;
List<List<String>> list = new ArrayList<List<String>>();
for (int i = 0; i < mVexs.length; i++) {
List<String> l = new ArrayList<String>();
if (!visited[i]) {
visited[i] = true;
l.add("" + mVexs[i].data);
queue[rear++] = i; // 入队列
}
while (head != rear) {
int j = queue[head++]; // 出队列
ENode node = mVexs[j].firstEdge;
while (node != null) {
int k = node.ivex;
if (!visited[k]) {
visited[k] = true;
l.add("" + mVexs[k].data);
queue[rear++] = k;
}
node = node.nextEdge;
}
}
if (l.size() > 0) {
list.add(l);
}
}
return list;
}
首先把顶点数组中所有顶点都设置成没有被读到，然后开始读，读顶点先把它自身与它所散发出来的链表中的、没有被访问的点入队列与连通分量集合，再一个一个出队，则对顶点散发链表中的点，所散发出来的链表上的点进行入队列与连通分量集合。这样才算遍历完成一个顶点，再读下一个顶点，有的顶点可能其后的所有点，都被读过，这是因为它已经是连通分量中的一员。这段话可能难以理解，画个图就明白了：
之后，发现遍历A之后，除了X、Y都遍历过，之后读顶点数组下一个B，同A的遍历，发现都遍历过了，全部都不要处理，产生的连通分量大小为0，不入加入连通分量数组，之后的C、D、E、F、G同是，直到X才出现一个长度为2的连通分量数组[X,Y]再连通分量数组，之后的Y又产生一个大小为0的连通分量。
至此，所有的顶点遍历完，在连通分量数组中躺着两个预想中的连通分量：{A, C, D, F, B, G, E}、{X, Y}整道题做完！
整个程序连起来如下：
import java.util.*;
class ListUDG {
// 邻接表中表对应的链表的顶点
private class ENode {
int ivex; // 该边所指向的顶点的位置
ENode nextEdge; // 指向下一条弧的指针
}
// 邻接表中表的顶点
private class VNode {
char data; // 顶点信息
ENode firstEdge; // 指向第一条依附该顶点的弧
};
private VNode[] mVexs; // 顶点数组
/*
* 创建图(用已提供的矩阵)
*
* 参数说明： vexs -- 顶点数组 edges -- 边数组
*/
public ListUDG(char[] vexs, char[][] edges) {
// 初始化"顶点数"和"边数"
int vlen = vexs.length;
int elen = edges.length;
// 初始化"顶点"
mVexs = new VNode[vlen];
for (int i = 0; i < vlen; i++) {
mVexs[i] = new VNode();
mVexs[i].data = vexs[i];
mVexs[i].firstEdge = null;
}
// 初始化"边"
for (int i = 0; i < elen; i++) {
// 读取边的起始顶点和结束顶点
int p1 = getPosition(edges[i][0]);
int p2 = getPosition(edges[i][1]);
// 初始化node1
ENode node1 = new ENode();
node1.ivex = p2;
// 将node1链接到"p1所在链表的末尾"
if (mVexs[p1].firstEdge == null)
mVexs[p1].firstEdge = node1;
else
linkLast(mVexs[p1].firstEdge, node1);
// 初始化node2
ENode node2 = new ENode();
node2.ivex = p1;
// 将node2链接到"p2所在链表的末尾"
if (mVexs[p2].firstEdge == null)
mVexs[p2].firstEdge = node2;
else
linkLast(mVexs[p2].firstEdge, node2);
}
}
/*
* 广度优先搜索（类似于树的层次遍历）
*/
public List<List<String>> BFS() {
int head = 0;
int rear = 0;
int[] queue = new int[mVexs.length]; // 辅组队列
boolean[] visited = new boolean[mVexs.length]; // 顶点访问标记
for (int i = 0; i < mVexs.length; i++)
visited[i] = false;
List<List<String>> list = new ArrayList<List<String>>();
for (int i = 0; i < mVexs.length; i++) {
List<String> l = new ArrayList<String>();
if (!visited[i]) {
visited[i] = true;
l.add("" + mVexs[i].data);
queue[rear++] = i; // 入队列
}
while (head != rear) {
int j = queue[head++]; // 出队列
ENode node = mVexs[j].firstEdge;
while (node != null) {
int k = node.ivex;
if (!visited[k]) {
visited[k] = true;
l.add("" + mVexs[k].data);
queue[rear++] = k;
}
node = node.nextEdge;
}
}
if (l.size() > 0) {
list.add(l);
}
}
return list;
}
/*
* 返回ch与邻接表顶点数组的位置
*/
private int getPosition(char ch) {
for (int i = 0; i < mVexs.length; i++)
if (mVexs[i].data == ch)
return i;
return -1;
}
/*
* 将node节点链接到list的最后
*/
private void linkLast(ENode list, ENode node) {
ENode p = list;
while (p.nextEdge != null)
p = p.nextEdge;
p.nextEdge = node;
}
/*
* 打印矩阵队列图
*/
public void print() {
System.out.printf("List Graph:\n");
for (int i = 0; i < mVexs.length; i++) {
System.out.printf("%d(%c): ", i, mVexs[i].data);
ENode node = mVexs[i].firstEdge;
while (node != null) {
System.out.printf("%d(%c) ", node.ivex, mVexs[node.ivex].data);
node = node.nextEdge;
}
System.out.printf("\n");
}
}
}
public class Graph_Ergodic {
public static void main(String[] args) {
char[] vexs = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'X', 'Y' };
char[][] edges = new char[][] { { 'A', 'C' }, { 'A', 'D' },
{ 'A', 'F' }, { 'B', 'C' }, { 'C', 'D' }, { 'E', 'G' },
{ 'F', 'G' }, { 'X', 'Y' } };
ListUDG pG;
pG = new ListUDG(vexs, edges);
pG.print(); // 打印图
List<List<String>> list = pG.BFS(); // 广度优先遍历
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
}
运行结果：
发现整道题目对于计算机考研的同学们非常有意义，尤其408的考试者，用到了单链表遍历、队列操作，并且考查了邻接表、广度优先遍历算法BFS、图的基本概念。拿去做408的第一题，15分的数据结构编程题，也不足为过！