1.BFS(广度优先搜索)动图如下：
BFS.gif
java实现如下：
//模板
void bfs(){
将起始点放入队列中
标记起点访问
while(如果队列不为空){
访问队首元素
删除队首元素
for(x所有相邻的点){
if(该点未被访问过且合法){
将该点加入队列末尾
}
}
}
队列为空，广搜结束
}
//代码：（以上图为例）
import java.util.LinkedList;
import java.util.Queue;
public class BFSTest {
/**
* 队列
*/
private static Queue<Vertex> queue;
/**
* 邻接矩阵，0表示无边，1表示有边
*/
private int[][] edges;
/**
* 顶点
*/
private Vertex[] vertices;
/**
* 顶点个数
*/
private int size;
/**
* 初始化
*/
public BFSTest(Vertex[] vertices,int[][] edges){
queue=new LinkedList<>();
this.size=vertices.length;
this.vertices=vertices;
this.edges=edges;
}
public BFSTest(){}
/**
* BFS方法
*/
public void BFS(){
//向队列加入第一个顶点
queue.offer(vertices[0]);
//标记第一个顶点已经被访问
vertices[0].wasVisited=true;
//当队列不空
while (!queue.isEmpty()){
//从队列中弹出并返回顶点
Vertex item=queue.poll();
System.out.println(item);
int index=0;
//获取顶点所在的vertices数组的下标
if(item != null) {//这样设计避免了for循环
index = item.index;
}
//将与item相连的(即在item所在的行且邻接矩阵中值非0的)且未被访问的顶点加入到队列中
for(int i=0;i<size;i++){
if((edges[index][i] != 0) && (vertices[i].wasVisited == false)){
queue.offer(vertices[i]);
vertices[i].wasVisited=true;
}
}
}
}
public static void main(String[] args){
Vertex[] V={
new Vertex('0',0),
new Vertex('1',1),
new Vertex('2',2),
new Vertex('3',3),
new Vertex('4',4),
new Vertex('5',5),
new Vertex('6',6),
new Vertex('7',7),
new Vertex('8',8)
};
int[][] edges={
{0,1,1,0,0,0,0,0,0},
{0,0,0,1,1,0,0,0,0},
{0,0,0,0,1,1,1,0,0},
{0,0,0,0,1,0,0,0,0},
{0,1,0,0,0,0,0,1,0},
{0,0,0,0,0,0,1,0,0},
{0,0,1,0,0,0,0,0,1},
{0,0,0,0,0,1,0,0,0},
{0,0,0,0,0,0,0,0,0},
};
BFSTest b=new BFSTest(V,edges);
b.BFS();
}
/**
* 顶点类
* */
static class Vertex{
/**
* 顶点值
*/
private char vertex;
/**
* 第index个顶点（从0开始）,这么设计避免了for循环
*/
private int index;
/**
* 顶点是否被访问
*/
private boolean wasVisited;
public Vertex(char vertex,int index){
this.vertex = vertex;
this.index=index;
wasVisited = false;
}
@Override
public String toString() {
return "Vertex{" +
"vertex=" + vertex +
'}';
}
}
}
结果如下：
image.png
2.DFS(深度优先搜索)动图如下：
DFS.gif
java实现如下：（做了优化，运行过程和动图一样）
//模板
void dfs(){
输出起始顶点;
起始顶点改为“已访问”标志;
stack.push(起始顶点);
while(stack非空){
//取栈顶元素（不出栈）
item=stack.peek();
if(栈顶元素存在未被访问过的邻接点w){
输出邻接点w；
邻接点w改为“已访问”标志;
邻接点w进栈；
}else{
//当前顶点退栈
stack.pop();
}
}
栈为空，结束；
}
//代码
import java.util.Stack;
public class DFSTest {
/**
* 栈
*/
private static Stack<Vertex> stack;
/**
* 邻接矩阵，0表示无边，1表示有边
*/
private int[][] edges;
/**
* 顶点
*/
private Vertex[] vertices;
/**
* 顶点个数
*/
private int size;
/**
* 初始化
*/
public DFSTest(Vertex[] vertices, int[][] edges){
stack=new Stack<>();
this.size=vertices.length;
this.vertices=vertices;
this.edges=edges;
}
public DFSTest(){}
/**
* DFS方法
*/
public void DFS(){
//输出第一个顶点
System.out.println(vertices[0]);
//将第一个顶点压栈
stack.push(vertices[0]);
//标记已经被访问过
vertices[0].wasVisited=true;
//栈顶顶点
Vertex item;
//栈顶顶点所在的行
int row;
//需要回溯到某一行的某一列(避免每次都从第1列扫描每行，作为优化)
int column=0;
//当栈不空
while (!stack.isEmpty()){
item=stack.peek();
row=item.index;
column=isExistAdjacentPoint(row,column);
//判断栈顶元素是否存在未被访问过的邻接点
if(column == -1){//不存在
stack.pop();
//回溯到上一行的下一列，例如当前在2号顶点，2号顶点是从（6,2）过来的，
// 2号顶点已经遍历完了，发现没有满足条件的邻接点，那么下次就会遍历 （6,3）,
// 避免了从（6,0）开始遍历，这段代码利用了邻接矩阵中行与列的关系
column=row+1;
}else {//存在
System.out.println(vertices[column]);
vertices[column].wasVisited=true;
stack.push(vertices[column]);
//下一次从第一列开始遍历，例如（1,3）满足条件，
// 那么下次会从（3,0）开始遍历寻找与3相邻的邻接点
column=0;
}
}
}
/**
* 判断是否存在邻接点
* @param row 当前顶点所在的行号
* @param column 当前顶点所在的行的所有列
* @return 下标，若不存在，则返回-1
*/
private int isExistAdjacentPoint(int row, int column) {
for(int i=column;i<size;i++){
if((edges[row][i] !=0) && (vertices[i].wasVisited==false)){
return i;
}
}
return -1;
}
public static void main(String[] args){
Vertex[] V={
new Vertex('0',0),
new Vertex('1',1),
new Vertex('2',2),
new Vertex('3',3),
new Vertex('4',4),
new Vertex('5',5),
new Vertex('6',6),
new Vertex('7',7),
new Vertex('8',8)
};
int[][] edges={
{0,1,1,0,0,0,0,0,0},
{0,0,0,1,1,0,0,0,0},
{0,0,0,0,1,1,1,0,0},
{0,0,0,0,1,0,0,0,0},
{0,1,0,0,0,0,0,1,0},
{0,0,0,0,0,0,1,0,0},
{0,0,1,0,0,0,0,0,1},
{0,0,0,0,0,1,0,0,0},
{0,0,0,0,0,0,0,0,0},
};
DFSTest b=new DFSTest(V,edges);
b.DFS();
}
/**
* 顶点类
* */
static class Vertex{
/**
* 顶点值
*/
private char vertex;
/**
* 第index个顶点（从0开始）,这么设计避免了for循环
*/
private int index;
/**
* 顶点是否被访问
*/
private boolean wasVisited;
public Vertex(char vertex,int index){
this.vertex = vertex;
this.index=index;
wasVisited = false;
}
@Override
public String toString() {
return "Vertex{" +
"vertex=" + vertex +
'}';
}
}
}
结果如下：
image.png
-
构建邻接矩阵以及顶点数组例题：
image.png
