图的基本操作

用户11097514

发布于 2024-05-30 21:39:43

800

发布于 2024-05-30 21:39:43

文章被收录于专栏：技术分享

图的定义

图是一种非线性数据结构，由【顶点Vertex】和【边Edge】组成。我们可以将图G抽象地表示为一组顶点V 和一组边 E 地集合。

如下图就是图地网络关系和树以及链表地区别

图与其他数据结构之间的关系我们可以抽象为

把顶点看作节点，将边看作各个节点地指针。，可以将图看作是一种从链表拓展而来的数据结构。它的复杂度和自由度更高。

图的常见类型

根据边是否具有方向，可分为「无向图 Undirected Graph」和「有向图 Directed Graph」

根据所有顶点是否联通，可分为「连通图 Connected Graph」和「非连通图 Disconnected Graph」

连通图：从一个顶点出发可以到达其余任意顶点。

非连通图：从一个顶点出发，至少有一个顶点无法到达。

还可以为图添加权重变量，从未得到有权图[Weighted Graph]

图的常用术语

图是由节点（vertices）和边（edges）组成的一种数据结构，常用术语包括：

有向图（Directed Graph）：每条边都有一个方向，从一个节点指向另一个节点。
无向图（Undirected Graph）：每条边没有方向，连接两个节点。
加权图（Weighted Graph）：每条边都有一个权重值，表示两个节点之间的距离、代价等。
连通图（Connected Graph）：图中的任意两个节点都可以通过路径相连。
子图（Subgraph）：一个图的一部分，包含一些节点和它们之间的边。
点的度数（Degree）：指与该节点相连的边的数目。
路径（Path）：连接两个节点的一系列边构成的序列。
环（Cycle）：路径的起点和终点相同的路径。
连通分量（Connected Component）：无向图中的极大连通子图。
强连通分量（Strongly Connected Component）：有向图中的极大强连通子图。
度（Degree）： 表示一个顶点所拥有的边数，对于有向图，那么描述变数就需要使用下面的两个出入度。
入度（In-degree）：有向图中指向一个节点的边的数目。
出度（Out-degree）：有向图中从一个节点出发的边的数目。
邻居（Neighbor）/邻接Adjacency：指与一个节点相连的其他节点。
序列（Sequence）：一个节点序列，其中每个节点都与相邻的节点相连。
生成树（Spanning Tree）：一个连通无向图的生成树是一个无环连通子图，包含所有节点，且仅有n-1条边。

图的表示方法

邻接矩阵：

设图的顶点数量为 n ，「邻接矩阵 Adjacency Matrix」使用一个 n×n 大小的矩阵来表示图，每一行（列）代表一个顶点，矩阵元素代表边，用 1 或 0 表示两个顶点之间是否存在边。

如下图所示，设邻接矩阵为 M 、顶点列表为 N ，那么矩阵元素M[i][j]=1 表示顶点 V[i]到顶点 V[j] 之间存在边，反之M[i][j]= 0 表示两顶点之间无边。

对角线无意义。
如果将矩阵中的数字换成其他数字，那么就相当于权重
对于邻接矩阵表示图时，它的curd操作时间复杂度非常低，都是O（1）。但是空间复杂度非常高，因为要构造邻接矩阵，所以未O（n2）

邻接表：

使用邻接表法和 hash表有异曲同工之妙。都是通过链表来实现。

「邻接表 Adjacency List」使用 n 个链表来表示图，链表节点表示顶点。第 i条链表对应顶点 i ，其中存储了该顶点的所有邻接顶点（即与该顶点相连的顶点）。

它相较于邻接矩阵最大的优点就是他存储的内容都是有用的，而不是像邻接矩阵那样都存储。

同时，邻接表我们可以进行优化，将链表过长的部分像hash表那样转换为红黑树。从而可以将时间效率从O(n)—-> O(log n)

基于邻接矩阵的实现

package tu;

import java.util.ArrayList;
import java.util.List;

/**
 * 基于邻接矩阵实现图
 */
public class GraphAdjMat {
    //定义邻接矩阵
    List<List<Integer>> AdjMat;
    //定义顶点列表
    List<Integer> vertices;

    /**
     * 构造器，对邻接矩阵进行初始化
     * @param edges edges 元素代表顶点索引，即对应 vertices 元素索引
     * @param Vertices 传入的顶点列表
     */
    public GraphAdjMat(int[][] edges , int[] Vertices){
        //1. 先new矩阵 和 列表 对象 (初始化空间)
        AdjMat = new ArrayList<>();
        vertices = new ArrayList<>();
        //2. 对顶点列表进行赋值,同时扩展矩阵
        for (int i : Vertices){
            addAdjMat(i);
        }
        //3. 添加边 .其中的edges中的元素为矩阵中为
        for (int[] e : edges) {
            addEdge(e[0], e[1]);
        }
    }

