十三、图

13.1 、图基本介绍

13.1.1 、为什么要有图

1) 前面我们学了线性表和树

2) 线性表局限于一个直接前驱和一个直接后继的关系

3) 树也只能有一个直接前驱也就是父节点

4) 当我们需要表示多对多的关系时，这里我们就用到了图。

13.1.2、图的举例说明

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

13.1.3 、图的常用概念

1) 顶点(vertex)

2) 边(edge)

3) 路径

4) 无向图(右图）

5) 有向图

6) 带权图

13.2 、图的表示方式

图的表示方式有两种：

二维数组表示（邻接矩阵）；链表表示（邻接表）

13.2.1 、邻接矩阵

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

13.2.2 、邻接表

1) 邻接矩阵需要为每个顶点都分配 n 个边的空间，其实有很多边都是不存在,会造成空间的一定损失.

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

3) 举例说明

13.3 、图的快速入门案例

1) 要求: 代码实现如下图结构

2) 思路分析

(1) 存储顶点 String 使用 ArrayList
(2) 保存矩阵 int [ ] [ ] edges

3) 代码实现

/**
 * description
 * 数据结构——图的快速入门案例
 *
 * @author xujicheng
 * @since 2022年12月10日 13:11
 */
public class Graph {

    private ArrayList<String> vertexList;  //存储顶点的集合

    private int[][] edges;  //存储图对应的邻接矩阵

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

    public static void main(String[] args) {
        //测试图是否创建完成
        int n = 5;  //节点的个数
        String[] Vertex = {"A", "B", "C", "D", "E"};
        //创建图对象
        Graph graph = new Graph(n);
        //循环的添加顶点
        for(String vertex : Vertex){
            graph.insertVertex(vertex);
        }
        //添加边 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();
    }

    /**
     * 构造器，用于初始化对象
     *
     * @param n 表示顶点的个数
     */
    public Graph(int n) {
        //初始化矩阵和vertexList
        edges = new int[n][n];
        vertexList = new ArrayList<String>(n);
        numOfEdges = 0;
    }

    /**
     * 数据结构——图中常用的方法——返回节点的个数
     *
     * @return 返回vertexList中节点的总树
     */
    public int getNumOfVertex() {
        return vertexList.size();
    }

    /**
     * 得到边的数目
     *
     * @return 返回边的总数
     */
    public int getNumOfEdges() {
        return numOfEdges;
    }

    /**
     * 返回节点i(下标)对应的数据"0" -> "A" ,"1" -> "B"
     *
     * @param i 节点对应的下标
     * @return 返回下标对应的数据
     */
    public String getValueByIndex(int i) {
        return vertexList.get(i);
    }

    //显示矩阵的方法
    public void showGraph() {
        for (int[] link : edges) {
            System.out.println(Arrays.toString(link));
        }
    }

    /**
     * 返回v1和v2的权值
     *
     * @param v1 顶点的下标
     * @param v2 另一个顶点的下标
     * @return 顶点的权值
     */
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    /**
     * 插入顶点的方法
     *
     * @param vertex 需要插入的顶点
     */
    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }

    /**
     * 添加边的方法
     *
     * @param v1     表示第一个顶点的下标，即是第几个顶点
     * @param v2     表示第二个顶点的下标
     * @param weight 矩阵边对应的值，要么是0要么是1，默认值为0
     */
    public void insertEdge(int v1, int v2, int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }
}

13.4 、图的深度优先遍历介绍

13.4.1 、图遍历介绍

所谓图的遍历，即是对结点的访问。一个图有那么多个结点，如何遍历这些结点，需要特定策略，一般有两种访问策略:

(1)深度优先遍历

(2)广度优先遍历

13.4.2 、深度优先遍历基本思想

图的深度优先搜索(Depth First Search) 。

1) 深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点，可以这样理解：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
2) 我们可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。
3) 显然，深度优先搜索是一个递归的过程

13.4.3 、深度优先遍历算法步骤

1) 访问初始结点 v，并标记结点 v 为已访问。

2) 查找结点 v 的第一个邻接结点 w。

3) 若 w 存在，则继续执行 4，如果 w 不存在，则回到第 1 步，将从 v 的下一个结点继续。

4) 若 w 未被访问，对 w 进行深度优先遍历递归（即把 w 当做另一个 v，然后进行步骤123）。

5) 查找结点 v 的 w 邻接结点的下一个邻接结点，转到步骤 3。

6) 分析图

