图Graph

1. 图的基本介绍

1.1 为什么要有图

众所周知，数据结构中已经有线性表和树结构，但是线性表局限于一个直接前驱和一个直接后继的关系（eg.链表），树也只能有一个直接前驱（即父节点），当我们需要表示多对多的关系时，就需要用到图这个数据结构。

1.2 举例说明

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

1.3 图的相关概念

• 顶点（vertex）：上图中的{A,B,C,D,E}是该图的顶点集；

• 边（edge）：上图中顶点A和B之间的连接就是该图的一条边；

• 路径：上图中D -> C的路径有，D -> B -> C和D -> A -> B -> C两条；

• 无向图：顶点之间的连接没有方向，比如A - B，既可以是A -> B也可以是B -> A；

• 有向图：顶点之间的连接有方向，如下图所示A - B，只能是A -> B，不能是B -> A；

• 带权图：如下图所示，这种边带权值的图也称之为“网”。

1.4 图的表示方式

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

• 邻接矩阵：表示图中的各个顶点之间相邻关系的矩阵。对于有n个顶点的图而言，矩阵的行和列表示的都是图中的各个顶点。矩阵中1表示顶点之间有边，0表示顶点之间没有连接，这种表示方法没有连接也会表示出来，因此比较浪费空间。

  

• 邻接表：邻接表由数组+链表组成，其实现只关注图中存在的边（即邻接矩阵中1所表示的两个顶点之间的连接），而不关心不存在的边（即邻接矩阵中0所表示的两顶点之间没有连接）。因此邻接表是没有空间浪费的。

  

• 说明：上图中标号为0的顶点的相关联的顶点为1，2，3，4；与标号为2的顶点之间有边连接的顶点为0，4，5；其他以此类推。

2. 图的创建

对于上图，使用ArrayList存储顶点集Vertex，使用二维数组int[][]存储邻接矩阵AdjacentMatrix。

代码实现：

package com.datastructure;

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

/**
 * @author SnkrGao
 * @create 2023-05-30 16:04
 */
public class GraphDemo {

    public static void main(String[] args) {

        String[] Vertex = {"1", "2", "3", "4", "5", "6", "7", "8"};
        int vertexNum = Vertex.length;
        int edgeNum = 9;
        Graph graph = new Graph(vertexNum, edgeNum);

        for (String vertex : Vertex) {
            graph.insertVertex(vertex);
        }
        graph.insertEdge(0, 1);
        graph.insertEdge(0, 2);
        graph.insertEdge(1, 3);
        graph.insertEdge(1, 4);
        graph.insertEdge(2, 5);
        graph.insertEdge(2, 6);
        graph.insertEdge(5, 6);
        graph.insertEdge(3, 7);
        graph.insertEdge(4, 7);

        System.out.println("邻接矩阵：");
        graph.showAdjacentMatrix();

    }
}

class Graph {
    private int vertexNum; // 图中的顶点个数
    private int edgeNum; // 图中的边数
    private ArrayList<String> vertexList; // 存储顶点集的List
    private int[][] AdjacentMatrix; // 二维数组存储图对应的邻接矩阵

    // 构造器
    public Graph(int vertexNum, int edgeNum) {
        this.vertexNum = vertexNum;
        this.edgeNum = edgeNum;
        this.vertexList = new ArrayList<>(vertexNum);
        this.AdjacentMatrix = new int[vertexNum][vertexNum];
    }

    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }

    // 向邻接矩阵中添加边，传入的参数表示的是顶点对应的下标
    public void insertEdge(int v1, int v2) {
        // AdjacentMatrix是一个对称矩阵
        AdjacentMatrix[v1][v2] = 1;
        AdjacentMatrix[v2][v1] = 1;
    }

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

3. 图的遍历

所谓图的遍历，即是对顶点的访问，一般有两种访问策略：深度优先遍历和广度优先遍历。

