Java数据结构（十七）—

Java数据结构（十七）—— 图

图

图的基本介绍

为什么要有图？

线性表局限于一个直接前去和一个直接后继的关系
树也只能有一个直接前去也就是父节点
当我们表示多对多的关系是=时，就用到了图

图的举例说明

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

如图：

图的常用概念

顶点：节点
边：顶点间的连接
路径：节点A到节点B的通路
无向图：顶点之间的连接没有方向
有向图：顶点之间的连接有方向
带权图：边带有权值的图

图的表示方式

邻接矩阵（二维数组表示）
- 邻接矩阵：是表示图形中顶点之间相邻关系的矩阵，对于 n个顶点的图而言，矩阵是row和col表示的是1……n个点
- 0表示不直接连通，1表示直接连通
邻接表（链表表示）
- 邻接矩阵需要为每隔顶点都分配n个边的空间，其实有很多边都是不存在的，会造成空间损失
- 邻接表只关心存在的边
- 邻接表由数组 + 链表组成
- 二维数组表示各个节点标号，链表存储与之连通的节点标号

图的创建

要求

代码实现如下图

思路分析

存储顶点 String 使用 ArrayList
保存邻接矩阵矩阵，使用二维数组

代码实现

package com.why.graph;

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

/**
 * @Description TODO 图
 * @Author why
 * @Date 2020/12/7 17:42
 * Version 1.0
 **/
public class Graph {

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

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

    private int numOfEdges;//边的个数

    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.insertVertex(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();
    }

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

    /**
     * 插入节点
     * @param vertex
     */
    public void insertVertex(String vertex){
        vertexList.add(vertex);
    }

    /**
     * 添加边
     * @param v1 节点下标
     * @param v2 节点下标
     * @param weight 权值
     */
    public void insertEdge(int v1,int v2,int weight){
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }

    /**
     * 返回节点数目
     * @return
     */
    public int getNumOfVertex(){
        return vertexList.size();
    }

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

    /**
     * 返回下标为i的节点
     * @param i
     * @return
     */
    public String getValueByIndex(int i){
        return vertexList.get(i);
    }

    /**
     * 返回v1和v2之间的权值
     * @param v1
     * @param v2
     * @return
     */
    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }

    /**
     * 显示图的矩阵
     */
    public void showGraph(){
        //遍历二维数组
        for (int[] link : edges
             ) {
            System.err.println(Arrays.toString(link));
        }
    }
}

图的遍历

图的遍历，即是对节点的访问

深度优先(Depth First Search , DFS)遍历

基本思想

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

算法步骤

访问初始节点v,并标记节点v为已访问
查找节点v的第一个邻接点w
若w存在，则继续执行4，若不存在，则回到第1步，将从v的下一个节点继续
若w未被访问，对w进行深度优先遍历递归
查找节点v的w邻接节点的下一个邻接节点

具体案例

代码实现

创建标志数组，标志节点是否被访问

private boolean[] isVisited ;//标志节点是否被访问

dfs，深度优先遍历及其方法

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

/**
 * 根据上一个邻接节点的下标获取下一个邻接节点
 * @param v1 当前节点
 * @param v2 当前节点已被访问的邻接节点
 * @return
 */
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;
}

/**
 * 深度优先遍历
 * @param isVisited 标志数组
 * @param i 第一次就是0
 */
private void dfs(boolean[] isVisited,int i){
    //首先访问该节点
    System.out.print(getValueByIndex(i) + "->");
    //将该节点设置为已访问
    isVisited[i] = true;

    //以i下标的节点为当前节点进行深度遍历
    //寻找第一个邻接节点
    int w = getFirstNeighbor(i);
    while (w != -1){//找到邻接节点
        if (!isVisited[w]){//没有被访问
            dfs(isVisited,w);
        }
        //如果w节点已经被访问，查找邻接节点的下一个节点
        w = getNextNeighbor(i,w);
    }
}

/**
 * 重载dfs，遍历所有的节点，对节点进行dfs深度优先遍历
 */
public void dfs(){
    //遍历所有节点
    for (int i = 0; i < getNumOfVertex(); i++) {
        if (!isVisited[i]){//没有被访问过，进行深度遍历
            dfs(isVisited,i);
        }
    }
}

测试

//测试深度优先遍历
System.out.println("深度优先遍历：");
graph.dfs();

广度优先（Broad First Search，BFS）遍历

基本介绍

类似于分层搜索的过程
使用一个队列以保持访问过的节点的顺序，以便按这个顺序来访问这些节点的邻接节点

算法步骤

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

6.1 若结点 w 尚未被访问，则访问结点 w 并标记为已访问。

6.2 结点 w 入队列

6.3 查找结点 u 的继 w 邻接结点后的下一个邻接结点 w，转到步骤 6。