13.4.4 、深度优先算法的代码实现

    只加入核心方法，测试部分和其他无关紧要的代码不写入，后面有汇总
    /**
     * 得到第一个邻接节点的下标w
     *
     * @param index 当前节点的下标
     * @return 如果存在返回当前节点的第一个邻接节点的下标，否则返回-1
     */
    public int getFirstNeighbor(int index) {
        for (int j = 0; j < vertexList.size(); j++) {
            if (edges[index][j] > 0) {
                return j;
            }
        }
        return -1;
    }

    /**
     * 根据前一个邻接节点的下标来获取下一个邻接节点
     *
     * @param v1 前一个邻接节点的下标
     * @param v2 当前邻接节点
     * @return 如果存在返回当前邻接节点的下一个邻接节点的下标，否则返回-1
     */
    public int getNextNeighbor(int v1, int v2) {
        for (int j = v2 + 1; j < vertexList.size(); j++) {
            if (edges[v1][j] > 0) {
                return j;
            }
        }
        return -1;
    }

    //对dfs方法进行一个重载,遍历我们所有的节点，并进行dfs
    public void dfs() {
        isVisited = new boolean[vertexList.size()];
        //遍历所有的节点，进行dfs[回溯]
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]) {   //增加节点是否被访问的逻辑提高遍历效率
                dfs(isVisited, i);
            }
        }
    }

    /**
     * 深度优先遍历算法
     *
     * @param isVisited 记录某个节点是否被访问
     * @param i         是节点的初始下标，第一次是0
     */
    private void dfs(boolean[] isVisited, int i) {
        //首先访问该节点(输出)
        System.out.print(getValueByIndex(i) + "-->");
        //访问后将该节点设置成已访问
        isVisited[i] = true;
        //查找节点i的第一个邻接点w
        int w = getFirstNeighbor(i);
        while (w != -1) {  //说明有邻接点
            //还需要判断当前节点是否被访问过
            if (!isVisited[w]) {
                dfs(isVisited, w);
            }
            //如果w这个节点已经被访问，就去查找w的邻接点的下一个邻接节点
            w = getNextNeighbor(i, w);
        }
    }

13.5 、图的广度优先遍历

13.5.1 、广度优先遍历基本思想

1) 图的广度优先搜索(Broad First Search) 。

2) 类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点

13.5.2 、广度优先遍历算法步骤

1) 访问初始结点 v 并标记结点 v 为已访问。

2) 结点 v 入队列

3) 当队列非空时，继续执行，否则算法结束。

4) 出队列，取得队头结点 u。

5) 查找结点 u 的第一个邻接结点 w。

6) 若结点 u 的邻接结点 w 不存在，则转到步骤 3；否则循环执行以下三个步骤：

6.1 若结点 w 尚未被访问，则访问结点 w 并标记为已访问。
6.2 结点 w 入队列
6.3 查找结点 u 的继 w 邻接结点后的下一个邻接结点 w，转到步骤 6。

13.5.3 、广度优先算法的图示

13.6、广度优先算法的代码实现

    /**
     * 广度优先遍历算法——以一个节点而言
     *
     * @param isVisited 记录某个节点是否被访问
     * @param i         是节点的初始下标，第一次是0
     */
    private void bfs(boolean[] isVisited, int i) {
        int u;  //表示队列的头节点对应的下标
        int w;  //表示邻接节点的下标
        //需要队列来记录节点访问的顺序
        LinkedList<Integer> queue = new LinkedList<Integer>();
        //访问这个节点(即输出这个节点的信息)
        System.out.print(getValueByIndex(i) + "-->");
        //访问后把此节点标记为已访问
        isVisited[i] = true;
        //将节点加入队列,根据队列的特点，加入节点是从尾部加，取出是从头部取
        queue.addLast(i);
        //只要队列不为空，继续执行，否则算法结束
        while (!queue.isEmpty()) {
            //取出队列的头节点下标
            u = queue.removeFirst();
            //得到第一个邻接点的下标w
            w = getFirstNeighbor(u);
            //判断w是否存在
            while (w != -1) {  //存在
                //判断节点是否被访问过
                if (!isVisited[w]) {  //未访问
                    //未访问，访问节点w
                    System.out.print(getValueByIndex(w) + "-->");
                    //标记为已访问
                    isVisited[w] = true;
                    //访问后入队列，记录访问顺序
                    queue.addLast(w);
                }
                //以u为起点，找w后面的后的下一个邻接点,即w被访问，还以u为起点继续向下访问
                w = getNextNeighbor(u, w);   //体现出广度优先
            }
        }
    }

    //遍历所有的节点，都进行广度优先搜索,对广度优先的方法进行重载
    public void bfs() {
        isVisited = new boolean[5];
        for (int i = 0; i < getNumOfVertex(); i++) {
            //增加判断是否访问过，以此增加遍历的效率
            if (!isVisited[i]) {
                bfs(isVisited, i);
            }
        }
    }

