数据结构与算法|数据结构（第四章）深度优先|算法|数据结构

视频链接：https://www.bilibili.com/video/BV1HQ4y1d7th
视频范围P168 - P178

目录描述

1.图深度优先遍历
2.图广度优先遍历

1.图深度优先遍历深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问，第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点，可以这样理解每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
图类：

package graph; import java.util.ArrayList; import java.util.Arrays; public class Graph {//存储顶点 private ArrayList vertexList; //邻接矩阵 private int[][] edges; //边的数量 private int edgsNum; //是否访问过 private boolean[] isSelectd; public Graph(int len) { this.vertexList = new ArrayList(len); this.edges = new int[len][len]; this.isSelectd = new boolean[len]; }//插入顶点方法 public voidinsertVertex(String vertex){ this.vertexList.add(vertex); }//添加图的边 public void insertEdges(int x, int y,int w){ edges[x][y] = w; edges[y][x] = w; //添加边的数量 edgsNum++; }//返回顶点个数 public int getVertexSize(){ return this.vertexList.size(); }//返回边的个数 public int getEdgesSize(){ return this.edgsNum; }//获取顶点的权值 xy坐标下的权值 public int getWeight(int x,int y){ return this.edges[x][y]; }//输出邻接矩阵的图案 public void showList(){ for(int[] arr : edges){ System.out.println(Arrays.toString(arr)); } }//给定一个索引顶点位置，查找当前索引的第一个邻接点 //如果存在返回索引位置，如果不存在返回-1 public int getFirstVertex(int index){ for (int i = 0; i < vertexList.size(); i++) { if (edges[index][i] > 0){ return i; } } return -1; }//根据给点的坐标，获取下一个邻接顶点 public int getNextVertex(int x,int y){ for (int i = y + 1; i < vertexList.size(); i++) { if (edges[x][i] > 0){ return i; } } return -1; }//访问的顶点 public String getValueIndex(int i){ return this.vertexList.get(i); }//深度优先算法 public void dfs(boolean[] isSelectd,int i){ System.out.println(getValueIndex(i)); //表示已经被访问过了 isSelectd[i] = true; //获取第一个邻接顶点 int w = getFirstVertex(i); while (w != -1){//存在第一个邻接点 if (!isSelectd[w]){ dfs(isSelectd,w); } //被访问过 w = getNextVertex(i,w); } }public void dfs(){ for (int i = 0; i < getVertexSize(); i++) { if (! isSelectd[i]){ dfs(isSelectd,i); } } } }

测试类：

package graph; public class Test { public static void main(String[] args) { Graph graph = new Graph(5); String[] vertexs = {"A","B","C","D","E"}; for (String v : vertexs){ graph.insertVertex(v); }graph.insertEdges(0,1,1); graph.insertEdges(0,2,1); graph.insertEdges(1,2,1); graph.insertEdges(1,3,1); graph.insertEdges(1,4,1); graph.insertEdges(0,2,1); graph.showList(); graph.dfs(); } }

运行结果：

文章图片

2.图广度优先遍历类似于一个分层搜素的过程，广度优先遍历（Breadth-First-Search）需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点
【数据结构与算法|数据结构（第四章）】图类：

package graph; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; public class Graph {//存储顶点 private ArrayList vertexList; //邻接矩阵 private int[][] edges; //边的数量 private int edgsNum; //是否访问过 private boolean[] isSelectd; public Graph(int len) { this.vertexList = new ArrayList(len); this.edges = new int[len][len]; this.isSelectd = new boolean[len]; }//插入顶点方法 public voidinsertVertex(String vertex){ this.vertexList.add(vertex); }//添加图的边 public void insertEdges(int x, int y,int w){ edges[x][y] = w; edges[y][x] = w; //添加边的数量 edgsNum++; }//返回顶点个数 public int getVertexSize(){ return this.vertexList.size(); }//返回边的个数 public int getEdgesSize(){ return this.edgsNum; }//获取顶点的权值 xy坐标下的权值 public int getWeight(int x,int y){ return this.edges[x][y]; }//输出邻接矩阵的图案 public void showList(){ for(int[] arr : edges){ System.out.println(Arrays.toString(arr)); } }//给定一个索引顶点位置，查找当前索引的第一个邻接点 //如果存在返回索引位置，如果不存在返回-1 public int getFirstVertex(int index){ for (int i = 0; i < vertexList.size(); i++) { if (edges[index][i] > 0){ return i; } } return -1; }//根据给点的坐标，获取下一个邻接顶点 public int getNextVertex(int x,int y){ for (int i = y + 1; i < vertexList.size(); i++) { if (edges[x][i] > 0){ return i; } } return -1; }//访问的顶点 public String getValueIndex(int i){ return this.vertexList.get(i); }//广度优先算法 public void bfs(boolean[] isSelectd,int i){ //取出头结点 int u; //第一个邻接点 int w; //创建队列 LinkedList queue = new LinkedList(); System.out.println(getValueIndex(i)); isSelectd[i] = true; queue.addLast(i); while (!queue.isEmpty()){ u = (Integer)queue.removeFirst(); w = getFirstVertex(u); while (w != -1){ if (!isSelectd[w]){ System.out.println(getValueIndex(w)); isSelectd[w] = true; queue.addLast(w); } w = getNextVertex(u,w); } } }public void bfs(){ for (int i = 0; i < getVertexSize(); i++) { if (! isSelectd[i]){ bfs(isSelectd,i); } } } }

测试类：

package graph; public class Test { public static void main(String[] args) { Graph graph = new Graph(5); String[] vertexs = {"A","B","C","D","E"}; for (String v : vertexs){ graph.insertVertex(v); }graph.insertEdges(0,1,1); graph.insertEdges(0,2,1); graph.insertEdges(1,2,1); graph.insertEdges(1,3,1); graph.insertEdges(1,4,1); graph.insertEdges(0,2,1); graph.showList(); graph.bfs(); } }

运行结果：