    //todo 实现元素顶点列的元素添加， 同时对矩阵进行扩展
    public void addAdjMat(int val){
        int size = vertices.size();
        vertices.add(val);
        //在矩阵中添加一行
        List<Integer> list = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            list.add(0);
        }
        AdjMat.add(list);
        //在矩阵中添加一列
        for (List<Integer> row : AdjMat){
            row.add(0);
        }
    }

    //todo 对矩阵进行赋值 ，其中 m、n 代表vertices的索引
    public void addEdge(int m , int n){
        //需要对数组下表越界 以及对角线的情况进行处理
        if(m < 0 || n < 0 || m > vertices.size() || n > vertices.size() || m == n){
            throw new IndexOutOfBoundsException("数组下标越界");
        }
        AdjMat.get(m).set(n,1);
        AdjMat.get(n).set(m,1);
    }


    /**
     * 删除边 ， 就是删除个顶点之间的边
     * @param m 该顶点对应vertices中元素的索引
     * @param n 另一个顶点对应vertices中元素的索引
     */
    public void removeAdjMat(int m ,int n){
        //还是需要考虑数组下标越界情况
        if(m < 0 || n < 0 || m > vertices.size() || n > vertices.size() || m == n){
            throw new IndexOutOfBoundsException("数组下标越界");
        }
        //修改两个顶点的连线
        AdjMat.get(m).set(n,0);
        AdjMat.get(n).set(m,0);

    }

    /**
     * 删除对应的顶点 ，需要同时删除矩阵中顶点对应的row and lie
     * @param index 元素在vertices中的索引
     */
    public void removeVertices(int index){
        //判断下标是否越界
        if (index > vertices.size()){
            throw new IndexOutOfBoundsException("数组下标越界， 无法删除");
        }
        vertices.remove(index);
        //删除矩阵中对应的row and lie
        AdjMat.remove(index);
        for (List<Integer> row : AdjMat){
            row.remove(index);
        }
    }

    //todo 打印矩阵
    public void list(){
        System.out.println("顶点列表....");
        vertices.forEach(System.out::print);
        System.out.println();
        System.out.println("矩阵....");
        for (int i = 0; i < AdjMat.size(); i++) {
            for (int j = 0; j < AdjMat.get(i).size(); j++) {
                System.out.print(AdjMat.get(i).get(j) + "\t");
            }
            System.out.println();
        }
    }


    public static void main(String[] args) {
        int[] vertices = new int[]{1,3,2,5,4};
        int[][] edges = new int[][]{
                {0,1},
                {0,3},
                {1,0},
                {2,1},
                {2,3},
                {2,4},
                {3,0},
                {3,2},
                {3,4},
                {4,2},
                {4,3}
        };
        GraphAdjMat graphAdjMat = new GraphAdjMat(edges,vertices);
        graphAdjMat.list();
    }


}

基于邻接表的实现

package tu;

import org.omg.CORBA.MARSHAL;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 基于邻接表实现图
 * 将顶点用顶点类Vertex 进行封装
 */
public class Graph {
    // 邻接表，key: 顶点，value：该顶点的所有邻接顶点
    Map<Vertex, List<Vertex>> adjList;

    /**
     * 初始化邻接表
     * @param edges 两顶点之间的边的关系， edges中的数代表顶点上的数
     */
    public Graph(Vertex[][] edges){
        this.adjList = new HashMap<>();
        //添加顶点
        for (Vertex[] edge  : edges){
            addVertex(edge[0]);
            addVertex(edge[1]);
            //添加边
            addAdjMat(edge[0],edge[1]);
        }
    }

    /**
     * 添加两个顶点之间的关系， 也就是添加边的关系
     * @param item0 顶点0
     * @param item1 顶点1
     */
    private void addAdjMat(Vertex item0, Vertex item1) {
        //首先判断两个顶点是否存在， 如果不存在就不能添加边的关系
        if (!adjList.containsKey(item0) || !adjList.containsKey(item1) || item0 == item1){
            throw new IndexOutOfBoundsException("其中一个顶点不存在！");
        }
        if (!adjList.get(item0).contains(item1)){
            adjList.get(item0).add(item1);
        }
           if (!adjList.get(item1).contains(item0)){
            adjList.get(item1).add(item0);
        }
        
    }

    /**
     * 添加点 ，并且需要将扩展顶点
     * @param item 顶点val
     */
    private void addVertex(Vertex item) {
        //先判断顶点是否存在
        if(adjList.containsKey(item)){
            return;
        }
        adjList.put(item,new ArrayList<>());
    }

    /**
     * 删除顶点 ，同时需要删除所有有关它的边的关系
     * @param val 顶点的所有边的关系
     */
    public void removeVertex(Vertex val){
        //先判断顶点是否存在
        if(!adjList.containsKey(val)){
            throw new IndexOutOfBoundsException("顶点不存在");
        }
        adjList.remove(val);
        //先遍历每个顶点，然后看他里面是否存在val顶点， 存在就删除
        for (Map.Entry<Vertex,List<Vertex>> item : adjList.entrySet()){
           item.getValue().remove(val);
        }
    }

    //todo 打印邻接表
    public void list(){
        for (Map.Entry<Vertex,List<Vertex>> item : adjList.entrySet()){
            System.out.print("key : " + item.getKey() + " value : ");
            List<Vertex> value = item.getValue();
            for (Vertex vertex  : value){
                System.out.print(vertex + "—>");
            }
            System.out.println();

        }
    }

    public static void main(String[] args) {
        Vertex vertex1 = new Vertex(1);
        Vertex vertex3 = new Vertex(3);
        Vertex vertex2 = new Vertex(2);
        Vertex vertex5 = new Vertex(5);
        Vertex vertex4 = new Vertex(4);
        Vertex[][] vertices = new Vertex[][]{
                {vertex1,vertex3},
                {vertex3,vertex1},
                {vertex2,vertex3},
                {vertex5,vertex1},
                {vertex4,vertex2},
        };
        Graph graph = new Graph(vertices);
        graph.addAdjMat(vertex1, vertex5);
        graph.addAdjMat(vertex3, vertex2);
        graph.addAdjMat(vertex2, vertex5);
        graph.addAdjMat(vertex2, vertex4);
        graph.addAdjMat(vertex5, vertex2);
        graph.addAdjMat(vertex5, vertex4);
        graph.addAdjMat(vertex4, vertex5);
        graph.list();
    }

}