13.7 、图的代码汇总

/**
 * description
 * 数据结构——图的快速入门案例
 *
 * @author xujicheng
 * @since 2022年12月10日 13:11
 */
public class Graph {

    private ArrayList<String> vertexList;  //存储顶点的集合

    private int[][] edges;  //存储图对应的邻接矩阵

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

    //定义个数组boolean[]，记录某个节点是否被访问
    private boolean[] isVisited;

    public static void main(String[] args) {
        //测试图是否创建完成
        int n = 5;  //节点的个数
        String[] Vertex = {"A", "B", "C", "D", "E"};
        //创建图对象
        Graph graph = new Graph(n);
        //循环的添加顶点
        for (String vertex : Vertex) {
            graph.insertVertex(vertex);
        }
        //添加边 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();

        //测试dfs遍历是否正常
        System.out.println("深度遍历");
        graph.dfs();

        System.out.println(); //换行
        System.out.println("广度优先遍历");
        graph.bfs();
    }

    /**
     * 构造器，用于初始化对象
     *
     * @param n 表示顶点的个数
     */
    public Graph(int n) {
        //初始化矩阵和vertexList
        edges = new int[n][n];
        vertexList = new ArrayList<String>(n);
        numOfEdges = 0;
    }

    /**
     * 得到第一个邻接节点的下标w
     *
     * @param index 当前节点的下标
     * @return 如果存在返回当前节点的第一个邻接节点的下标，否则返回-1
     */
    public int getFirstNeighbor(int index) {
        for (int j = 0; j < vertexList.size(); j++) {
            if (edges[index][j] > 0) {
                return j;
            }
        }
        return -1;
    }

    /**
     * 根据前一个邻接节点的下标来获取下一个邻接节点
     *
     * @param v1 前一个节点的下标
     * @param v2 下一个邻接节点
     * @return 如果存在返回当前邻接节点的下一个邻接节点的下标，否则返回-1
     */
    public int getNextNeighbor(int v1, int v2) {
        for (int j = v2 + 1; j < vertexList.size(); j++) {
            if (edges[v1][j] > 0) {
                return j;
            }
        }
        return -1;
    }

