一、图的基本介绍

1、为什么要有图

QQ截图20200902150009.jpg

2、图的举例说明

图是一种数据结构，其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为
顶点。如图：
QQ截图20200902150125.jpg

3、图的常用概念

QQ截图20200902150202.jpg

4、图的表现方式

邻接矩阵

QQ截图20200902150258.jpg

邻接表

QQ截图20200902150306.jpg

5、代码实现(邻接矩阵)

QQ截图20200903120931.jpg
依据上图进行插入各个节点以及边。
属性有三个组成：vertexs(用来存储节点名称，集合存储)、edges(用来存储邻接矩阵，二维数组)、numOfEdge(用来存储两节点相连的实际边数，int型)
主要方法有三个：构造方法(根据输入节点个数来为三个属性进行赋初值)、插入节点名称(集合插入)、插入邻接矩阵中两点连线的权值
其他常用普遍方法：

  1. package graph;
  3. import java.util.ArrayList;
  4. import java.util.Arrays;
  6. public class Graph {
  8.     public static void main(String[] args) {
  9.         Graph graph = new Graph(5);
  10.         String[] vertexName = {"A","B","C","D","E"};
  11.         //插入节点名称
  12.         for(String vertex:vertexName) {
  13.             graph.insertVertex(vertex);
  14.         }
  16.         //插入各自节点的权值
  17.         //A-B A-C B-C B-D B-E
  18.         graph.insertEdge(0, 1, 1);
  19.         graph.insertEdge(0,2,1);
  20.         graph.insertEdge(1,2,1);
  21.         graph.insertEdge(1,3,1);
  22.         graph.insertEdge(1,4,1);
  24.         graph.showGraph();
  25.     }
  27.     private ArrayList<String> vertexs;//用来存储节点的
  28.     private int[][] edges;//存储图对应的邻接矩阵
  29.     private int numOfEdge;//用来存储边的数量
  31.     //构造函数，用来对属性进行初始化
  32.     public Graph(int n) {
  33.         edges = new int[n][n];//邻接矩阵进行初始化
  34.         vertexs = new ArrayList<>(n);//开辟指定空间的集合
  35.         numOfEdge = 0;//边的数目暂时不确定
  36.     }
  38.     //其他普遍常用的方法*************
  39.     //获取边数
  40.     public int getNumOfEdge(){
  41.         return numOfEdge;
  42.     }
  44.     //获取指定下标的对应类型名称
  45.     public String getValueByIndex(int i) {
  46.         return vertexs.get(i);
  47.     }
  49.     //获取两点之间的权值
  50.     public int getWeight(int v1,int v2) {
  51.         return edges[v1][v2];    
  52.     }
  54.     //显示图对应的矩阵
  55.     public void showGraph() {
  56.         for(int[] link:edges) {
  57.             System.out.println(Arrays.toString(link));
  58.         }
  59.     }
  60.     //其他普遍常用的方法*************
  62.     //插入节点
  63.     public void insertVertex(String vertex) {
  64.         vertexs.add(vertex);//来进行插入到list集合中
  65.     }
  67.     //插入边
  68.     public void insertEdge(int v1,int v2,int weight) {
  69.         edges[v1][v2] = weight;
  70.         edges[v2][v1] = weight;
  71.         numOfEdge++;
  72.     }
  75. }

运行结果：
QQ截图20200903142140.jpg

二、图的遍历

所谓图的遍历，即是对结点的访问。一个图有那么多个结点，如何遍历这些结点，需要特定策略，一般有两种 访问策略:(1)深度优先遍历 (2)广度优先遍历

1、深度优先遍历(dfs)

源代码：Graph.java

基本思想以及算法步骤

QQ截图20200904121437.jpg
算法步骤
QQ截图20200904121521.jpg

代码实现以及思路

QQ截图20200903154107.jpg

