投稿
  1. 首页
  2. 随笔

数据结构之图（java代码版）

通信工程培训 • 2022-12-14 • 随笔 • 阅读 47

数据结构之图（java代码版）,第1张

数据结构之图（java代码版）

图是一个基本的数据结构

  • 在于理解图和java代码实现
一、图的基本介绍

1、为什么要图

复习一下我们之前学习的东西

  • 线性表和树
  • 线性表局限于只能连接一个前驱节点和一个后继节点
  • 树也只能连接一个直接前驱也就是父节点
  • 当我们需要表示多对多的情况时，这时候就表示两种结构都不能满足的情况（图产生的原因）

2、图的基本概念

图是一种数据结构，其中节点可以具有零个或多个相邻元素。两个节点之间的连接称为边，节点也可以称为顶点。（指不定我们的地图就是用这个来实现的）



3、图的表示方式

  • 1表示它们之间能直接连通
  • 0表示不能直接连通
  • 左边一排表示我们的顶点
  • 右边一排表示和对应节点的连接情况
二、图的图解和代码实现 （1）实现分析

1、题目

2、思路分析

  • 首先得要有一个节点来存放顶点
  • 其次是实现矩阵来进行图的表示
（2）代码实现
  • 先看Graph
  • 最后看主类
package cn;

import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        //测试
        int n = 5;//节点的个数
        String[] vertexs = {"A","B","C","D","E"};
        Graph graph = new Graph(n);
        //循环的添加顶点
        for (String value : vertexs) {
            graph.addVertex(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();
    }
}

class Graph {
    private ArrayList vertexList ;//存储我们顶点的集合
    private int[][] edges;//存储图对应的邻结矩阵
    private int numOfEdges;//表示边的个数


    //构造器
    public Graph() {

    }

    //构造器
    public Graph(int n) {
        edges = new int[n][n];
        vertexList = new ArrayList<>(n);
        numOfEdges = 0;//边不知道是多少，所以默认为0
    }

    
    public void addVertex(String n) {
        vertexList.add(n);
    }

    
    public void insertEdge(int v1,int v2,int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }

    
    public int getNumOfVertex() {
        return vertexList.size();
    }

    
    public int getNumOfEdges() {
        return numOfEdges;
    }

    
    public String getValueByIndex(int x) {
        return vertexList.get(x);
    }

    
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    
    public void showGraph() {
        for(int[] link: edges) {
            System.out.println(Arrays.toString(link));
        }
    }
}
三、图的遍历 1、图的深度优先遍历 （1）概念



  • 先看红色
  • 看橙色
  • 看蓝色
（2）代码实现

代码阅读建议：

  • 首先去看Graph 类的方法八，九，十，十一，其他的不用管
  • 最后看一下测试
package cn;

import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        //测试
        int n = 5;//节点的个数
        String[] vertexs = {"A","B","C","D","E"};
        Graph graph = new Graph(n);
        //循环的添加顶点
        for (String value : vertexs) {
            graph.addVertex(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();

        System.out.println("深度遍历为" );
        graph.dfs();
        
    }
}

class Graph {
    private ArrayList vertexList ;//存储我们顶点的集合
    private int[][] edges;//存储图对应的邻结矩阵
    private int numOfEdges;//表示边的个数
    private boolean [] isVisited;//用于记录某个节点是否被访问

    //构造器
    public Graph() {

    }