    //对dfs方法进行一个重载,遍历我们所有的节点，并进行dfs
    public void dfs() {
        isVisited = new boolean[vertexList.size()];
        //遍历所有的节点，进行dfs[回溯]
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]) {   //增加节点是否被访问的逻辑提高遍历效率
                dfs(isVisited, i);
            }
        }
    }

    /**
     * 深度优先遍历算法
     *
     * @param isVisited 记录某个节点是否被访问
     * @param i         是节点的初始下标，第一次是0
     */
    private void dfs(boolean[] isVisited, int i) {
        //首先访问该节点(输出)
        System.out.print(getValueByIndex(i) + "-->");
        //访问后将该节点设置成已访问
        isVisited[i] = true;
        //查找节点i的第一个邻接点w
        int w = getFirstNeighbor(i);
        while (w != -1) {  //说明有邻接点
            //还需要判断当前节点是否被访问过
            if (!isVisited[w]) {
                dfs(isVisited, w);
            }
            //如果w这个节点已经被访问，就去查找w的邻接点的下一个邻接节点
            w = getNextNeighbor(i, w);
        }
    }

    /**
     * 广度优先遍历算法——以一个节点而言
     *
     * @param isVisited 记录某个节点是否被访问
     * @param i         是节点的初始下标，第一次是0
     */
    private void bfs(boolean[] isVisited, int i) {
        int u;  //表示队列的头节点对应的下标
        int w;  //表示邻接节点的下标
        //需要队列来记录节点访问的顺序
        LinkedList<Integer> queue = new LinkedList<Integer>();
        //访问这个节点(即输出这个节点的信息)
        System.out.print(getValueByIndex(i) + "-->");
        //访问后把此节点标记为已访问
        isVisited[i] = true;
        //将节点加入队列,根据队列的特点，加入节点是从尾部加，取出是从头部取
        queue.addLast(i);
        //只要队列不为空，继续执行，否则算法结束
        while (!queue.isEmpty()) {
            //取出队列的头节点下标
            u = queue.removeFirst();
            //得到第一个邻接点的下标w
            w = getFirstNeighbor(u);
            //判断w是否存在
            while (w != -1) {  //存在
                //判断节点是否被访问过
                if (!isVisited[w]) {  //未访问
                    //未访问，访问节点w
                    System.out.print(getValueByIndex(w) + "-->");
                    //标记为已访问
                    isVisited[w] = true;
                    //访问后入队列，记录访问顺序
                    queue.addLast(w);
                }
                //以u为起点，找w后面的后的下一个邻接点,即w被访问，还以u为起点继续向下访问
                w = getNextNeighbor(u, w);   //体现出广度优先
            }
        }
    }

    //遍历所有的节点，都进行广度优先搜索,对广度优先的方法进行重载
    public void bfs() {
        isVisited = new boolean[5];
        for (int i = 0; i < getNumOfVertex(); i++) {
            //增加判断是否访问过，以此增加遍历的效率
            if (!isVisited[i]) {
                bfs(isVisited, i);
            }
        }
    }

    /**
     * 数据结构——图中常用的方法——返回节点的个数
     *
     * @return 返回vertexList中节点的总树
     */
    public int getNumOfVertex() {
        return vertexList.size();
    }

    /**
     * 得到边的数目
     *
     * @return 返回边的总数
     */
    public int getNumOfEdges() {
        return numOfEdges;
    }

    /**
     * 返回节点i(下标)对应的数据"0" -> "A" ,"1" -> "B"
     *
     * @param i 节点对应的下标
     * @return 返回下标对应的数据
     */
    public String getValueByIndex(int i) {
        return vertexList.get(i);
    }

    //显示矩阵的方法
    public void showGraph() {
        for (int[] link : edges) {
            System.out.println(Arrays.toString(link));
        }
    }

    /**
     * 返回v1和v2的权值
     *
     * @param v1 顶点的下标
     * @param v2 另一个顶点的下标
     * @return 顶点的权值
     */
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    /**
     * 插入顶点的方法
     *
     * @param vertex 需要插入的顶点
     */
    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }

    /**
     * 添加边的方法
     *
     * @param v1     表示第一个顶点的下标，即是第几个顶点
     * @param v2     表示第二个顶点的下标
     * @param weight 矩阵边对应的值，要么是0要么是1，默认值为0
     */
    public void insertEdge(int v1, int v2, int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }
}

数据结构的学习笔记（第十二部分）

十三、图

13.1 、图基本介绍

13.1.1 、为什么要有图

13.1.2、图的举例说明

13.1.3 、图的常用概念

13.2 、图的表示方式

13.2.1 、邻接矩阵

13.2.2 、邻接表

13.3 、图的快速入门案例

13.4 、图的深度优先遍历介绍

13.4.1 、图遍历介绍

13.4.2 、深度优先遍历基本思想

13.4.3 、深度优先遍历算法步骤

13.4.4 、深度优先算法的代码实现

13.5 、图的广度优先遍历

13.5.1 、广度优先遍历基本思想

13.5.2 、广度优先遍历算法步骤

13.5.3 、广度优先算法的图示

13.6、广度优先算法的代码实现

13.7 、图的代码汇总

13.8 、图的深度优先 VS 广度优先

热门文章

最新文章

相关课程

相关电子书

数据结构的学习笔记（第十二部分）

十三、图

13.1 、图基本介绍

13.1.1 、为什么要有图

13.1.2、 图的举例说明

13.1.3 、图的常用概念

13.2 、图的表示方式

13.2.1 、邻接矩阵

13.2.2 、邻接表

13.3 、图的快速入门案例

13.4 、图的深度优先遍历介绍

13.4.1 、图遍历介绍

13.4.2 、深度优先遍历基本思想

13.4.3 、深度优先遍历算法步骤

13.4.4 、深度优先算法的代码实现

13.5 、图的广度优先遍历

13.5.1 、广度优先遍历基本思想

13.5.2 、广度优先遍历算法步骤

13.5.3 、广度优先算法的图示

13.6、 广度优先算法的代码实现

13.7 、图的代码汇总

13.8 、图的深度优先 VS 广度优先

热门文章

最新文章

相关课程

相关电子书

13.1.2、图的举例说明

13.6、广度优先算法的代码实现