进行深搜需要有两个辅助方法：都很简单只不过就是遍历看是否大于1返回对应下标
① 获取当前节点位置行中第一个相连接的节点 —》 getFirstConnectNode
② 获取到当前节点位置中对应位置节点之后的一个节点 —》getNextConnectNode
下面dfs方法分成两部分，实际上可以直接分成一部分，只不过更加区分好理解而已。

  1. package graph;
  3. import java.util.ArrayList;
  4. import java.util.Arrays;
  6. public class Graph {
  7.     private ArrayList<String> vertexs;//用来存储节点的
  8.     private int[][] edges;//存储图对应的邻接矩阵
  9.     private int numOfEdge;//用来存储边的数量
  10.     private boolean[] isVisible;//用来判断该点是否已经访问过了
  13.     //构造函数，用来对属性进行初始化
  14.     public Graph(int n) {
  15.         edges = new int[n][n];//邻接矩阵进行初始化
  16.         vertexs = new ArrayList<>(n);//开辟指定空间的集合
  17.         numOfEdge = 0;//边的数目暂时不确定
  18.         isVisible = new boolean[n];//默认都是false
  19.     }
  21.     //dfs算法相关******************
  22.     //辅助方法1：获取对应节点中第一个连接的节点
  23.     public int getFirstConnectNode(int w) {
  24.         for(int i = 0;i<vertexs.size();i++) {
  25.             if(edges[w][i]>0) {
  26.                 return i;//返回第一个连接的节点位置
  27.             }
  28.         }
  29.         return -1;//没有的话就返回-1;
  30.     }
  31.     //辅助方法2：获取对应节点中的下一个节点,需要传入两个值一个是当前节点，另一个是当前节点这行中的位置
  32.     public int getNextConnectNode(int w1,int w2) {
  33.         for(int i = w2+1;i<vertexs.size();i++) {
  34.             //找到w2节点之后的进行返回对应位置
  35.             if(edges[w1][i]>0) {
  36.                 return i;
  37.             }
  38.         }
  39.         return -1;
  40.     }
  42.     //开始写dfs算法
  43.     private void dfs(int n) {
  44.         //获取当前访问的节点
  45.         System.out.printf(vertexs.get(n)+"->");
  46.         //当前节点已经被访问
  47.         isVisible[n] = true;
  48.         //获取到对应节点连接的第一个节点
  49.         int w = getFirstConnectNode(n);
  50.         while(w != -1) {
  51.             if(!isVisible[w]) {
  52.                 dfs(w);
  53.             }
  54.             w = getNextConnectNode(n, w);//当前节点为n，对应位置节点为w
  55.         }
  56.     }
  57.     //这里写一个外部，涉及到所有可能性
  58.     public void dfs() {
  59.         //对每个边都进行搜查，而不是只是一个节点不断往下搜查
  60.         for(int i=0;i<vertexs.size();i++) {
  61.             if(!isVisible[i]) {
  62.                 dfs(i);
  63.             }
  64.         }
  65.     }
  66.     //dfs算法相关******************
  67.     ....其他方法可见上面图的代码实现
  68. }

测试方法：

  1. package graph;
  3. import java.util.ArrayList;
  4. import java.util.Arrays;
  6. public class Graph {
  8.     public static void main(String[] args) {
  9.         Graph graph = new Graph(5);
  10.         String[] vertexName = {"A","B","C","D","E"};
  11.         //插入节点名称
  12.         for(String vertex:vertexName) {
  13.             graph.insertVertex(vertex);
  14.         }
  16.         //插入各自节点的权值
  17.         //A-B A-C B-C B-D B-E
  18.         graph.insertEdge(0, 1, 1);
  19.         graph.insertEdge(0,2,1);
  20.         graph.insertEdge(1,2,1);
  21.         graph.insertEdge(1,3,1);
  22.         graph.insertEdge(1,4,1);
  24.         //展示矩形图
  25.         graph.showGraph();
  27.         //进行深搜遍历
  28.         graph.dfs();
  29.     }
  30. }

