java数据结构之图及其深度优先搜索与最小生成树

深碍√TFBOYSˉ_ 2022-04-03 07:22 181阅读 0赞

# 定义： #

图 (graph) 是由一些点 (vertex) 和这些点之间的连线 (edge) 所组成的；其中，点通常被成为 "顶点(vertex)"，而点与点之间的连线则被成为 "边或弧"(edege)。通常记为，G=(V,E)。

# DFS(Depth-first-search) 深度优先遍历 #

形象的说, 就像搜索文件夹, 从第一个开始文件夹开始搜索到底, 然后再搜索第二个到底, 然后第三个…. 一直到最后.   
官方的说:

a) 假设初始状态是图中所有顶点都未曾访问过，则可从图 G 中任意一顶点 v 为初始出发点，首先访问出发点 v，并将其标记为已访问过。

b) 然后依次从 v 出发搜索 v 的每个邻接点 w，若 w 未曾访问过，则以 w 作为新的出发点出发，继续进行深度优先遍历，直到图中所有和 v 有路径相通的顶点都被访问到。

c) 若此时图中仍有顶点未被访问，则另选一个未曾访问的顶点作为起点，重复上述步骤，直到图中所有顶点都被访问到为止。

![20181220232131196][]

注：红色数字代表遍历的先后顺序，所以图 (e) 无向图的深度优先遍历的顶点访问序列为：V0，V1，V2，V5，V4，V6，V3，V7，V8

如果采用邻接矩阵存储，则时间复杂度为 O(n2)；当采用邻接表时时间复杂度为 O(n+e)。

# BFS(Breadth-first-search) 广度优先搜索遍历 #

形象的, 类似于树的层次遍历, 一层层的找.

书面上:

广度优先搜索遍历 BFS 类似于树的按层次遍历。其基本思路是：

a) 首先访问出发点 Vi

b) 接着依次访问 Vi 的所有未被访问过的邻接点 Vi1，Vi2，Vi3，…，Vit 并均标记为已访问过。

c) 然后再按照 Vi1，Vi2，… ，Vit 的次序，访问每一个顶点的所有未曾访问过的顶点并均标记为已访问过，依此类推，直到图中所有和初始出发点 Vi 有路径相通的顶点都被访问过为止。

图示如下：

![20181220232131215][]

因此，图 (f) 采用广义优先搜索遍历以 V0 为出发点的顶点序列为：V0，V1，V3，V4，V2，V6，V8，V5，V7

如果采用邻接矩阵存储，则时间复杂度为 O(n2)，若采用邻接表，则时间复杂度为 O(n+e)。

# 邻接矩阵 #

维持一个二维数组，arr\[i\]\[j\] 表示 i 到 j 的边，如果两顶点之间存在边，则为 1，否则为 0；   
维持一个一维数组，存储顶点信息，比如顶点的名字；   
下图为一般的有向图：

![0_1331733733n6BY.gif][]  
注意：如果我们要看 vi 节点邻接的点，则只需要遍历 arr\[i\] 即可；

下图为带有权重的图的邻接矩阵表示法：

缺点：邻接矩阵表示法对于稀疏图来说不合理，因为太浪费空间；

java代码如下，因为时间关系没有写广度优先遍历，其实差不多，只不过是用队列实现，感兴趣的可以试一试咯