代码实现

/**
 * 对一个节点进行广度优先遍历
 * @param isVisited 标志数组
 * @param i 节点
 */
private void bfs(boolean[] isVisited,int i){
    int u;//表示队列的头节点对应的下标
    int w;//邻接节点w
    //队列，记录节点访问的顺序
    LinkedList queue = new LinkedList();
    //访问当前节点，输出信息
    System.out.print(getValueByIndex(i) + "->");
    //标记为已访问
    isVisited[i] = true;
    //将节点加入队列
    queue.addLast(i);
    while (!queue.isEmpty()) {//队列非空
        //取出队列的头节点下标
        u = (Integer) queue.removeFirst();
        //得到第一个邻接点下标
        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() {
    for (int i = 0; i < getNumOfVertex(); i++) {
        if (!isVisited[i]) {//没有被访问过
            bfs(isVisited, i);
        }
    }
}

深度优先 VS 广度优先　

图的代码汇总

package com.why.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.jar.JarEntry;

/**
 * @Description TODO 图
 * @Author why
 * @Date 2020/12/7 17:42
 * Version 1.0
 **/
public class Graph {

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

    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"};
        //创建图
        Graph graph = new Graph(n);
        //循环添加节点
        for (String value : Vertexs
             ) {
            graph.insertVertex(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();
//        System.out.println();

        //测试广度优先遍历
        System.out.println("广度优先遍历：");
        graph.bfs();
    }

    /**
     * 构造器
     * @param n 顶点个数
     */
    public Graph(int n) {
        //初始化矩阵和顶点列表
        edges = new int[n][n];
        vertexList = new ArrayList<>(n);
        numOfEdges = 0;
        isVisited = new boolean[n];
    }

    /**
     * 插入节点
     * @param vertex
     */
    public void insertVertex(String vertex){
        vertexList.add(vertex);
    }

    /**
     * 添加边
     * @param v1 节点下标
     * @param v2 节点下标
     * @param weight 权值
     */
    public void insertEdge(int v1,int v2,int weight){
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }

    /**
     * 返回节点数目
     * @return
     */
    public int getNumOfVertex(){
        return vertexList.size();
    }

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

    /**
     * 返回下标为i的节点
     * @param i
     * @return
     */
    public String getValueByIndex(int i){
        return vertexList.get(i);
    }

    /**
     * 返回v1和v2之间的权值
     * @param v1
     * @param v2
     * @return
     */
    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }

    /**
     * 显示图的矩阵
     */
    public void showGraph(){
        //遍历二维数组
        for (int[] link : edges
             ) {
            System.err.println(Arrays.toString(link));
        }
    }

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

    /**
     * 根据上一个邻接节点的下标获取下一个邻接节点
     * @param v1 当前节点
     * @param v2 当前节点已被访问的邻接节点
     * @return
     */
    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;
    }

    /**
     * 深度优先遍历
     * @param isVisited 标志数组
     * @param i 第一次就是0
     */
    private void dfs(boolean[] isVisited,int i){
        //首先访问该节点
        System.out.print(getValueByIndex(i) + "->");
        //将该节点设置为已访问
        isVisited[i] = true;

        //以i下标的节点为当前节点进行深度遍历
        //寻找第一个邻接节点
        int w = getFirstNeighbor(i);
        while (w != -1){//找到邻接节点
            if (!isVisited[w]){//没有被访问
                dfs(isVisited,w);
            }
            //如果w节点已经被访问，查找邻接节点的下一个节点
            w = getNextNeighbor(i,w);
        }
    }

    /**
     * 重载dfs，遍历所有的节点，对节点进行dfs深度优先遍历
     */
    public void dfs(){
        //遍历所有节点
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]){//没有被访问过，进行深度遍历
                dfs(isVisited,i);
            }
        }
    }

    /**
     * 对一个节点进行广度优先遍历
     * @param isVisited 标志数组
     * @param i 节点
     */
    private void bfs(boolean[] isVisited,int i){
        int u;//表示队列的头节点对应的下标
        int w;//邻接节点w
        //队列，记录节点访问的顺序
        LinkedList queue = new LinkedList();
        //访问当前节点，输出信息
        System.out.print(getValueByIndex(i) + "->");
        //标记为已访问
        isVisited[i] = true;
        //将节点加入队列
        queue.addLast(i);
        while (!queue.isEmpty()) {//队列非空
            //取出队列的头节点下标
            u = (Integer) queue.removeFirst();
            //得到第一个邻接点下标
            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() {
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]) {//没有被访问过
                bfs(isVisited, i);
            }
        }
    }
}

所有源码都可在gitee仓库中下载：https://gitee.com/vvwhyyy/java_algorithm