1、基本介绍

线性表局限于一个直接前驱和一个直接后继的关系,树也只能有一个直接前驱,也就是父结点。当我们需要表示多对多的关系时,就会用到图这个结构。
图是一种数据结构,其中的结点也称为顶点,两个顶点之间的连接称为边。
 

2、图的常用概念

1、顶点(vertex):即结点;
2、边(edge):两个顶点之间的连线;
3、路径:一个顶点到另一个顶点直接的连线集合;
4、无向图
 
5、有向图
6、带权图
 

3、图的表示方式

图的表示方式主要有两种:二维数组表示(邻接矩阵)和链表表示(邻接表)。

3.1 邻接矩阵

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

3.2 邻接表

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

4、图的代码实现

代码中,图用邻接矩阵表示。

package cn.klb.datastructures.graph;

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

/**
 * @author DDKK.COM 弟弟快看,程序员编程资料站
 * @Description:
 * @Date: Create in 2023/4/18 18:59
 * @Modified By:
 */
public class Graph {
   
     
    private ArrayList<String> vertexsList;  // 存储图的顶点
    private int[][] edges;  // 存储图对应的邻接矩阵
    private int numberOfEdges;  // 图的边的个数

    public Graph(int n) {
   
     
        this.edges = new int[n][n];
        this.vertexsList = new ArrayList<String>(n);
        numberOfEdges = 0;
    }
    /**
     * 显示图对应的邻接矩阵
     */
    public void showGraph() {
   
     
        for (int[] link : edges) {
   
     
            System.out.println(Arrays.toString(link));
        }
    }

    /**
     * 返回顶点的个数
     *
     * @return
     */
    public int getNumberOfVertexs() {
   
     
        return this.vertexsList.size();
    }

    /**
     * 获取图中边的个数
     *
     * @return
     */
    public int getNumberOfEdges() {
   
     
        return this.numberOfEdges;
    }

    /**
     * 返回第 index 个顶点
     *
     * @param index
     * @return
     */
    public String getVertexsByIndex(int index) {
   
     
        return vertexsList.get(index);
    }

    /**
     * 获取顶点的索引
     *
     * @param vertexs
     * @return
     */
    public int getIndexByVertexs(String vertexs) {
   
     
        for (int index = 0; index < vertexsList.size(); index++) {
   
     
            if (vertexs.equals(vertexsList.get(index))) {
   
     
                return index;
            }
        }
        return -1;
    }

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

    /**
     * 对v1和v2进行连接,边的权值未weight
     *
     * @param v1
     * @param v2
     * @param weight
     */
    public void insertEdge(int v1, int v2, int weight) {
   
     
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numberOfEdges++;
    }

    /**
     * 对v1和v2进行连接,边的权值未weight
     *
     * @param v1
     * @param v2
     * @param weight
     */
    public void insertEdge(String v1, String v2, int weight) {
   
     
        edges[getIndexByVertexs(v1)][getIndexByVertexs(v2)] = weight;
        edges[getIndexByVertexs(v2)][getIndexByVertexs(v1)] = weight;
        numberOfEdges++;
    }
}

5、图的遍历

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

5.1 深度优先遍历

5.1.1 基本思想

图的深度优先搜索(Depth First Search),从初始访问顶点出发,访问它的第一个邻接顶点,然后再以这个被访问的邻接顶点作为初始顶点,又访问第一个邻接顶点。即每次访问完当前顶点后首先访问当前顶点的第一个邻接顶点。
可以看出,这个访问策略是优先纵向挖掘深入,而不是对一个顶点的所有邻接顶点进行横向访问。显然,深度优先遍历是一个递归的过程。

5.1.2 算法步骤

1、访问初始顶点v,并标记顶点v为已访问;
2、查找顶点v的第一个邻接顶点w;
3、若w存在且未被访问过,则对w进行深度优先遍历递归;若w不存在或者存在但被访问过了,则查找结点v的w邻接结点后的下一个邻接结点,重复步骤3。
 
