图Graph的存储、图的广度优先搜索和深度优先搜索（待更新）

目录

一、图的两种存储方式

1.邻接矩阵

2.邻接表

---

生活中处处有图Graph的影子，例如交通图，地图，电路图等，形象的表示点与点之间的联系。

首先简单介绍一下图的概念和类型：

 

图的的定义：图是由一组顶点和一组能够将两个顶点相连的边组成的

图的类型：

顶点之间的连接方向：无方向-->无向图  有方向-->有向图 

边上是否有权值：有-->带权图  无-->无权图

以下分别是：无向无权、有向无权、无向有权、有向有权图

 

 

一、图的两种存储方式

1.邻接矩阵

存储原理：邻接矩阵是一种用数组来表示图的方法，其中矩阵的行和列表示图中的顶点，矩阵元素表示顶点之间是否有边相连。具体来说，如果顶点v和顶点u之间有边，则矩阵的第u行第v列的元素为1；否则为0。带权值则为权值，没有相连的为0。

优点：

• 结构简单，易于理解和实现。

• 对于稠密图，邻接矩阵的空间利用率较高。

• 可以方便地计算出图中节点的度（即与该节点相邻的节点的数量）。

缺点：

• 对于稀疏图，邻接矩阵可能占用大量空间。

• 访问相邻节点的速度较慢，需要进行遍历操作。

示例：下图的邻接矩阵存储

 

代码实现 

import java.util.Arrays;
 
//邻接矩阵
public class Graph01 {
 
    char[] val;//顶点数据
 
    int[][] edges;//二维数组记录边
 
    Vertex[] vertices;//顶点类数组
 
    int N;//表大小
 
    public Graph01(char[] arr) {
        this.N = arr.length;
        //初始化顶点数据
        this.val = Arrays.copyOf(arr, arr.length);
        this.edges = new int[this.N][this.N];
        this.vertices = new Vertex[this.N];
        for (int i = 0; i < this.N; i++) {
            this.vertices[i] = new Vertex(arr[i]);
        }
    }
 
    private class Vertex {
        Character val;
 
        public Vertex(Character val) {
            this.val = val;
        }
    }
 
    //打印邻接矩阵
    public void show() {
        System.out.format("%5c", 32);
        for (int i = 0; i < this.N; i++) {
            System.out.format("%5c", this.val[i]);
        }
        System.out.println();
 
        for (int i = 0; i < this.N; i++) {
            System.out.format("%5c", this.val[i]);
            for (int j = 0; j < this.N; j++) {
                System.out.format("%5d", this.edges[i][j]);
            }
            System.out.println();
        }
    }
 
 
    public static void main(String[] args) {
        char[] arr = {'A', 'E', 'F', 'G', 'H', 'P'};
        Graph01 graph01 = new Graph01(arr);
 
        // 构建边集
        int[][] edges = graph01.edges;
        edges[0][1] = 5;
        edges[0][2] = 4;
        edges[0][3] = 2;
 
        edges[1][0] = 5;
        edges[1][3] = 1;
        edges[1][4] = 3;
 
        edges[2][0] = 4;
 
        edges[3][0] = 2;
        edges[3][1] = 1;
        edges[3][4] = 2;
        edges[3][5] = 4;
 
        edges[4][1] = 3;
        edges[4][3] = 2;
        edges[4][5] = 3;
 
 
        edges[5][3] = 4;
        edges[5][4] = 3;
 
        // 调用打印方法
        graph01.show();
    }
}

打印结果 ： 

 

2.邻接表

存储原理：

邻接表中的每个节点都对应一个链表，链表中的每个元素都是一个顶点（或节点），表示与当前节点相邻的节点。这种方式在处理稀疏图（即边的数量远小于顶点的数量）时效率较高。

优点：

• 存储空间开销较小，适用于稀疏图。

• 查找速度快，可以直接通过索引访问相邻节点。

• 可动态添加、删除节点和边。

缺点：

• 存储结构相对复杂，不利于处理大规模数据。

• 空间利用率不高，对于稠密图可能存在大量未使用的节点和边。

代码实现 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
//邻接表
public class Graph02 {
 
    char[] val;//顶点数据
 
    List[] edgesList;//边连接
 
    Vertex[] vertices;
 
    int N;//表大小
    public Graph02(char[] arr){
       this.N = arr.length;
       this.val = Arrays.copyOf(arr,arr.length);
       this.edgesList = new List[this.N];
       this.vertices = new Vertex[this.N];
       for (int i = 0; i < this.N; i++) {
            this.vertices[i] = new Vertex(arr[i]);
            this.edgesList[i] = new ArrayList<>();
        }
   }
 
    private class Vertex{
        Character val;
        public Vertex(Character val){
            this.val = val;
        }
    }
 
    public void show(){
 
        //打印邻接矩阵
        for (int i = 0; i <this.N; i++) {
            System.out.format("%-3c",this.val[i]);
            List list = this.edgesList[i];
            list.stream().forEach(item->{
                System.out.format("%d-->",item);
            });
            System.out.println();
        }
    }
 
 
    public static void main(String[] args) {
        char[] arr = {'A', 'E', 'F', 'G', 'H', 'P'};
        Graph02 graph02 = new Graph02(arr);
 
        // 构建边集
        List[] edges = graph02.edgesList;
 
        edges[0].add(1);
        edges[0].add(2);
        edges[0].add(3);
 
        edges[1].add(0);
        edges[1].add(3);
        edges[1].add(4);
 
        edges[2].add(0);
 
        edges[3].add(0);
        edges[3].add(1);
        edges[3].add(4);
        edges[3].add(5);
 
        edges[4].add(1);
        edges[4].add(3);
        edges[4].add(5);
 
        edges[5].add(3);
        edges[5].add(4);
 
 
        // 调用打印方法
        graph02.show();
    }
}

打印结果 ：