注意：1. 对于图的遍历与树的遍历不同，图中可能存在回路，即在访问完某个顶点后，可能会沿着某条边回到曾经访问过的顶点。因此为了避免重复访问，在对图进行遍历时，需要设置一个辅助数组isVisited[vertexNum]，用于标记对应下标的顶点是否已经被访问过。

​ 2. 每次调用dfs或bfs之前，先对isVisited单独进行初始化。否则调用方法会对isVisited数组中的元素重复赋值。

3.1 深度优先搜索DFS基本思想

• 从初始访问顶点出发，初始访问顶点可能有多个邻接点。DFS的策略就是，首先访问其第一个邻接点，之后再以该被访问的邻接点作为新的初始顶点，再去访问其第一个邻接点；
• 也即DFS的访问策略是优先往纵向挖掘深入，而非对一个顶点的所有邻接点进行横向访问；
• 很明显，DFS是一个递归的过程。

3.2 DFS算法步骤

• 访问开始遍历的初始顶点start（start为初始访问顶点的下标），并标记该顶点为已访问即令isVisited[start] = true；
• 在一维数组int[start]中循环遍历，查找初始访问顶点的第一个邻接点；
• 若该邻接点存在（ie.start与遍历到的顶点之间有边连接，即AdjacentMatrix[start][i] > 0）且该邻接点未被访问过（即isVisited[i] == false）；
• 以该顶点i为新的初始访问顶点start进行dfs，重复执行前面的步骤。

3.3 代码实现

/**
 * 深度优先搜索
 * @param start 开始遍历的顶点在list中的下标
 */
public void dfs(int start) {
    System.out.print(vertexList.get(start) + " ");
    // 标记为已访问
    isVisited[start] = true;

    // 遍历start下标对应的一维数组
    for (int i = 0; i < vertexNum; i++) {
        // 找到第一个邻接点就递归
        if (AdjacentMatrix[start][i] > 0 && !isVisited[i]) {
            dfs(i);
        }
    }
}

3.4 广度优先搜索BFS基本思想

• 类似于一个分层搜索的过程，广度优先遍历需要使用一个队列queue来保持访问过的顶点的顺序，以便按该顺序去访问这些顶点的所有邻接点；
• BFS的策略是：首先从初始访问顶点出发，将该顶点入队列并标记已访问；之后按照出队列的顺序，访问当前出队列顶点的所有邻接点（每访问一个顶点就将其入队列），重复直至队列为空为止。

3.5 BFS算法步骤

• 访问开始遍历的初始顶点start（start为初始访问顶点的下标），并标记该顶点已访问即令isVisited[start] = true；
• 将start入队列，queue.offer(start)；
• 重复执行以下步骤，直至队列为空时终止：
  • 取出队列头的顶点对应下标temp；
  • 在一维数组int[temp]中循环遍历，找到temp对应顶点的所有邻接点；
  • 每找到一个邻接点，就入队并标记其为已访问。

3.6 代码实现

/**
 * 广度优先搜索
 * @param start 开始遍历的顶点在list中的下标
 */
public void bfs(int start) {
    Queue<Integer> queue = new LinkedList<>();
    // 入队列
    queue.offer(start);
    isVisited[start] = true;

    while (!queue.isEmpty()) {
        // 出队列
        int temp = queue.poll();
        System.out.print(vertexList.get(temp) + " ");

        // 遍历temp下标对应的一维数组
        for (int i = 0; i < vertexNum; i++) {
            // 访问所有的邻接点，并入队列
            if (AdjacentMatrix[temp][i] > 0 && !isVisited[i]) {
                queue.offer(i);
                isVisited[i] = true;
            }
        }
    }
}

4. 完整代码

package com.datastructure;

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

/**
 * @author SnkrGao
 * @create 2023-05-30 16:04
 */
public class GraphDemo {