比如上面这个图,深度优先遍历的结果是:{1,2,4,8,5,3,6,7}

5.1.3 代码实现

    /**
     * 对图进行深度优先遍历
     */
    public void dfs() {
   
     
        isVisited = new boolean[vertexsList.size()];
        for (int i = 0; i < getNumberOfVertexs(); i++) {
   
     
            if (!isVisited[i]) {
   
     
                doDFS(isVisited, i);
            }
        }
    }

    /**
     * 深度优先遍历算法
     *
     * @param isVisited
     * @param i
     */
    private void doDFS(boolean[] isVisited, int i) {
   
     
        // 访问顶点,输出
        System.out.print(getVertexsByIndex(i) + " ");
        // 把这个点设置为已读
        isVisited[i] = true;
        // 找到顶点i的第一个邻接顶点
        int w = getNextNeighbor(i, -1);
        while (w != -1) {
   
     
            if (!isVisited[w]) {
   
     
                doDFS(isVisited, w);
            }
            // 如果w已经被访问过了,就继续找下一个邻接顶点
            w = getNextNeighbor(i, w);
        }
    }

    /**
     * v2是v1的邻接顶点,返回v2之后的下一个邻接顶点
     *
     * @param v1
     * @param v2
     * @return
     */
    public int getNextNeighbor(int v1, int v2) {
   
     
        for (int i = v2 + 1; i < vertexsList.size(); i++) {
   
     
            if (edges[v1][i] > 0) {
   
     
                return i;
            }
        }
        return -1;
    }

5.2 广度优先遍历

5.2.1 基本思想

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

5.2.2 算法步骤

1、访问初始顶点v并标记顶点v为以访问;
2、顶点v入队列;
3、当队列不为空时,算法继续往下执行;
4、取出队列头顶点u;
5、查找顶点u的第一个邻接顶点w;
6、若顶点w不存在,则转到步骤3,否则向下执行;
6.1、若顶点w未被访问,则访问顶点w并把w标记为以访问;
6.2、顶点w入队列;
6.3、查找顶点u继w后的下一个邻接顶点,转到步骤6。
 
比如上面这个图,广度优先遍历的结果是:{1,2,3,4,5,6,7,8}

5.2.3 代码实现

    /**
     * 执行广度优先遍历
     */
    public void bfs() {
   
     
        isVisited = new boolean[vertexsList.size()];
        for (int i = 0; i < getNumberOfVertexs(); i++) {
   
     
            if (!isVisited[i]) {
   
     
                doBFS(isVisited, i);
            }
        }
    }

    /**
     * 广度优先遍历算法
     *
     * @param isVisited
     * @param i
     */
    private void doBFS(boolean[] isVisited, int i) {
   
     
        // 用一个链表模拟队列,用于记录顶点的访问顺序
        LinkedList queue = new LinkedList();

        int u;   // 表示队列的头顶点对应下标(是顶点的下标,不是队列的下标)
        int w;  // 邻接顶点

        // 访问顶点,输出顶点信息
        System.out.print(getVertexsByIndex(i) + " ");

        // 访问过后就设置为已访问
        isVisited[i] = true;

        // 把顶点加入到队列
        queue.add(i);

        // 只要队列不空,就继续
        while (!queue.isEmpty()) {
   
     
            // 获取队列头顶点下标
            u = (Integer) queue.removeFirst();
            // 得到第一个邻接顶点的下标 w
            w = getNextNeighbor(u, -1);
            // -1 表示找不到邻接顶点
            while (w != -1) {
   
     
                if (!isVisited[w]) {
   
       // 如果第一个邻接顶点没有被访问过,则输出
                    System.out.print(getVertexsByIndex(w) + " ");
                    isVisited[w] = true;
                    // 入队
                    // 会发现入队的全是w的邻接顶点,意思就是w的邻接顶点先遍历完
                    // 然后取出队列里的元素变为新的 u
                    queue.addLast(w);
                }
                // 以u为前驱点,找w后面的下一个邻顶点
                w = getNextNeighbor(u, w);
            }
        }
    }