【数据结构与算法11】图

算法 图
数据结构与算法
发布日期:   2022-06-24
更新日期:   2022-06-24
文章字数:   3k
阅读时长:   13 分
阅读次数:  

参考：https://blog.csdn.net/qq_45596525/article/details/110038250

1. 图基本介绍

1.1 为什么要有图？

1）前面我们学了线性表和树
2）线性表局限于一个直接前驱和一个直接后继的关系
3）树也只能有一个直接前驱也就是父节点
4）当我们需要表示多对多的关系时， 这里我们就用到了图

1.2  图的举例说明

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

image-20220614151347689.png

1.3 图的常用概念

1)顶点(vertex)
2)边(edge)
3)路径
4)无向图(右图

image.png

5)有向图

image.png

6)带权图

image.png

2. 图的表示方式

图的表示方式有两种：二维数组表示（邻接矩阵）；链表表示（邻接表）。

2.1 邻接矩阵

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

image.png

2.2 邻接表

  • 邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在,会造成空间的一定损失.
  • 邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表由数组+链表组成

image.png

说明:

  1. 标号为0的结点的相关联的结点为 1 2 3 4
  2. 标号为1的结点的相关联结点为0 4，
  3. 标号为2的结点相关联的结点为 0 4 5
  4. ….

3. 图的快速入门案例

要求: 代码实现下图结构

image.png

思路分析:
(1) 使用 ArrayList 存储顶点String
(2) 边保存在矩阵 int[][] edges
代码实现：

public class GraphDemo {
    //存储顶点的集合
    private ArrayList<String> vertextList;
    //存储图对应的领结矩阵
    private int[][] edges;
    //边的数量
    private int numOfEdges;

    public static void main(String[] args) {
        int n = 5;
        String vertexs[] = {"A","B","C","D","E"};
        GraphDemo graph = new GraphDemo(5);
        for (String vertex : vertexs) {
            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 GraphDemo(int n) {
        this.vertextList = new ArrayList<>(n);
        this.edges = new int[n][n];
        this.numOfEdges = 0;        //这里写不写都可以 默认也是0
    }

    //插入节点
    public void insertVertex(String vertex){
        vertextList.add(vertex);
    }

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

    //返回edges[v2][v1]的权值
    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }

    //返回节点i下标对应的数据
    public String getValueByIndex(int i){
        return vertextList.get(i);
    }

    //显示图对应的矩阵
    public void showGraph(){
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));
        }
    }

    //边的数量
    public int getNumOfEdges(){
        return numOfEdges;
    }
    //节点的数量
    public int getNumOfVertex(){
        return vertextList.size();
    }
}

4. 图的深度优先遍历

4.1 图遍历介绍

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

4.2 深度优先遍历基本思想

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

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

    4.3 深度优先遍历算法步骤

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

看一个具体案例分析:

image.png

代码实现：
需要重点关注的几个方法：getFirstNeighbor，getNextNeighbor，dfs，

public class GraphDemo {
    //存储顶点的集合
    private ArrayList<String> vertextList;
    //存储图对应的领结矩阵
    private int[][] edges;
    //边的数量
    private int numOfEdges;
    //定义数组 记录节点列表中的节点是否被访问
    private boolean[] isVisited;

    public static void main(String[] args) {
        int n = 5;
        String vertexs[] = {"A","B","C","D","E"};
        GraphDemo graph = new GraphDemo(5);
        for (String vertex : vertexs) {
            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();

        graph.dfs();

    }

    /**
     * 初始化
     * @param n 节点个数
     */
    public GraphDemo(int n) {
        this.vertextList = new ArrayList<>(n);
        this.edges = new int[n][n];
        this.numOfEdges = 0;        //这里写不写都可以 默认也是0
        this.isVisited = new boolean[n];
    }

    //插入节点
    public void insertVertex(String vertex){
        vertextList.add(vertex);
    }

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

    //返回edges[v2][v1]的权值
    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }

    //返回节点i下标对应的数据
    public String getValueByIndex(int i){
        return vertextList.get(i);
    }

    //显示图对应的矩阵
    public void showGraph(){
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));
        }
    }

    //边的数量
    public int getNumOfEdges(){
        return numOfEdges;
    }
    //节点的数量
    public int getNumOfVertex(){
        return vertextList.size();
    }

    //得到 vertextList[i] 节点的 第一个领结节点的下标
    public int getFirstNeighbor(int index){
        for (int i = 0; i < vertextList.size(); i++) {
            if(edges[index][i]>0){
                return i;
            }
        }
        return -1;
    }
    //根据前一个邻接节点的下标获取下一个邻接节点
    public int getNextNeighbor(int v1,int v2){
        for (int j = v2 + 1; j < vertextList.size(); j++) {
            if(edges[v1][j] > 0){
                return j;
            }
        }
        return -1;
    }

    //深度优先遍历算法
    //i 第一次就是 0
    private void dfs(boolean[] isVisited,int i){
        //首先输出该节点
        System.out.println(getValueByIndex(i) + "->");
        //该节点置为已访问
        isVisited[i] = true;
        //查找节点i的第一个领结节点w
        int w = getFirstNeighbor(i);
        while (w != -1){
            if(!isVisited[w]){
                dfs(isVisited,w);
            }
            //如果节点w已经访问过了
            w = getNextNeighbor(i,w);
        }
    }

    //对dfs重载，遍历vertexList的所有节点
    public void dfs(){
        for (int i = 0; i < getNumOfVertex(); i++) {
            if(!isVisited[i]){
                dfs(isVisited,i);
            }
        }
    }
}

5. 图的广度优先遍历

5.1 广度优先遍历基本思想

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

5.2 广度优先遍历算法步骤

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

5.3 广度优先举例说明

image.png

关键代码：

//得到 vertextList[i] 节点的 第一个邻接结点的下标
public int getFirstNeighbor(int index){
    for (int i = 0; i < vertextList.size(); i++) {
        if(edges[index][i]>0){
            return i;
        }
    }
    return -1;
}

//根据前一个邻接节点的下标获取下一个邻接节点
public int getNextNeighbor(int v1,int v2){
    for (int j = v2 + 1; j < vertextList.size(); j++) {
        if(edges[v1][j] > 0){
            return j;
        }
    }
    return -1;
}
//对一个结点进行广度优先遍历的方法
private void bfs(boolean[] isVisited,int i){
    int u;  //表示队列的头结点对应的下标
    int w;  //邻接结点
    //队列  ：记录结点的访问顺序
    LinkedList<Integer> queue = new LinkedList<>();
    //输出结点信息
    System.out.print(getValueByIndex(i) + "=>");
    //标记该结点已访问
    isVisited[i] = true;
    //将结点加入队列
    queue.addLast(i);
    while (!queue.isEmpty()){
        //取出队列的头结点
        u = queue.removeFirst();
        //得到第一个邻接结点的下标w
        w = getFirstNeighbor(u);
        while (w != -1){
            //判断得到第一个邻接结点的下标w 是否已经访问过
            if(!isVisited[w]){
                System.out.print(getValueByIndex(w) + "=>");
                //标记该结点已访问
                isVisited[w] = true;
                //将结点加入队列
                queue.addLast(w);
            }
            // u行中  找w后面的下一个邻结点
            w = getNextNeighbor(u,w);
        }
    }
}

public void bfs(){
    isVisited = new boolean[vertextList.size()];
    for (int i = 0; i < getNumOfVertex(); i++) {
        if(!isVisited[i]){
            bfs(isVisited,i);
        }
    }
}

完整代码：

package com.xjt.javase.dataStructure.graph;

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

