VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > 编程开发 > Java教程 >

  • 数据结构与算法(十三)

图的基本介绍

前面学过的 线性表 和 树：

  • 线性表：局限于一个 直接前驱 和 一个 直接后继 的关系
  • 树：只能有一个直接前驱（父节点）

当我们需要表示 多对多 的关系时，就需要用到图

比如：城市交通图。他就是一个图，对应程序中的图如下所示

图是一种 数据结构，其中节点可以具有 零个或多个相邻元素，两个节点之间的链接称为 边，节点页可以称为 顶点。

图的常用概念

  • 顶点（vertex）

  • 边（edge）

  • 路径：路径就是一个节点到达另一个节点所经过的节点连线

    D -> C 的路径就有两条（针对无向图来说）：

    • D → B → C
    • D → A → B → C

  • 无向图：顶点之间的连接没有方向

    比如上图它是一个 无向图；比如 A-B，可以是 A->B 也可以是 B <- A

  • 有向图：顶点之间的连接是有方向的。

  • 带权图：边有权值时，则叫做带权图，同时也叫 网

比如上图中，北京 到 上海这一条边上有一个数值 1463，这个可能是他的距离，这种就叫做 边带权值

图的表示方式

有两种：

  • 二维数组表示：邻接矩阵
  • 链表表示：邻接表

邻接矩阵

邻接矩阵是表示图形中 顶点之间相邻关系 的矩阵，对于 n 个顶点的图而言，矩阵的 row 和 col 表示的是 1....n 个点

邻接表

由于邻接矩阵有一个缺点：它需要为每个顶点都分配 n 个边的空间，其实有很多边都是不存在的（比如上面的 0,0 不链接，也需要表示出来），这 会造成空间的一定损失。

而 邻接表 的实现只关心 存在的边，因此没有空间浪费，由 数组 + 链表组成。

图的快速入门案例

要求用代码实现如下图结构

思路分析：

  • 每一个顶点需要用一个容器来装，这里使用简单的 String 类型来表示 A、B ... 等节点
  • 这些所有的顶点，我们用一个 List 来存储
  • 它对应的矩阵使用一个二维数组来表示，节点之间的关系

代码实现