    public static void main(String[] args) {

        String[] Vertex = {"1", "2", "3", "4", "5", "6", "7", "8"};
        int vertexNum = Vertex.length;
        int edgeNum = 9;
        Graph graph = new Graph(vertexNum, edgeNum);

        for (String vertex : Vertex) {
            graph.insertVertex(vertex);
        }
        graph.insertEdge(0, 1);
        graph.insertEdge(0, 2);
        graph.insertEdge(1, 3);
        graph.insertEdge(1, 4);
        graph.insertEdge(2, 5);
        graph.insertEdge(2, 6);
        graph.insertEdge(5, 6);
        graph.insertEdge(3, 7);
        graph.insertEdge(4, 7);

        System.out.println("邻接矩阵：");
        graph.showAdjacentMatrix();

        System.out.println("深度优先搜索：");
        // 调用前先初始化isVisited数组
        graph.setIsVisited(new boolean[vertexNum]);
        graph.dfs(0);

        System.out.println();

        System.out.println("广度优先搜索：");
        // 调用前先初始化isVisited数组
        graph.setIsVisited(new boolean[vertexNum]);
        graph.bfs(0);

    }
}

class Graph {
    private int vertexNum; // 图中的顶点个数
    private int edgeNum; // 图中的边数
    private ArrayList<String> vertexList; // 存储顶点集的List
    private int[][] AdjacentMatrix; // 二维数组存储图对应的邻接矩阵

    private boolean[] isVisited;

    // 构造器
    public Graph(int vertexNum, int edgeNum) {
        this.vertexNum = vertexNum;
        this.edgeNum = edgeNum;
        this.vertexList = new ArrayList<>(vertexNum);
        this.AdjacentMatrix = new int[vertexNum][vertexNum];
    }

    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }

    // 向邻接矩阵中添加边，传入的参数表示的是顶点对应的下标
    public void insertEdge(int v1, int v2) {
        // AdjacentMatrix是一个对称矩阵
        AdjacentMatrix[v1][v2] = 1;
        AdjacentMatrix[v2][v1] = 1;
    }

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

    /**
     * 深度优先搜索
     * @param start 开始遍历的顶点在list中的下标
     */
    public void dfs(int start) {
        System.out.print(vertexList.get(start) + " ");
        // 标记为已访问
        isVisited[start] = true;

        // 遍历start下标对应的一维数组
        for (int i = 0; i < vertexNum; i++) {
            // 找到第一个邻接点就递归
            if (AdjacentMatrix[start][i] > 0 && !isVisited[i]) {
                dfs(i);
            }
        }
    }

    /**
     * 广度优先搜索
     * @param start 开始遍历的顶点在list中的下标
     */
    public void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        // 入队列
        queue.offer(start);
        isVisited[start] = true;

        while (!queue.isEmpty()) {
            // 出队列
            int temp = queue.poll();
            System.out.print(vertexList.get(temp) + " ");

            // 遍历temp下标对应的一维数组
            for (int i = 0; i < vertexNum; i++) {
                // 访问所有的邻接点，并入队列
                if (AdjacentMatrix[temp][i] > 0 && !isVisited[i]) {
                    queue.offer(i);
                    isVisited[i] = true;
                }
            }
        }
    }

    public void setIsVisited(boolean[] isVisited) {
        this.isVisited = isVisited;
    }
}

本栏目推荐文章
• 搜索学习笔记+杂题 （基础一 简单的dfs+bfs）
• lc -- 第 121 场双周赛(bfs, 数位dp, python3, go)
• 深度优先搜索（DFS）和广度优先搜索（BFS）
• LOJ-3033/QOJ-4896/南外集训 2023.12.26 T3 Alice、Bob 与 DFS
• 算法复习 DFS两题
• P9669 [ICPC2022 Jinan R] DFS Order 2 题解
• BFS-走迷宫
• 图(树)的广度优先遍历bfs
• 图(树)的深度优先遍历dfs
• BFS模板

BFS DFSdfs bfs dfs-bfs 模板dfs bfs 基础 笔记dfs bfs 广度 深度dfs bfs 基础bfs dfs 语言dfs bfs 算法dfs-bfs java dfs 记忆 算法dfs bfs 个数 石油dfs bfs