文章目录
- 一、介绍
- 二、图的建立
-
- 2.1建立图类
- 2.2建立图
- 三、BFS
-
- 3.1图解：
- 3.2代码
- 四、DFS和BFS完整代码
一、介绍
图的DFS(深度优先搜索)与BFS(广度优先搜索)是图的两种遍历方式。
主要区别在于当到达图中的一个顶点后，DFS直接到达其中的一个（未遍历过的）顶点，之后再以这个新的顶点为基点重复上面的操作；而BFS到达图中的一个顶点后，会先遍历顶点周围的所有（未遍历过的）顶点，然后在以其中的一个顶点为基点，重复上面的操作。
举个简单的例子：
如果分别用DFS和BFS进行遍历（以A为起点）：
DFS：A B D E C (一条路走到头)
BFS：A B C D E (先把A的周围走完，接着走完B和C的周围)
这篇文章将进行BFS的分析，前一篇文章分析DFS。
二、图的建立
2.1建立图类
- 使用邻接矩阵保存图的信息。
- 为了给每个顶点起名字，使用了两组map集合使顶点的名字与邻接矩阵的数字一一对应。
- 用boolean型数组记录某节点是否被访问过。
代码：
class graph{
int vertexNum;//顶点数
int edgeNum;//边数
int[][] adjacentMatrix;//邻接矩阵
boolean[] isVisited;//各顶点是否被访问
Map<Character,Integer> nameToNum;
Map<Integer,Character> numToName;
int index;//顶点名称的下标
//构造函数
graph(int vertexnum, int edgenum){
vertexNum = vertexnum;
edgeNum = edgenum;
adjacentMatrix = new int[vertexNum][vertexNum];
nameToNum = new HashMap<>();
numToName = new HashMap<>();
isVisited = new boolean[vertexnum];
}
//顶点名称
public void addVertexName(char vertex){
nameToNum.put(vertex,index);
index++;
}
//反转顶点和其索引的对应关系
public void invertNameToNum(){
Set<Character> chs = nameToNum.keySet();
for (Character c : chs) {
numToName.put(nameToNum.get(c),c);
}
}
//打印两个map
public void printMap(){
System.out.println("name to num:");
Set<Character> chs = nameToNum.keySet();
for (Character c : chs) {
System.out.println(c + "->" + nameToNum.get(c));
}
System.out.println();
System.out.println("num to name:");
Set<Integer> ins = numToName.keySet();
for (Integer in : ins) {
System.out.println(in+"->"+ numToName.get(in));
}
}
//添加边
public void addEdge(char vertex1, char vertex2, int weight){
adjacentMatrix[nameToNum.get(vertex1)][nameToNum.get(vertex2)] = weight;
adjacentMatrix[nameToNum.get(vertex2)][nameToNum.get(vertex1)] = weight;
}
//打印邻接矩阵
public void printAdjacentMatrix(){
for (int[] am : adjacentMatrix) {
for (int i : am) {
System.out.print(i + " ");
}
System.out.println();
}
}
}
2.2建立图
以下面的图为例，建立图结构。
main方法中的代码：
public static void main(String[] args) {
//while (true) {
System.out.println("请输入顶点数：");
Scanner sc = new Scanner(System.in);
int vertexNum = sc.nextInt();
System.out.println("请输入边数：");
int edgeNum = sc.nextInt();
graph gr = new graph(vertexNum, edgeNum);
for (int i = 0; i < vertexNum; i++) {
System.out.println("请输入第" + i + "个顶点的名称：");
gr.addVertexName(sc.next().charAt(0));//字符串的第一个字符存入
}
gr.invertNameToNum();
for (int i = 0; i < edgeNum; i++) {
System.out.println("请输入第" + i + "条边(name1 name2 weight)：");
gr.addEdge(sc.next().charAt(0), sc.next().charAt(0), 1);//无向图权重为1，不用输入
}
gr.printAdjacentMatrix();
}
依次输入相关信息：
出来的邻接矩阵：
三、BFS
- BFS方法使用队列进行遍历。
- 先将出发点压入队列，之后将其周围的点压入队列。
- 出队列的过程就是遍历输出的过程。
- 每次出队列时，将其周围的（未遍历过的）顶点都入队列。
- 当队列中没有元素了，就表明遍历完成。
3.1图解：
以A为起始点，将A的周围顶点都入队列（队列=ABCD），A出队列输出A，A周围的顶点都入队列了，不用执行入队列操作。
此时队列=BCD，B出队列，输出B，将B相邻顶点E入队列。
此时队列=BCDE，C出队列，输出C，将C相邻顶点F入队列。
此时队列=DEF，D出队列，输出D，将D相邻顶点G入队列。
此时队列=EFG，E出队列，输出E。后面循环这个操作，依次输出E，F，G。
输出顺序为：A B C D E F G。
代码：
3.2代码
graph类中的方法。
public void BFS(){
Queue<Integer> qu = new ArrayDeque<>();//创建队列
qu.add(0);//从第0开始访问
System.out.print(numToName.get(0)+ "->");
isVisited[0] = true;
while(!qu.isEmpty()){ //队列是否为非空
int po = qu.poll();//出队列
int start = 0;
while(start < vertexNum ){ //将周围的顶点（未标记过的）入队列
if(adjacentMatrix[po][start] != 0 && !isVisited[start]){
qu.add(start);//入队列
System.out.print(numToName.get(start)+"->");//输出
isVisited[start] = true;//标记为访问过
}
start++;
}
}
System.out.println("结束");
}
结果：A->B->C->D->E->F->G->结束
四、DFS和BFS完整代码
package graph;
import java.util.*;
public class BFSAndDFS {
public static void main(String[] args) {
System.out.println("请输入顶点数：");
Scanner sc = new Scanner(System.in);
int vertexNum = sc.nextInt();
System.out.println("请输入边数：");
int edgeNum = sc.nextInt();
graph gr = new graph(vertexNum, edgeNum);
for (int i = 0; i < vertexNum; i++) {
System.out.println("请输入第" + i + "个顶点的名称：");
gr.addVertexName(sc.next().charAt(0));//字符串的第一个字符存入
}
gr.invertNameToNum();
for (int i = 0; i < edgeNum; i++) {
System.out.println("请输入第" + i + "条边(name1 name2 weight)：");
gr.addEdge(sc.next().charAt(0), sc.next().charAt(0), 1);
}
gr.printAdjacentMatrix();
gr.DFS();
gr.BFS();
}
}
class graph{
int vertexNum;//顶点数
int edgeNum;//边数
int[][] adjacentMatrix;//邻接矩阵
boolean[] isVisited;//各顶点是否被访问
Map<Character,Integer> nameToNum;
Map<Integer,Character> numToName;
int index;//顶点名称的下标
//构造函数
graph(int vertexnum, int edgenum){
vertexNum = vertexnum;
edgeNum = edgenum;
adjacentMatrix = new int[vertexNum][vertexNum];
nameToNum = new HashMap<>();
numToName = new HashMap<>();
isVisited = new boolean[vertexnum];
}
//顶点名称
public void addVertexName(char vertex){
nameToNum.put(vertex,index);
index++;
}
//反转顶点和其索引的对应关系
public void invertNameToNum(){
Set<Character> chs = nameToNum.keySet();
for (Character c : chs) {
numToName.put(nameToNum.get(c),c);
}
}
//打印两个map
public void printMap(){
System.out.println("name to num:");
Set<Character> chs = nameToNum.keySet();
for (Character c : chs) {
System.out.println(c + "->" + nameToNum.get(c));
}
System.out.println();
System.out.println("num to name:");
Set<Integer> ins = numToName.keySet();
for (Integer in : ins) {
System.out.println(in+"->"+ numToName.get(in));
}
}
//添加边
public void addEdge(char vertex1, char vertex2, int weight){
adjacentMatrix[nameToNum.get(vertex1)][nameToNum.get(vertex2)] = weight;
adjacentMatrix[nameToNum.get(vertex2)][nameToNum.get(vertex1)] = weight;
}
//打印邻接矩阵
public void printAdjacentMatrix(){
for (int[] am : adjacentMatrix) {
for (int i : am) {
System.out.print(i + " ");
}
System.out.println();
}
}
public void DFS(int index){
System.out.print(numToName.get(index) + "->");
isVisited[index] = true;
int start = 0;
while( start < vertexNum && (adjacentMatrix[index][start] == 0||(adjacentMatrix[index][start] != 0 && isVisited[start]))){
start++;
}
if(start > vertexNum - 1){
return;
}
DFS(start);
}
public void DFS(){
for (int i = 0; i < vertexNum; i++) {
if(!isVisited[i]){
DFS(i);
}
}
System.out.println("结束");
for (int i = 0; i < isVisited.length; i++) {
isVisited[i] = false;
}
}
public void BFS(){
Queue<Integer> qu = new ArrayDeque<>();//创建队列
qu.add(0);//从第0开始访问
System.out.print(numToName.get(0)+ "->");
isVisited[0] = true;
while(!qu.isEmpty()){
int po = qu.poll();
int start = 0;
while(start < vertexNum ){
if(adjacentMatrix[po][start] != 0 && !isVisited[start]){
qu.add(start);
System.out.print(numToName.get(start)+"->");
isVisited[start] = true;
}
start++;
}
}
System.out.println("结束");
}
}
