大家好，我是被白菜拱的猪。

一个热爱学习废寝忘食头悬梁锥刺股，痴迷于girl的潇洒从容淡然coding handsome boy。

文章目录

一、写在前言二、图（一）深度优先遍历（二）广度优先遍历 三、结束语

一、写在前言

二、图

（一）深度优先遍历

深度优先遍历（Depth First Search）他是一条道走到黑，走不通了就回去再去走，直到把所有的路走完，这里有一个回溯的过程，所以我们可以运用递归，类似于树的前序遍历，代码很简单。这里不多说直接上代码

package com.codingboy.graph; import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; /** * @author: ljl * @date: 2020/9/2 16:42 * @description: 图 */ public class GraphDemo { public static void main(String[] args) { Graph graph = new Graph(5); String[] vertexes = {"A", "B", "C", "D", "E"}; //插入顶点 for (String vertex : vertexes) { graph.insertVertexe(vertex); } //插入边 graph.insertEdges(0,1,1); graph.insertEdges(0,3,1); graph.insertEdges(0,2,1); graph.insertEdges(1,3,1); graph.insertEdges(2,3,1); graph.insertEdges(2,4,1); graph.insertEdges(3,4,1); graph.show(); graph.dfs(0); } } class Graph { //顶点表 private ArrayList<String> vertexes = new ArrayList<>(); //邻接表 private int[][] arc; //顶点数 private int numVertexes; //边数 private int numEdges; //false 代表没有访问，true代表已经访问 private Boolean[] visited; public Graph(int numVertexes) { this.numVertexes = numVertexes; arc = new int[numVertexes][numVertexes]; visited = new Boolean[numVertexes]; //对数组赋初始值，开始都是false，表示没有被访问 for (int i = 0; i <numVertexes ; i++) { visited[i] = false; } } //添加顶点 public void insertVertexe(String value) { vertexes.add(value); } //添加表 public void insertEdges(int v1, int v2, int weight) { arc[v1][v2] = weight; arc[v2][v1] = weight; numEdges++; } public void show() { for (int[] link:arc) { System.out.println(Arrays.toString(link)); } } //深度优先遍历 public void dfs(int i) { //进来就说明已经访问 visited[i] = true; System.out.println(vertexes.get(i)); for (int j = 0; j < numVertexes; j++) { if (arc[i][j] == 1 && !visited[j]) { dfs(j); } } } }

在这里需要记住的就是借用了队列这个数据结构，保证了他的层序遍历的顺序性。

（二）广度优先遍历

广度优先遍历（Broad First Search）这就好像是水漫金山，鬼子扫荡，慢慢的扩大范围而不是像深度优先遍历一个道走到黑，这里借助了队列的数组结构，一个一个来搜索，类似于树的分层搜索。

public void bfs() { //借助数据结构队列 Queue<Integer> queue = new LinkedList<>(); //为了防止非连通图 for (int i = 0; i < numVertexes ; i++) { //这里假如是连通图的话其实就执行了一次 if (!visited[i]) { //表示已访问 visited[i] = true; //在入队前打印顶点 System.out.println(vertexes.get(i)); queue.add(i); while(!queue.isEmpty()) { //出队 Integer index = queue.poll(); for (int j = 0; j < numVertexes; j++) { if (arc[index][j] == 1 && !visited[j]) { //已访问 visited[j] = true; //打印元素 System.out.println(vertexes.get(j)); //入队 queue.add(j); } } } } } }

三、结束语

无论是dfs还是bfs他们的作用都是一样的，只不过遍历的方式不同，实际上的作用一样，一个好像是有针对性遍历，一个好像漫无目的。

最近开学学习的效率也没有提高多好，看博客笔记写的质量就知晓了，就拿这篇来说就有些敷衍，最近有些焦虑了，六级还有十几天，又得裸考了一次。

来到学校了反而觉得在某些方面更加的孤独了。