graph——图数据结构基础

摘要：介绍图（Graph）相关的定义和图的分类，使用Java语言实现了图的数据结构。

图（Graph）相关定义及分类

图（Graph）

一个图（graph）G=（V，E）由顶点（vertex）的集V和边（edge）的集E组成

有向图

无向图

图的表示

邻接矩阵（Adjacent Matrix）

邻接表（Adjacent List）

图数据结构的实现

创建一个接口，在接口中声明图主要的API

package com.shg.graph;

/**
 * @author: shg
 * @create: 2022-05-17 4:11 下午
 */
public interface Graph<K, E> {

    /**
     *
     * @return 边的个数
     */
    int edgesSize();

    /**
     *
     * @return 定点个数
     */
    int verticesSize();

    /**
     * 添加一个顶点
     * @param k
     */
    void addVertex(K k);

    /**
     * 添加一条无权值的边
     * @param from
     * @param to
     */
    void addEdge(K from, K to);

    /**
     * 添加一条带权值的边
     * @param from
     * @param to
     * @param weight
     */
    void addEdge(K from, K to, E weight);

    /**
     * 删除一个顶点
     * @param k
     */
    void removeVertex(K k);

    /**
     * 删除一条边
     * @param from
     * @param to
     */
    void removeEdge(K from, K to);
}

创建Graph接口的实现类，实现各方法

package com.shg.graph;

import java.util.*;

/**
 * @author: shg
 * @create: 2022-05-17 4:21 下午
 */
public class ListGraph<K, E> implements Graph<K, E> {
    private Map<K, Vertex<K, E>> vertices;
    private Set<Edge<K, E>> edges;

    public ListGraph() {
        vertices = new HashMap<>();
        edges = new HashSet<>();
    }

    public void print() {
        vertices.forEach((k, vertex) -> {
            System.out.println(k + "->" + vertex);
        });

        edges.forEach(System.out::println);
    }

    @Override
    public int edgesSize() {
        return edges.size();
    }

    @Override
    public int verticesSize() {
        return vertices.size();
    }

    @Override
    public void addVertex(K k) {
        vertices.put(k, new Vertex<>(k));
    }

    @Override
    public void addEdge(K from, K to) {
        addEdge(from, to, null);
    }

    @Override
    public void addEdge(K from, K to, E weight) {
        Vertex<K, E> fromVertex = vertices.get(from);
        if (fromVertex == null) {
            fromVertex = new Vertex<>(from);
            vertices.put(from, fromVertex);
        }

        Vertex<K, E> toVertex = vertices.get(to);
        if (toVertex == null) {
            toVertex = new Vertex<>(to);
            vertices.put(to, toVertex);
        }

        Edge<K, E> edge = new Edge<>(weight, fromVertex, toVertex);
        if (fromVertex.outEdges.remove(edge)) {
            toVertex.inEdges.remove(edge);
        }
        fromVertex.outEdges.add(edge);
        toVertex.inEdges.add(edge);
        edges.add(edge);
    }

    @Override
    public void removeVertex(K k) {
        Vertex<K, E> vertex = vertices.remove(k);
        if (vertex == null) return;
        Iterator<Edge<K, E>> iterator = vertex.inEdges.iterator();
        while (iterator.hasNext()) {
            Edge<K, E> edge = iterator.next();
            edge.from.outEdges.remove(edge);
            iterator.remove();
            edges.remove(edge);
        }
        iterator = vertex.outEdges.iterator();
        while (iterator.hasNext()) {
            Edge<K, E> edge = iterator.next();
            edge.to.inEdges.remove(edge);
            iterator.remove();
            edges.remove(edge);
        }
    }

    @Override
    public void removeEdge(K from, K to) {
        Vertex<K, E> fromVertex = vertices.get(from);
        if (fromVertex == null) return;
        Vertex<K, E> toVertex = vertices.get(to);
        if (toVertex == null) return;

        Edge<K, E> edge = new Edge<>(fromVertex, toVertex);
        if (edges.remove(edge)) {
            fromVertex.outEdges.remove(edge);
            toVertex.inEdges.remove(edge);
        }
    }

    /**
     * 图的边
     *
     * @param <K>
     * @param <E>
     */
    private static class Edge<K, E> {
        E weight;
        Vertex<K, E> from;
        Vertex<K, E> to;

        public Edge(Vertex<K, E> from, Vertex<K, E> to) {
            this(null, from, to);
        }

        public Edge(E weight, Vertex<K, E> from, Vertex<K, E> to) {
            this.weight = weight;
            this.from = from;
            this.to = to;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Edge<?, ?> edge = (Edge<?, ?>) o;
            return Objects.equals(from, edge.from) && Objects.equals(to, edge.to);
        }

        @Override
        public int hashCode() {
            return Objects.hash(from, to);
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "weight=" + weight +
                    ", from=" + from +
                    ", to=" + to +
                    '}';
        }
    }

    /**
     * 图的定点
     *
     * @param <K>
     * @param <E>
     */
    private static class Vertex<K, E> {
        K key;
        Set<Edge<K, E>> inEdges;
        Set<Edge<K, E>> outEdges;

        public Vertex(K key) {
            this.key = key;
            this.inEdges = new HashSet<>();
            this.outEdges = new HashSet<>();
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Vertex<?, ?> vertex = (Vertex<?, ?>) o;
            return Objects.equals(key, vertex.key);
        }

        @Override
        public int hashCode() {
            return Objects.hash(key);
        }

        @Override
        public String toString() {
            return key.toString();
        }
    }

    @Override
    public String toString() {
        return "ListGraph{" +
                "vertices=" + vertices +
                ", edges=" + edges +
                '}';
    }
}

---

图数据结构与算法文章汇总

graph——图数据结构基础

graph——图生成器