您的位置: 首页  >  文章  >  图的基本概念表示方法以及两种搜索方式——深度优先遍历和广度优先遍历

图的基本概念表示方法以及两种搜索方式——深度优先遍历和广度优先遍历

分类: 文章 • 2024-02-17 21:46:16

原贴查看：https://blog.****.net/qq_34528297/article/details/73008288


原先的知识没好好学，导致现在很多都忘了，或者说以前就没弄懂过。现在重新看一遍，收获良多，不管怎样先写这篇基础的，当做笔记。

图的定义：是由顶点的有穷非空集合和顶点之间的边的集合组成的，通常表示为 G（V,E）。其中G表示一个图，V是图的顶点的集合，E是图的边的集合。

有跟多条边的图我们称为稠密图，很少条边的我们称为稀疏图。

有向图和无向图：

无向图：顶点之间的边是没有方向的，也就是两个方向互通的。比如顶点 Vi 和顶点 Vj 之间的边，用（Vi,Vj）表示。

有向图：顶点间的边是有方向的，称为有向边，也成为 弧（Arc）。比如顶点Vi指向顶点Vj 的弧，用有序的偶：

<Vi,Vj> 表示，Vi称为弧尾，Vj 称为弧头。


如果无向图中任意两个顶点之间都存在边，则称该图是无向完全图。n 个顶点的无向图有 （n - 1）*n / 2条边。

与图的边或者弧有关的数叫做权（权值，Weight），带权的图通常称为网。


连通图：如果顶点Vi 到Vj 有路径，则称Vi 和Vj 是连通的。如果对于图中的任意两个顶点 Vi 和 Vj 是连通的则称该图为连通图。

无向图中的极大连通子图称为连通分量。


度：一个顶点所连接的边的数目，是对无向图而言的

入度和出度：一个顶点指向其他顶点的弧的数目称为出度，其他顶点指向该顶点的弧的数目称为入度。


图的存储结构：邻接矩阵、邻接表、十字链表临街多重表等。


邻接矩阵的存储方式：

用一个一维的数组来存储存储图中的顶点信息，用一个二维的数组来存储图中边的或者弧的信息。

邻接矩阵简单的定义图的结构：

[java] view plain copy
  1. <span style="font-size:18px;">public class graph {  
  2.       
  3.     public char[] vexs;     //顶点  
  4.     public int[][] arc;     //邻接矩阵  
  5.     int numVexs;            //顶点数  
  6.     int numEdges;           //边数  
  7.   
  8.     public graph(int nVexs,int nEdg){  
  9.         this.numVexs = nVexs;  
  10.         this.numEdges = nEdg;  
  11.     }  
  12. }</span>  
我们先用一位数组 vexs 存储 n 个顶点的信息，然后一个 n*n 的二维数组 arc 存储边或者弧。arc[ i ][ j ] 等于 1 表示顶点 Vi 连通 Vj （如果是无向图那么 arc[ j ][ i ] 也为 1），等于 0 则说明这两个顶点之间没有边或者弧 。无向图的邻接矩阵是对称的。

邻接矩阵是一种不错的存储图的数据结构，但是当顶点相对较多而边相对较少的时候，二维的邻接矩阵显得有点浪费。
所以这里引入邻接表：用一个一维数组存储顶点，顶点的邻接点构成一个线性表。我们把这种数组和线性表相组合的存储方法称为邻接表。

十字链表、多重链表就不说了。

接下来重点说图的遍历：从图中的某一顶点出发访问图中的其余顶点，且每个顶点仅访问一次，这 一过程称为图的遍历。
深度优先遍历（Depth First Search）：也称为深度优先搜索，DFS，深度优先搜索其实是一个递归过程，一条路先走到底有，点像二叉树的先序遍历。我们需要一个数组 visited 来标记已经访问过的顶点 ，visited[ i ] = false 表示未访问，true 表示已经访问过。
具体实现：
[java] view plain copy
  1. package com.hunter.Graph;  
  2. /** 
  3.  * 深度优先搜索 
  4.  * @author luzi 
  5.  * 
  6.  */  
  7. public class graphDFS {  
  8.       
  9.     public void DFSraverse(graph gh){  
  10.           
  11.         //初始化visited数组，用  false 以表示该顶点是否已经访问过  
  12.         boolean[] visited = new boolean[gh.numVexs];  
  13.         for(int i = 0; i < gh.numVexs; i++){  
  14.             visited[i] = false;  
  15.         }  
  16.         System.out.println();  
  17.         for(int i = 0; i < gh.numVexs; i++){  
  18.             if(!visited[i])  
  19.                 DFS(gh,i,visited);  
  20.         }  
  21.     }  
  22.   
  23.     private void DFS(graph gh, int k,boolean[] vi) {  
  24.         // TODO Auto-generated method stub  
  25.       
  26.         vi[k] = true;  
  27.         System.out.println("正访问的结点是 ： " + gh.vexs[k]);  
  28.           
  29.         for(int i = 0; i < gh.numVexs; i++){  
  30.             if(gh.arc[k][i] == 1 && !vi[i])  
  31.                 DFS(gh,i,vi);  
  32.         }  
  33.     }     
  34. }  