package 数据结构;
    
    public class Graph {
    	Stack mystack;
         int maxsize=10;//结点个数
         Vertex vertex[];//用来存储图的各个结点
         int juzhen[][];//图的邻接矩阵，表示图每条边的连通情况
         int nvertex=0;//初始顶点
         public Graph(int maxsize){
        	 vertex=new Vertex[maxsize];//图结点的容量初始化
        	 juzhen=new int [maxsize][maxsize];//矩阵的容量初始化
        	 mystack=new Stack(maxsize);
        	 for(int i=0;i<maxsize;i++){//初始化矩阵
        		 for(int j=0;j<maxsize;j++){
        			 juzhen[i][j]=0;//初始化每条边为0
        			 juzhen[j][i]=0;
        		 }
        	 }
         }
         public void addVertex(char a){
        	 vertex[nvertex++]=new Vertex(a);//添加顶点
         }
         public void addEdge(int start,int end){
        	 juzhen[start][end]=1;
        	 juzhen[end][start]=1;//添加边
         }
         public int getadjVertex(int v){
        	 for(int i=0;i<nvertex;i++){
        		 if(juzhen[v][i]==1&&vertex[i].wasvisited==false){
        			 return i;//得到与当前结点相连的结点，且没有被遍历过
        		 }
        	 }
        	 return -1;//找不到返回-1
         }
         public void dfs(){//先从0结点开始访问
        	 vertex[0].wasvisited=true;
        	 display(0);//显示该顶点
        	 mystack.push(0);//压入栈中
        	 while(!mystack.IsEmpty()){
        		 int v=getadjVertex((int)mystack.peek()); //得到栈顶元素且与它相邻未遍历的结点
        		 if(v==-1){//不符合要求，出栈
        			 mystack.pop();
        		 }else{
        			 vertex[v].wasvisited=true;//表示已遍历过
        			 display(v);//输出它
        			 mystack.push(v);//再将他压入栈，找他的相邻结点
        		 }
        	 }
        	 for(int i=0;i<nvertex;i++){
        		 vertex[i].wasvisited=false;//结束之后，恢复原状态
        	 }
        	 
         }
         public void display(int v){
        	 System.out.print(vertex[v].lable);
         }
         public void smallTree(){//找最小生成树
        	 vertex[0].wasvisited=true;
        	 mystack.push(0);//压入栈中
        	 while(!mystack.IsEmpty()){
        		 int currentvertex=(int )mystack.peek();//提取栈顶元素
        		 int v=getadjVertex((int)mystack.peek()); //找与栈顶相邻的结点
        		 if(v==-1){
        			 mystack.pop();//相邻的都被遍历过就出栈
        		 }else{
        			 vertex[v].wasvisited=true;//该节点已遍历过
        			 display(currentvertex);//打印出当前结点
        			 System.out.print("-");
        			 display(v); //打印与它相邻的结点
        			 mystack.push(v);//把相邻的结点入栈
        			 System.out.print(" ");;
        		 }
        	 }
        	 for(int i=0;i<nvertex;i++){
        		 vertex[i].wasvisited=false;//恢复图原来的状态
        	 }
        	 
         }
    }

图结点vertex类：

package 数据结构;
    
    public class Vertex {
          public  char lable;
          boolean wasvisited;
          public Vertex(char lable){
        	  this.lable=lable;
        	  
          }
    }

测试：

package 数据结构;
    
    public class TestGraph {
    public static void main(String args[]){
    	Graph graph=new Graph(10);
    	graph.addVertex('A');//char类型的顶点，int值记为0
    	graph.addVertex('B');//int值记为1；
    	graph.addVertex('C');//int值记为2
    	//设置边
    	graph.addVertex('D');
    	graph.addVertex('E');
    /*	graph.addEdge(0, 1);//AB连通
    	graph.addEdge(1, 2);//BC连通
    	graph.addEdge(2, 3);//CD连通
    	graph.addEdge(3, 4);//DE连通*/
    	graph.addEdge(0, 1);
    	graph.addEdge(0, 2);
    	graph.addEdge(0, 3);
    	graph.addEdge(0, 4);
    	graph.addEdge(1, 2);
    	graph.addEdge(1, 3);
    	graph.addEdge(1, 4);
    	graph.addEdge(2, 3);
    	graph.addEdge(2, 4);
    	graph.addEdge(3,4);
    	System.out.println("图的遍历");
    	graph.dfs();
    	System.out.println();
    	System.out.println("最小生成树的顺序");
    	graph.smallTree();
    	
    }
    }

结果如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2phdmFfX2xpeW9uZw_size_16_color_FFFFFF_t_70][]

好啦,这次就到这里啦，有问题可以和我留言哦！

邮箱：2321591758@qq.com

其他博客的链接：

[Github个人网站][Github]      [知乎][Link 1]      [简书][Link 2]

欢迎各位访问哦，这次就到这里啦！

[20181220232131196]: /images/20220403/5264017c9afb4415a5b9b7a5a65762b5.png
[20181220232131215]: /images/20220403/9d8c38b9fd15470bb2521cd9e48ce0ad.png
[0_1331733733n6BY.gif]: /images/20220403/14c0cd0404e4480fba25d1ae83bc4d57.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2phdmFfX2xpeW9uZw_size_16_color_FFFFFF_t_70]: /images/20220403/e8855c2d65e347b18975754ec6de69e9.png
[Github]: http://www.imlowliness.club
[Link 1]: https://www.zhihu.com/people/li-yong-ji-suan-ji/activities
[Link 2]: https://www.jianshu.com/u/6c1284ced65e