public class GraphDemo {
    //存储顶点的集合
    private ArrayList<String> vertextList;
    //存储图对应的领结矩阵
    private int[][] edges;
    //边的数量
    private int numOfEdges;
    //定义数组 记录节点列表中的节点是否被访问
    private boolean[] isVisited;

    public static void main(String[] args) {
        int n = 5;
        String vertexs[] = {"A","B","C","D","E"};
        GraphDemo graph = new GraphDemo(5);
        for (String vertex : vertexs) {
            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();
        System.out.println("深度优先遍历---->");
        graph.dfs();

        System.out.println("广度优先遍历===>");
        graph.bfs();

    }

    /**
     * 初始化
     * @param n 节点个数
     */
    public GraphDemo(int n) {
        this.vertextList = new ArrayList<>(n);
        this.edges = new int[n][n];
        this.numOfEdges = 0;        //这里写不写都可以 默认也是0
        this.isVisited = new boolean[n];
    }

    //插入节点
    public void insertVertex(String vertex){
        vertextList.add(vertex);
    }

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

    //返回edges[v2][v1]的权值
    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }

    //返回节点i下标对应的数据
    public String getValueByIndex(int i){
        return vertextList.get(i);
    }

    //显示图对应的矩阵
    public void showGraph(){
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));
        }
    }

    //边的数量
    public int getNumOfEdges(){
        return numOfEdges;
    }
    //节点的数量
    public int getNumOfVertex(){
        return vertextList.size();
    }

    //得到 vertextList[i] 节点的 第一个邻接节点的下标
    public int getFirstNeighbor(int index){
        for (int i = 0; i < vertextList.size(); i++) {
            if(edges[index][i]>0){
                return i;
            }
        }
        return -1;
    }
    //根据前一个邻接节点的下标获取下一个邻接节点
    public int getNextNeighbor(int v1,int v2){
        for (int j = v2 + 1; j < vertextList.size(); j++) {
            if(edges[v1][j] > 0){
                return j;
            }
        }
        return -1;
    }

    //深度优先遍历算法
    //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 = getNextNeighbor(i,w);
        }
    }

    //对dfs重载，遍历vertexList的所有节点
    public void dfs(){
        isVisited = new boolean[vertextList.size()];
        for (int i = 0; i < getNumOfVertex(); i++) {
            if(!isVisited[i]){
                dfs(isVisited,i);
            }
        }
    }

    //对一个结点进行广度优先遍历的方法
    private void bfs(boolean[] isVisited,int i){
        int u;  //表示队列的头结点对应的下标
        int w;  //邻接结点
        //队列  ：记录结点的访问顺序
        LinkedList<Integer> queue = new LinkedList<>();
        //输出结点信息
        System.out.print(getValueByIndex(i) + "=>");
        //标记该结点已访问
        isVisited[i] = true;
        //将结点加入队列
        queue.addLast(i);
        while (!queue.isEmpty()){
            //取出队列的头结点
            u = queue.removeFirst();
            //得到第一个邻接结点的下标w
            w = getFirstNeighbor(u);
            while (w != -1){
                //判断得到第一个邻接结点的下标w 是否已经访问过
                if(!isVisited[w]){
                    System.out.print(getValueByIndex(w) + "=>");
                    //标记该结点已访问
                    isVisited[w] = true;
                    //将结点加入队列
                    queue.addLast(w);
                }
                // u行中  找w后面的下一个邻结点
                w = getNextNeighbor(u,w);
            }
        }
    }

    public void bfs(){
        isVisited = new boolean[vertextList.size()];
        for (int i = 0; i < getNumOfVertex(); i++) {
            if(!isVisited[i]){
                bfs(isVisited,i);
            }
        }
    }
}

6. 深度优先 VS 广度优先

应用实例：

image.png

文章作者: CoderXiong
文章链接: http://bfd2018.github.io/2022/06/24/shu-ju-jie-gou-yu-suan-fa/shu-ju-jie-gou-yu-suan-fa-11-tu/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 CoderXiong !
算法 图
赏
  目录