广（宽）度优先遍历（Breadth First Search）：又称为广度优先搜索，简称BFS 。
遍历的过程是先从顶点 V0 出发，遍历与 V0 直接连接而又未访问过的顶点V1 、V2 、V3 等，再访问 与 V1直接连接且未访问过的顶点。同样用一个数组来标记一个顶点是否已经访问过，用一个队列来存储待访问的顶点。
具体实现：
[java] view plain copy
  1. package com.hunter.Graph;  
  2.   
  3. import java.util.LinkedList;  
  4. import java.util.Queue;  
  5.   
  6. public class graphBFS {  
  7.       
  8.     public void BFSraverse(graph gh){  
  9.           
  10.         Queue<Integer> que =  new LinkedList<Integer>();  
  11.         boolean[] visited = new boolean[gh.numVexs];  
  12.         for(int i = 0; i < gh.numVexs; i++)  
  13.             visited[i] = false;  
  14.           
  15.         for(int i = 0; i < gh.numVexs; i++){  
  16.               
  17.             if(!visited[i]){  
  18.                   
  19.                 visited[i] = true;  
  20.                 System.out.println("正在访问的节点是 ：" + gh.vexs[i]);  
  21.                 que.add(i);  
  22.                   
  23.                 while(!que.isEmpty()){  
  24.                     que.remove();  
  25.                       
  26.                     for(int j = 0; j <gh.numVexs; j++){  
  27.                           
  28.                         if(gh.arc[i][j] == 1 && !visited[j]){  
  29.                             visited[j] = true;  
  30.                             System.out.println("正在访问的节点是 ：" + gh.vexs[j]);  
  31.                             que.add(j);  
  32.                         }  
  33.                     }  
  34.                 }  
  35.             }  
  36.         }     
  37.     }  
  38. }  

深度优先和宽度优先的时间复杂度是一样的，但是访问的顺序不一样。
深度优先类似二叉树的先序遍历而宽度优先类似二叉树的层序遍历。

最后再看一个例子，有如下的无向图：
图的基本概念表示方法以及两种搜索方式——深度优先遍历和广度优先遍历


初始化该图，调用深度优先和宽度优先遍历：
[java] view plain copy
  1. package com.hunter.Graph;  
  2.   
  3. public class Demo {  
  4.       
  5.     public static void main(String args[]){  
  6.   
  7.         int numVexs = 7;  
  8.         int numEdges = 6;  
  9.         graph gh = new graph(numVexs,numEdges);  
  10.         gh.vexs = new char[numVexs];  
  11.         gh.vexs[0] = 'A';  
  12.         gh.vexs[1] = 'B';  
  13.         gh.vexs[2] = 'C';  
  14.         gh.vexs[3] = 'D';  
  15.         gh.vexs[4] = 'E';  
  16.         gh.vexs[5] = 'F';  
  17.         gh.vexs[6] = 'G';  
  18.           
  19.         gh.arc = new int[numVexs][numVexs];  
  20.         gh.arc[0][1] = 1;  
  21.         gh.arc[1][0] = 1;  
  22.         gh.arc[0][4] = 1;  
  23.         gh.arc[4][0] = 1;  
  24.         gh.arc[1][2] = 1;  
  25.         gh.arc[2][1] = 1;  
  26.         gh.arc[2][3] = 1;  
  27.         gh.arc[3][2] = 1;  
  28.         gh.arc[3][4] = 1;  
  29.         gh.arc[4][3] = 1;  
  30.         gh.arc[2][5] = 1;  
  31.         gh.arc[5][2] = 1;  
  32.         gh.arc[1][5] = 1;  
  33.         gh.arc[5][1] = 1;  
  34.         gh.arc[6][3] = 1;  
  35.         gh.arc[3][6] = 1;             
  36.           
  37.         System.out.println("********************广度优先搜索********************");  
  38.         graphDFS ghDFS = new graphDFS();  
  39.         ghDFS.DFSraverse(gh);  
  40.         System.out.println("********************广度优先搜索********************");  
  41.         graphBFS ghBFS = new graphBFS();  
  42.         ghBFS.BFSraverse(gh);  
  43.     }  
  44. }  



实际运行结果：

图的基本概念表示方法以及两种搜索方式——深度优先遍历和广度优先遍历


相关推荐