Java 高级数据结构］图形 - 图形表示和迭代

最编程 2024-07-02 12:00:00

...

Java高阶数据结构 & 图的概念 & 图的存储与遍历

1. 图的基本概念

1.1 图的属性

图是由顶点集合及顶点间的关系组成的一种数据结构：

G = (V，E)

Graph图，vertex顶点， edge边

其中：顶点集合V = {x|x属于某个数据对象集}是有穷非空集合；

E = {(x,y)|x,y属于V}或者E = {|x,y属于V && Path(x, y)}，是顶点间关系的有穷集合，也叫做边的集合。

(x, y)表示x到y的一条双向通路，即边(x, y)是无方向的；

Path表示从x到y的一条单向通路，即Path(x, y)是有方向的。

顶点和边：

图中结点称为顶点，

第i个顶点记作vi。

两个顶点vi和vj相关联称作顶点vi和顶点vj之间有一条边，

图中的第k条边记作ek，ek = 无向边(vi，vj)或有向边Path（vi，vj）

1.2 无向图与有向图

在有向图中，顶点对是有序的，顶点对称为顶点x到顶点y的一条边(弧)，Path(x, y)和Path(y, x)是两条不同的边，比如下图G3和G4为有向图。

在无向图中，顶点对(x, y)是无序的，顶点对(x,y) 称为顶点x和顶点y相关联的一条边，这条边没有特定方向，Path(x, y)和Path(y, x)是同一条边，比如下图G1和G2为无向图。

注意：无向边(x, y)等于有向边Path(x, y)和Path(y, x)

网络异常，图片无法展示

1.3 完全图

在有n个顶点的

无向图中，n(n - 1) / 2 条边

任何两个顶点都有且仅有一条边

根据排列组合原理，第一个顶点可连接n - 1个顶点,第二个顶点可以连接 n - 2 个顶点······

第n个顶点可连接0个顶点，总和n(n - 1) / 2

【------】

即无向完全图，如G1

有向图中，n(n - 1)条边

任何两个顶点都有且仅有两条方向相反的边

n(n - 1) / 2 * 2 = n(n - 1)

【<==>】

即有向完全图，如G4

1.4 简单路径和回路

简单路径：路径上的顶点（V1，V2······）均不重复

回路：若路径上的第一个顶点与最后一个顶点重合，即成环回路

网络异常，图片无法展示

1.5 子图

即图G集合的子集G1 = {V1,E1},则称G1为G的子图

V1包含于V

E1包含于E

网络异常，图片无法展示

1.6 连通图

无向图中，V1到V2有路径，则称V1和V2连通

如果每对顶点都是连通的，则称此图为连通图

如果此图为有向图，并且每一对顶点Vi到Vj与Vj到Vi都连通，则称为强连通图

完全图就是更加强大的连通图~

生成树在求最小生成树篇章讲解

2. 图的存储（理论）

2.1 ※邻接矩阵

如果一个图，有n个顶点（V0 ··· Vn-1）

每个顶点都有对应的下标（0 ··· n - 1）

那么邻接矩阵就是个n×n的矩阵

如果顶点Vi到Vj有一条有向边 ---->

直接相连

那么这个矩阵（二维数组）的的i行第j列的元素置为对应的距离（权值）

带权图（不带权图默认为1）

默认值为 ∞（无穷大）

无向图的一条边是双向的

自己到自己可以是0也可以是默认值∞，最好是∞，这样后面好判断

无向图的邻接矩阵是关于对角线对称的：

有向图则不一定：

带权图：

2.2 邻接链表

邻接表：

用数组表示顶点的集合

用链表来表示边的关系

解析：

A可以到B和C，则A对应的链表存放两个节点【1->2->null】

B可以到A和D，则B对应的链表存放两个节点【0->3->null】

C可以到A，则C对应的链表存放一个节点【0->null】

D可以到B，则D对应的链表存放一个节点【1->null】

如果是有向图的邻接表，则分为两种

入边表

出边表

那么所有的链表的节点和就是边数

因为一条有向边必然是一个顶点的“出”，另一个顶点的“入”

3. 图的存储（代码表示）

3.1 邻接矩阵

3.1.1 邻接矩阵的基本属性

public class GraphByMatrix{
    // 1. 顶点集合
    private char[] arrayV;
    //2. 邻接矩阵
    private int[][] matrix;//顶点在这里的下标即在字符数组的下标
    //3. 是否是有向图
    private boolean isDirect;
   
}

3.1.2 构造方法和初始化方法

/**
 *
 * @param size 【顶点个数】
 * @param isDirect
 */
public GraphByMatrix(int size, boolean isDirect) {
    this.arrayV = new char[size];
    matrix = new int[size][size];//此时默认都是0
    this.isDirect = isDirect;
    //将邻接矩阵默认值改为【∞】
    for (int i = 0; i < size; i++) {
        Arrays.fill(matrix[i], Integer.MAX_VALUE);
        //fill,让数组充满【∞】这个值
    }
}
public void initArrayV(char[] array) {
    for (int i = 0; i < array.length; i++) {
        arrayV[i] = array[i];
    }
}

构造方法

传入size，即顶点的个数 ==> arrayV的大小

传入isDirect，即确认是有向图或者无向图

将邻接矩阵的默认值改为无穷大

初始化顶点集合

传入字符数组，挨个赋值

测试：

public static void main(String[] args) {
    char[] chars = {'A', 'B', 'C', 'D'};
    GraphByMatrix graph = new GraphByMatrix(chars.length, true);
    graph.initArrayV(chars);
    System.out.println();
}

3.1.3 获取顶点字符在顶点集合中的下标

这个方法获得的下标，也代表该顶点在邻接矩阵的下标

可以用哈希表去存储顶点们，这里不是~

所以我用的是遍历数组的方法

//获得顶点对应下标
public int getIndexOfV(char v) {
    for (int i = 0; i < arrayV.length; i++) {
        if(v == arrayV[i]) {
            return i;
        }
    }
    return -1;
}

3.1.4 增加边

参数左指向参数右的有向边

如果是无向图，默认参数右也指向参数左

/**
 * 添加边
 * @param v1 起始顶点
 * @param v2 目的顶点
 * @param weight 权值
 */
public void addEdge(char v1, char v2, int weight) {
    int index1 = getIndexOfV(v1);
    int index2 = getIndexOfV(v2);
    if(index1 != -1 && index2 != -1 && index1 != index2) {
        matrix[index1][index2] = weight;
        //index1 --> index2
        if(!isDirect) {//无向图
            matrix[index2][index1] = weight;
        }
    }
}

测试：

public static void main(String[] args) {
        char[] chars = {'A', 'B', 'C', 'D'};
        GraphByMatrix graph = new GraphByMatrix(chars.length, true);
        graph.initArrayV(chars);
        graph.addEdge('A', 'B', 1);
        graph.addEdge('A', 'D', 1);
        graph.addEdge('B', 'A', 1);
        graph.addEdge('B', 'C', 1);
        graph.addEdge('C', 'B', 1);
        graph.addEdge('C', 'D', 1);
        graph.addEdge('D', 'A', 1);
        graph.addEdge('D', 'C', 1);
        System.out.println();
    }
}

对比：