江苏龙网

  1. 主页 > 生活百科 > >

数据结构与算法：图形结构( 二 )

图形结构


数据结构与算法：图形结构

文章插图
 
邻接顶点没有未访问的，进行回溯，直到遇到未访问的邻接顶点
数据结构与算法：图形结构

文章插图
 
当所有顶点都被访问过时，退出算法
数据结构与算法：图形结构

文章插图
 
下面是深度优先搜索的过程动画
数据结构与算法：图形结构

文章插图
 
代码演示
public void dsf(){visited = new boolean[vertexes.size()];//以在集合中下标为0的顶点，进行深度搜索dsf(visited, 0);}/** * 深度优先搜索 * @param visited * @param row */public void dsf(boolean[] visited, int row){//输出当前顶点System.out.print(vertexes.get(row) + " -> ");//将当前顶点设为已访问visited[row] = true;//获取当前顶点的邻接顶点下标int index = getFirstNeighbor(row);//如果当前顶点有邻接顶点则进行深度搜索while (index != -1){//当邻接顶点未访问时，则递归遍历if (visited[index] != true){dsf(visited, index);}//当邻接顶点已访问时，则寻找另一个邻接顶点index = getNeighbor(row, index);}}宽度优先搜索宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型 。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想 。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果 。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止 。
宽度优先搜索算法类似于一个分层搜索的过程，宽度优先搜索算法需要一个队列以保持访问过顶点的顺序，以便按这个顺序来访问这些顶点的邻接顶点 。
思路：依次访问当前顶点的邻接顶点，并按访问顺序将这些邻接顶点存储在队列中，当当前顶点的所有邻接顶点都被访问后，从队列中弹出一个顶点，以该顶点为当前顶点继续该步骤，直到所有顶点都被访问过 。
依次访问当前顶点的所有邻接顶点，并把这些邻接顶点按访问顺序存储在队列中
数据结构与算法：图形结构

文章插图
 
当前顶点没有未访问的邻接顶点，从队列中弹出一个顶点，以该弹出顶点继续访问未访问的邻接顶点
数据结构与算法：图形结构

文章插图
 
注意，虽然图中的顶点都已经访问过了，但还是要等队列中的所有顶点弹出访问后，算法才结束
数据结构与算法：图形结构

文章插图
 
下面时宽度优先搜索的过程动画
数据结构与算法：图形结构

文章插图
 
代码演示
public void bfs(){visited = new boolean[vertexes.size()];////以在集合中下标为0的顶点，进行广度优先搜索bfs(visited, 0);}/** * 广度优先搜索 * @param visited * @param row */public void bfs(boolean[] visited, int row){//创建队列，存储遍历邻接顶点的顺序LinkedList queue = new LinkedList();//输出当前顶点System.out.print(vertexes.get(row) + " -> ");//将当前顶点设为已访问visited[row] = true;//将当前顶点加入队列中queue.add(row);//当队列不为空时，即有未搜索的邻接顶点，进行搜索while (!queue.isEmpty()){//按顺序从队列中弹出邻接顶点下标int last = (Integer)queue.removeFirst();//获取该弹出顶点的邻接顶点下标int index = getFirstNeighbor(last);//当弹出顶点有邻接顶点时，进行广度搜索while(index != -1){//当邻接顶点未访问时if(visited[index] != true){//输出该邻接顶点System.out.print(vertexes.get(index) + " -> ");//把该邻接顶点设为已访问visited[index] = true;//将该邻接顶点加入队列queue.addLast(index);}//继续寻找弹出顶点的另一个邻接顶点index = getNeighbor(last, index);}}}完整演示代码public class GraphDemo {public static void main(String[] args) {String[] s = {"A","B","C","D","E","F","G"};Graph graph = new Graph(s);//A-B A-C A-G A-F F-D F-E D-E E-Ggraph.connect(0, 1);graph.connect(0, 2);graph.connect(0, 6);graph.connect(0, 5);graph.connect(5, 3);graph.connect(5, 4);graph.connect(3, 4);graph.connect(4, 6);graph.showGraphMatrix();graph.dsf();//A -> B -> C -> F -> D -> E -> G ->System.out.println();graph.bfs();//A -> B -> C -> F -> G -> D -> E ->}}//图形结构class Graph {//存储图中所有顶点private List<String> vertexes;//图形结构的邻接矩阵private int[][] matrix;//各顶点访问情况，true为已访问，false为未访问private boolean[] visited;/*** 根据传入的顶点信息生成矩阵* @param s*/public Graph(String s[]) {vertexes = new ArrayList<>();for (String vertex : s){vertexes.add(vertex);}matrix = new int[s.length][s.length];}/*** 将俩个顶点连接，即生成边* @param index1 顶点在集合中的索引* @param index2*/public void connect(int index1, int index2){if (index1 < 0 || index1 > matrix.length || index2 < 0 || index2 > matrix.length){throw new RuntimeException("该顶点未存在");}//将新的邻接添加的邻接矩阵中matrix[index1][index2] = 1;matrix[index2][index1] = 1;}/*** 展示邻接矩阵*/public void showGraphMatrix(){for (int arr[] : matrix){System.out.println(Arrays.toString(arr));}}public void dsf(){visited = new boolean[vertexes.size()];//以在集合中下标为0的顶点，进行深度优先搜索dsf(visited, 0);}/*** 深度优先搜索* @param visited* @param row*/public void dsf(boolean[] visited, int row){//输出当前顶点System.out.print(vertexes.get(row) + " -> ");//将当前顶点设为已访问visited[row] = true;//获取当前顶点的邻接顶点下标int index = getFirstNeighbor(row);//如果当前顶点有邻接顶点则进行深度搜索while (index != -1){//当邻接顶点未访问时，则递归遍历if (visited[index] != true){dsf(visited, index);}//当邻接顶点已访问时，则寻找另一个邻接顶点index = getNeighbor(row, index);}}public void bfs(){visited = new boolean[vertexes.size()];////以在集合中下标为0的顶点，进行广度优先搜索bfs(visited, 0);}/*** 广度优先搜索* @param visited* @param row*/public void bfs(boolean[] visited, int row){//创建队列，存储遍历邻接顶点的顺序Queue queue = new ArrayDeque();//输出当前顶点System.out.print(vertexes.get(row) + " -> ");//将当前顶点设为已访问visited[row] = true;//将当前顶点加入队列中queue.add(row);//当队列不为空时，即有未搜索的邻接顶点，进行搜索while (!queue.isEmpty()){//按顺序从队列中弹出邻接顶点下标int last = (Integer)queue.poll();//获取该弹出顶点的邻接顶点下标int index = getFirstNeighbor(last);//当弹出顶点有邻接顶点时，进行广度搜索while(index != -1){//当邻接顶点未访问时if(visited[index] != true){//输出该邻接顶点System.out.print(vertexes.get(index) + " -> ");//把该邻接顶点设为已访问visited[index] = true;//将该邻接顶点加入队列queue.add(index);}//继续寻找弹出顶点的另一个邻接顶点index = getNeighbor(last, index);}}}/*** 获取顶点在邻接矩阵对应行row中的第一个邻接顶点下标* @param row* @return 当有邻接顶点时返回邻接顶点下标，没有则返回-1*/public int getFirstNeighbor(int row){for(int i =0; i<matrix.length; i++){if (matrix[row][i] != 0){return i;}}return -1;}/*** 获取顶点在邻接矩阵对于行row中col列的下一个邻接顶点* @param row* @param col* @return 当有邻接顶点时返回邻接顶点下标，没有则返回-1*/public int getNeighbor(int row, int col){for (int i=col+1; i<matrix.length; i++){if (matrix[row][i] != 0){return i;}}return -1;}}


推荐阅读


上一篇：为什么有些公司不让用Lombok？

下一篇：trouble shooting 问题跟踪