复制代码



	
		

			
				

					 

					
			
				public class Graph {
		

		

			
				

					 

					
			
				private ArrayList<String> vertex;//表示图的顶点信息
		

		

			
				

					 

					
			
				private int[][] edge;//表示图中边的信息
		

		

			
				

					 

					
			
				private int numOfEdges;//表示边的条数
		

		

			
				

					 

					
			
				public static void main(String[] args) {
		

		

			
				

					 

					
			
				//测试图
		

		

			
				

					 

					
			
				int n = 5;
		

		

			
				

					 

					
			
				String[] arr = {"A","B","C","D","E"};
		

		

			
				

					 

					
			
				Graph graph = new Graph(5);
		

		

			
				

					 

					
			
				//添加顶点
		

		

			
				

					 

					
			
				for(String value : arr){
		

		

			
				

					 

					
			
				graph.insertVertex(value);
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				//添加边
		

		

			
				

					 

					
			
				//A-B A-C B-C B-D B-E
		

		

			
				

					 

					
			
				graph.insertEdge(0,1,1);
		

		

			
				

					 

					
			
				graph.insertEdge(0,2,1);
		

		

			
				

					 

					
			
				graph.insertEdge(1,2,1);
		

		

			
				

					 

					
			
				graph.insertEdge(1,3,1);
		

		

			
				

					 

					
			
				graph.insertEdge(1,4,1);
		

		

			
				

					 

					
			
				 
		

		

			
				

					 

					
			
				//显示图
		

		

			
				

					 

					
			
				graph.showGraph();
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				 
		

		

			
				

					 

					
			
				//创建图
		

		

			
				

					 

					
			
				public Graph(int n){
		

		

			
				

					 

					
			
				vertex = new ArrayList<>(n);
		

		

			
				

					 

					
			
				edge = new int[n][n];
		

		

			
				

					 

					
			
				numOfEdges = 0;//默认为0条边
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				 
		

		

			
				

					 

					
			
				//添加顶点
		

		

			
				

					 

					
			
				public void insertVertex(String s){
		

		

			
				

					 

					
			
				vertex.add(s);
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				 
		

		

			
				

					 

					
			
				/**
		

		

			
				

					 

					
			
				* 添加边
		

		

			
				

					 

					
			
				* @param v1 第一个节点
		

		

			
				

					 

					
			
				* @param v2 第二个节点
		

		

			
				

					 

					
			
				* @param weight 边的权重，我们规定0表示不能连接，1表示连接
		

		

			
				

					 

					
			
				*/
		

		

			
				

					 

					
			
				public void insertEdge(int v1,int v2,int weight){
		

		

			
				

					 

					
			
				edge[v1][v2] = 1;
		

		

			
				

					 

					
			
				edge[v2][v1] = 1;
		

		

			
				

					 

					
			
				numOfEdges++;
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				 
		

		

			
				

					 

					
			
				//获取顶点的数量
		

		

			
				

					 

					
			
				public int getVertexSize(){
		

		

			
				

					 

					
			
				return vertex.size();
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				//获取边的数量
		

		

			
				

					 

					
			
				public int getEdgeSize(){
		

		

			
				

					 

					
			
				return numOfEdges;
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				//根据下标获取顶点值
		

		

			
				

					 

					
			
				public String getValueByIndex(int i){
		

		

			
				

					 

					
			
				return vertex.get(i);
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				//返回两个顶点之间的权值
		

		

			
				

					 

					
			
				public int getWeight(int v1,int v2){
		

		

			
				

					 

					
			
				return edge[v1][v2];
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				//显示图矩阵
		

		

			
				

					 

					
			
				public void showGraph(){
		

		

			
				

					 

					
			
				for(int[] g : edge){
		

		

			
				

					 

					
			
				System.out.println(Arrays.toString(g));
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				}
		

	




	



	图的深度优先遍历介绍



	所谓图的遍历，则是 对节点的访问。一个图有很多个节点，如何遍历这些节点，需要特定策略，一般有两种访问策略：


    
	
  1. 
		深度优先遍历（DFS，Depth First Search）
    2. 
	
  2. 
		广度优先遍历（BFS，Broad First Search）
    3. 




	深度优先遍历基本思想



	图的深度优先搜索（Depth First Search），简称 DFS。



	从初始访问节点出发，初始访问节点可能有多个 邻接节点（直连），深度优先遍历的策略为：


    
	
  • 
		首先访问第一个邻接节点
    • 
	
  • 
		然后以这个 被访问的邻接节点作为初始节点
    • 
	
  • 
		然后循环这个操作。
    • 




	可以这样理解：每次都在访问完 当前节点 后，首先 访问当前节点的第一个邻接节点。



	可以看到：这样的访问策略是 优先往纵向 挖掘深入，而 不是 对一个节点的所有邻接节点进行 横向访问。



	那么显然深度优先搜索是一个 递归过程



	深度优先遍历算法步骤



	基本思想看完，可能还是不清楚是如何遍历的，看看他的遍历步骤：


    
	
  1. 
		
    
			访问初始节点 v，并标记节点 v 为已访问
    
	
    2. 
	
  2. 
		
    
			查找节点 v 的第一个邻接（直连）节点 w
    
	
    3. 
	
  3. 
		
    
			如果节点 w 不存在，则回到第 1 步，然后从 v 的下一个节点继续
    
	
    4. 
	
  4. 
		
    
			如果节点 w 存在：
    
		
      
			
    1. 
				
      
					未被访问过，则对 w 进行深度优先遍历递归（即把 w 当做另一个 v，执行步骤 123）
      
			
      2. 
			
    2. 
				
      
					如果已经被访问过：查找节点 v 的 w 邻接节点的下一个邻接节点，转到步骤 3 
      
			
      3. 
		
    
	
    5. 




	以上图作为例子：添加节点的顺序为 A、B、C、D、E。



	代码实现



	复制代码





	
		

			
				

					 

					
			
				//获取当前元素的第一个邻结点下标,找到就返回其下标，没有找到就返回-1
		

		

			
				

					 

					
			
				private int getFirstNeighbor(int index){
		

		

			
				

					 

					
			
				for(int i = 0; i < numOfEdges; i++){
		

		

			
				

					 

					
			
				if(edge[index][i] > 0){
		

		

			
				

					 

					
			
				return i;
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				return -1;
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				//获取当前元素的第一个邻结点的下一个领结点的下标，没有则返回-1
		

		

			
				

					 

					
			
				//其中index表示要获取谁的下一个邻结点，i表示已经找到的前一个邻结点的下标
		

		

			
				

					 

					
			
				private int getNextNeighbor(int index,int i){
		

		

			
				

					 

					
			
				for(int j = i+1; j < numOfEdges; j++){
		

		

			
				

					 

					
			
				if(edge[index][j] > 0){
		

		

			
				

					 

					
			
				return j;
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				return -1;
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				//图的深度遍历
		

		

			
				

					 

					
			
				private void dfs(boolean[] isVisited,int i){
		

		

			
				

					 

					
			
				//先输出当前节点的信息
		

		

			
				

					 

					
			
				System.out.print(getValueByIndex(i) + "->");
		

		

			
				

					 

					
			
				//将当前节点设置为访问过
		

		

			
				

					 

					
			
				isVisited[i] = true;
		

		

			
				

					 

					
			
				//找当前结点的第一个邻结点
		

		

			
				

					 

					
			
				int w = getFirstNeighbor(i);
		

		

			
				

					 

					
			
				while(w != -1){
		

		

			
				

					 

					
			
				//找到了
		

		

			
				

					 

					
			
				if(!isVisited[w]){
		

		

			
				

					 

					
			
				//没有访问则递归遍历
		

		

			
				

					 

					
			
				dfs(isVisited,w);
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				//如果已经访问过，则查找下一个
		

		

			
				

					 

					
			
				w = getNextNeighbor(i,w);
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				//重载深度遍历，对每一个节点都进行深度遍历
		

		

			
				

					 

					
			
				public void dfs(){
		

		

			
				

					 

					
			
				for(int i = 0; i < numOfEdges; i++){
		

		

			
				

					 

					
			
				if(!isVisited[i]){
		

		

			
				

					 

					
			
				dfs(isVisited,i);
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				}
		

	




	



	图的广度优先遍历



	图的广度优先搜索（DFS，Broad First Search），类似于一个 分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的节点的顺序，以便按这个顺序来访问这些节点的邻接节点。



	算法步骤


    
	
  1. 
		访问初始节点 v ，并标记节点 v 为已访问
    2. 
	
  2. 
		节点 v 入队列
    3. 
	
  3. 
		当队列非空时，继续执行，否则算法结束（仅对 v 的节点算法结束）。
    4. 
	
  4. 
		出队列，取得队头的节点 u
    5. 
	
  5. 
		查找节点 u 的第一个邻接节点 w
    6. 
	
  6. 
		若节点 u 的邻接节点 w 不存在，则跳转到步骤 3；否则执行以下三个步骤：
		
      
			
    1. 
				若节点 w 尚未被访问，则访问节点 w 并标记为已访问
      2. 
			
    2. 
				节点 w 入队列
      3. 
			
    3. 
				查找节点 u 的继 w 邻接节点后的下一个邻接节点 w，转到步骤 6
      4. 
		
    
	
    7. 




	这里可以看到，与深度优先不同的是：


    
	
  • 
		
    
			广度优先：找到第一个邻接节点，访问之后，会继续寻找这个节点的下一个邻接节点（非第一个）
    
	
    • 
	
  • 
		
    
			深度优先：每次只找第一个邻接节点，然后以找到的节点作为基础找它的第一个邻接节点，如果找不到才回溯到上一层，寻找找它的下一个邻接节点（非第一个） 
    
	
    • 




	就如同上图：


    
	
  • 
		左侧的是广度优先，先把 A 能直连的都访问完，再换下一个节点
    • 
	
  • 
		右图是深度优先，每次都只访问第一个直连的节点，然后换节点继续，访问不到，则回退到上一层，找下一个直连节点
    • 




	代码实现



	复制代码





	
		

			
				

					 

					
			
				//图的广度优先
		

		

			
				

					 

					
			
				private void bfs(boolean[] isVisited,int i){
		

		

			
				

					 

					
			
				int u;//队里的头节点
		

		

			
				

					 

					
			
				int w;//当前节点的邻结点
		

		

			
				

					 

					
			
				System.out.print(getValueByIndex(i) + "->");
		

		

			
				

					 

					
			
				isVisited[i] = true;
		

		

			
				

					 

					
			
				//创建一个队列
		

		

			
				

					 

					
			
				LinkedList list = new LinkedList();
		

		

			
				

					 

					
			
				//将当前元素添加到队列尾部
		

		

			
				

					 

					
			
				list.addLast(i);
		

		

			
				

					 

					
			
				while(!list.isEmpty()){
		

		

			
				

					 

					
			
				//从队列头部取出一个数据
		

		

			
				

					 

					
			
				u = (Integer) list.removeFirst();
		

		

			
				

					 

					
			
				w = getFirstNeighbor(u);
		

		

			
				

					 

					
			
				while(w != -1){
		

		

			
				

					 

					
			
				if(!isVisited[w]){
		

		

			
				

					 

					
			
				System.out.print(getValueByIndex(w) + "->");
		

		

			
				

					 

					
			
				isVisited[w] = true;
		

		

			
				

					 

					
			
				list.addLast(w);
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				w = getNextNeighbor(u,w);
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				 
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				public void bfs(){
		

		

			
				

					 

					
			
				for(int i = 0; i < numOfEdges;i++){
		

		

			
				

					 

					
			
				if(!isVisited[i]){
		

		

			
				

					 

					
			
				bfs(isVisited,i);
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				}
		

	




	



	图的深度优先 VS 广度优先



	由于前面讲解的点较少，恰好输出顺序一致，现在来对比下多一点的点。如下图 



	进行代码测试遍历： 



	



	来源：https://www.cnblogs.com/wyzstudy/p/15434064.html



	 


      



  

  
  

   
    
    
   

  

  
 
 

 
 
  
 
 
 
 






 






相关教程