    //构造器
    public Graph(int n) {
        edges = new int[n][n];
        vertexList = new ArrayList<>(n);
        numOfEdges = 0;//边不知道是多少，所以默认为0
        isVisited = new boolean[n];
    }

    
    public void addVertex(String n) {
        vertexList.add(n);
    }

    
    public void insertEdge(int v1,int v2,int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }

    
    public int getNumOfVertex() {
        return vertexList.size();
    }

    
    public int getNumOfEdges() {
        return numOfEdges;
    }

    
    public String getValueByIndex(int x) {
        return vertexList.get(x);
    }

    
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    
    public void showGraph() {
        for(int[] link: edges) {
            System.out.println(Arrays.toString(link));
        }
    }

    
    public int getFirstNeighbor(int index) {
        //进行遍历
        for (int i = 0; i < vertexList.size(); i++) {
            if (edges[index][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    
    public int getNextNeighbor(int v1,int v2) {
        for (int i = v2 + 1; i < vertexList.size(); i++) {
            if (edges[v1][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    
    public void dfs(boolean[] isVisited,int i) {
        //1、调用这个方法，说明进入了步骤中的第一步
        System.out.print(getValueByIndex(i) + "->" );
            //将该节点设置为已经访问
        isVisited[i] = true;
        //2、查找节点i的第一个相邻节点w
        int w = getFirstNeighbor(i);
        while (w != -1) {//说明有邻接节点
            //4、要判断是否被访问过，如果没有被访问过
            if (!isVisited[w]) {
                //递归进行访问
                dfs(isVisited,w);
            }
            //5、如果没有被访问过，则去找w的下一个节点
            w = getNextNeighbor(i,w);
        }

    }

    
    public void dfs() {
        //遍历所有的节点，进行dfs[回溯]
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]) {
                dfs(isVisited,i);
            }
        }
    }

}
2、图的广度优先遍历 （1）概念

1、基本思想

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

2、基本步骤

  • 访问初始节点v并标记节点v为已访问。
  • 节点v入队列
  • 当队列非空时，继续执行，否则算法结束【就是对v的第一次算法结束】
  • 出队列，取得队头节点u
  • 查找节点u的第一个相邻节点w
  • 若节点u的相邻节点w不存在，则转到步骤3，否则循环执行以下三个步骤
    • 若节点w尚未被访问，则访问节点w并标记为已访问。
    • 节点w入队列
    • 查找节点u的继w相邻节点后的下一个邻接节点w，转到步骤6

3、是这样的一个过程

（2）代码实现 
public class Main {
    public static void main(String[] args) {
        //测试
        int n = 5;//节点的个数
        String[] vertexs = {"A","B","C","D","E"};
        Graph graph = new Graph(n);
        //循环的添加顶点
        for (String value : vertexs) {
            graph.addVertex(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();

        


        System.out.println("广度优先");
        graph.bfs();
    }
}

class Graph {
    private ArrayList vertexList ;//存储我们顶点的集合
    private int[][] edges;//存储图对应的邻结矩阵
    private int numOfEdges;//表示边的个数
    private boolean [] isVisited;//用于记录某个节点是否被访问

    //构造器
    public Graph() {

    }

    //构造器
    public Graph(int n) {
        edges = new int[n][n];
        vertexList = new ArrayList<>(n);
        numOfEdges = 0;//边不知道是多少，所以默认为0
        isVisited = new boolean[n];
    }

    
    public void addVertex(String n) {
        vertexList.add(n);
    }

    
    public void insertEdge(int v1,int v2,int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }

    
    public int getNumOfVertex() {
        return vertexList.size();
    }

    
    public int getNumOfEdges() {
        return numOfEdges;
    }

    
    public String getValueByIndex(int x) {
        return vertexList.get(x);
    }

    
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    
    public void showGraph() {
        for(int[] link: edges) {
            System.out.println(Arrays.toString(link));
        }
    }

    
    public int getFirstNeighbor(int index) {
        //进行遍历
        for (int i = 0; i < vertexList.size(); i++) {
            if (edges[index][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    
    public int getNextNeighbor(int v1,int v2) {
        for (int i = v2 + 1; i < vertexList.size(); i++) {
            if (edges[v1][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    
    public void dfs(boolean[] isVisited,int i) {
        //1、调用这个方法，说明进入了步骤中的第一步
        System.out.print(getValueByIndex(i) + "->" );
            //将该节点设置为已经访问
        isVisited[i] = true;
        //2、查找节点i的第一个相邻节点w
        int w = getFirstNeighbor(i);
        while (w != -1) {//说明有邻接节点
            //4、要判断是否被访问过，如果没有被访问过
            if (!isVisited[w]) {
                //递归进行访问
                dfs(isVisited,w);
            }
            //5、如果没有被访问过，则去找w的下一个节点
            w = getNextNeighbor(i,w);
        }

    }

    
    public void dfs() {
        //遍历所有的节点，进行dfs[回溯]
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]) {
                dfs(isVisited,i);
            }
        }
    }


    
    public void bfs(boolean[] isVisited,int i) {
        int u;//表示队列的头节点对应的下标
        int w;//整个过程会去找的，邻接的节点w
        //队列，节点访问的顺序
        linkedList queue = new linkedList<>();
        //1、访问节点
        System.out.println(getValueByIndex(i) + "->");
            //标记为已访问
        isVisited[i] = true;
        //2、加入队列
        queue.addLast(i);
        //3、只要队列不为空，
        while (!queue.isEmpty()) {
            //就取出队列的头节点的下标
            u = (Integer)queue.removeFirst();
            //取出第一个邻节点的下标w
            w = getFirstNeighbor(u);
            while (w != -1) {//说明你找到了，
                //如果没有访问
                if (!isVisited[w]) {
                    System.out.println(getValueByIndex(w) + "->");
                    isVisited[w] =true;
                    //入队列
                    queue.addLast(w);
                }
                //如果访问过了,以u为前驱节点，找w后面的第一个节点下一个邻节点
                w = getNextNeighbor(u,w);
            }
        }

    }

    //方法十三：重载一下十二方法
    public void bfs() {
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]) {//如果没有访问过
                bfs(isVisited,i);
            }
        }
    }

}
 
（3）留点问题 

1、在测试的时候我们是不能同时测试的
 原因是当我们深度遍历后，会把用于判断的数组全部置为true，所以全部不会输出。
 

2、解决办法是从新设计
 在我们的构造方法不能直接赋值我们的用于判断的boolean数组。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5583026.html

					

				
								

										
										
										
										
										
									

								

					
						
							
						 赞
						(0)
					
					

						
							 打赏
						
							
								微信扫一扫 微信扫一扫
							
							
								支付宝扫一扫 支付宝扫一扫
							
						
					

				

				

					

						

							
								通信工程培训
								通信工程培训
								一级用户组
							
						

						

							

								
									
										
									
									0
								
								
									
										
									
									0
								
							

							
							

								
									
										
									
								
							

						

					

				

			
			
            

            	            

            
			

								

					
					

         				
							
								
							 上一篇
						
						2022-12-15
					

				

												

					
					

         				
							下一篇 
           						
							
						
						2022-12-14
					

				

							


			
			

				

					

						发表评论
					

										

						
						

							

								登录后才能评论
							

							
						

					

									

								
 评论列表（0条）

				
    
									

				
											

		

	

	





	


	

		

			

			

				
				

					

						Copyright © 2022 内存溢出 版权所有
						
							湘ICP备2022025235号						
						Powered by
						
							outofmemory.cn
						
					
					

				

			

			

				

					
					
						
						
					
					
						
					
				

			

		

	




























    
    

    

        
            保存