运行结果：
QQ截图20200903154245.jpg

2、广度优先遍历(BFS)

源代码：Graph.java

基本思想以及算法步骤

QQ截图20200904121614.jpg
算法步骤
QQ截图20200904121643.jpg
QQ截图20200904121648.jpg

代码实现

QQ截图20200904121740.jpg

  1.     //辅助方法1：获取对应节点中第一个连接的节点
  2.     public int getFirstConnectNode(int w) {
  3.         for(int i = 0;i<vertexs.size();i++) {
  4.             if(edges[w][i]>0) {
  5.                 return i;//返回第一个连接的节点位置
  6.             }
  7.         }
  8.         return -1;//没有的话就返回-1;
  9.     }
  10.     //辅助方法2：获取对应节点中的下一个节点,需要传入两个值一个是当前节点，另一个是当前节点这行中的位置
  11.     public int getNextConnectNode(int w1,int w2) {
  12.         for(int i = w2+1;i<vertexs.size();i++) {
  13.             //找到w2节点之后的进行返回对应位置
  14.             if(edges[w1][i]>0) {
  15.                 return i;
  16.             }
  17.         }
  18.         return -1;
  19.     }    
  20.     //开始写bfs算法
  21.     public void bfs(int n) {
  22.         int u;//设置为队列的头节点对应下标
  23.         int w;//邻接节点
  24.         System.out.print(vertexs.get(n)+"=>");
  25.         //创建一个队列
  26.         LinkedList<Integer> list = new LinkedList<>();
  27.         //设置对应节点已经访问过
  28.         isVisible[n] = true;
  29.         list.addLast(n);//将首先这个节点放置最后
  30.         //1、队列不为空为判断情况  这里相当于将每一行的放置在队列中依次取出
  31.         while(!list.isEmpty()) {
  32.             u = list.removeFirst();//取出队列中的第一个节点并获取下标
  33.             //2、得到第一个邻接节点的下标w 这里相当于遍历头节点行进行打印以及放置队列
  34.             w = getFirstConnectNode(u);
  35.             while(w != -1) {
  36.                 if(!isVisible[w]) {
  37.                     System.out.print(vertexs.get(w)+"=>");
  38.                     isVisible[w] = true;
  39.                     list.addLast(w);//将该节点添加到队列中
  40.                 }
  41.                 w = getNextConnectNode(u, w);//继续获取头节点对应下一节点的位置
  42.             }
  44.         }
  45.     }
  47.     //对所有情况进行遍历
  48.     public void bfs() {
  49.         for(int i = 0;i<vertexs.size();i++) {
  50.             if(!isVisible[i]) {
  51.                 bfs(i);
  52.             }
  53.         }
  54.     }


测试代码：**

  1. package graph;
  3. import java.util.ArrayList;
  4. import java.util.Arrays;
  5. import java.util.LinkedList;
  7. public class Graph {
  9.     public static void main(String[] args) {
  10.         Graph graph = new Graph(5);
  11.         String[] vertexName = {"A","B","C","D","E"};
  12.         //插入节点名称
  13.         for(String vertex:vertexName) {
  14.             graph.insertVertex(vertex);
  15.         }
  17.         //插入各自节点的权值
  18.         //A-B A-C B-C B-D B-E
  19.         graph.insertEdge(0, 1, 1);
  20.         graph.insertEdge(0,2,1);
  21.         graph.insertEdge(1,2,1);
  22.         graph.insertEdge(1,3,1);
  23.         graph.insertEdge(1,4,1);
  25.         //展示矩形图
  26.         graph.showGraph();
  28.         //进行深搜遍历
  29.         //graph.dfs();
  31.         //进行广搜遍历
  32.         graph.bfs();
  33.     }
  34. }

运行结果：
QQ截图20200904122021.jpg

图的深度优先 VS 广度优先

QQ截图20200904175303.jpg

整理者：长路 时间：2020/9/2-2020/9/4