文章
问答
冒泡
Dane.shang
2023-05-29阅读438
图结构实现与学习
        图形结构是一种比树形结构更复杂的非线性结构。在树形结构中，结点间具有分支层次关系，每一层上的结点只能和上一层中的至多一个结点相关，但可能和下一层的多个结点相关。而在图形结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。
        图由一堆不重复的节点和一堆不重复的边构成,任意一个节点和另一个节点之间都可能会产生边,其实说白了图就是一种网状结构.在对图结构的表达中,比较常见的就是邻接矩阵和邻接表了.

一,邻接矩阵

1,特点:

适合边比较多, 节点比较少的图
数组+数组实现
由于要初始化所有节点之间的边空间,相对来说比较浪费空间

2,JAVA实现

(1),节点Key类

public class NodeKey {

    private String key;

    private List<String> attribute = new ArrayList<>();

    public NodeKey(String... attributes) {
        initAttribute(attributes);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        NodeKey nodeKey = (NodeKey) o;
        return Objects.equals(key, nodeKey.key);
    }

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

    public String getKey() {
        return key;
    }

    public void initAttribute(String... values) {
        StringBuilder sb = new StringBuilder();
        for (String value : values) {
            this.attribute.add(value);
            sb.append(value);
        }
        this.key = DigestUtil.md5Hex(sb.toString());
    }
}

(2),节点类

@Data
public class Node<E> {

    /**
     * 节点唯一性标识
     */
    private NodeKey key;

    /**
     * 节点数据
     */
    private E data;

    public Node(E data) {
        this.data = data;
        this.key = new NodeKey(data.toString());
    }

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

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

(3),图类

public class MatrixGraph<N,W> {

    /**
     * 节点列表
     */
    private Node<N>[] nodes;

    /**
     * 矩阵
     */
    private W[][] matrix;

    /**
     * 边的数量
     */
    private int edgeNum;

    /**
     * 当前节点位置
     */
    private int index = 0;

    /**
     * 是否有向图
     */
    private boolean directed = false;

    /**
     * 初始化构造函数
     * @param nodeNum
     */

    public MatrixGraph(int nodeNum, Class<?> w,Boolean directed){
        if (w != null) {
            matrix = (W[][])(Array.newInstance(w,nodeNum,nodeNum));
        }else {
            matrix = (W[][])(Array.newInstance(Boolean.class,nodeNum,nodeNum));
        }
        nodes = new Node[nodeNum];
        if (directed != null) {
            this.directed = directed;
        }
    }

    public MatrixGraph(int nodeNum, Class<?> w){
        matrix = (W[][])(Array.newInstance(w,nodeNum,nodeNum));
        nodes = new Node[nodeNum];
    }

    public MatrixGraph(int nodeNum){
        matrix = (W[][])(Array.newInstance(Boolean.class,nodeNum,nodeNum));
        nodes = new Node[nodeNum];
    }

    /**
     * 添加1个节点
     * @param node
     */
    public int addNode(Node node){
        int t = -1;
        for (int i = 0; i < nodes.length; i++) {
            if (nodes[i] == null)
                break;
            if (node.getKey().equals(nodes[i].getKey())) {
                t = i;
                break;
            }
        }
        if (t == -1) {
            nodes[index] = node;
            index++;
            return index-1;
        }
        return t;
    }

    public void addEdge(Node start,Node end,W weight){
        start.setKey(start.getKey() == null ? new NodeKey(start.getData().toString()) : start.getKey());
        end.setKey(end.getKey() == null ? new NodeKey(end.getData().toString()) : end.getKey());
        int startIndex = addNode(start);
        int endIndex = addNode(end);
        addEdge(startIndex,endIndex,weight);
    }

    public void addEdge(Node start,Node end){
        addEdge(start,end,(W)Boolean.TRUE);
    }

    /**
     * 添加边(不带权重)
     * @param start
     * @param end
     */
    public void addEdge(NodeKey start,NodeKey end){
       addEdge(start,end, (W) Boolean.TRUE);
    }

    /**
     * 添加边(带权重)
     * @param start
     * @param end
     */
    public void addEdge(NodeKey start,NodeKey end,W weight){
        int startIndex = index(start);
        int endIndex = index(end);
        addEdge(startIndex,endIndex,weight);
    }

    private int index(NodeKey key){
        for (int i = 0; i < nodes.length; i++) {
            if (nodes[i] == null) {
                return -1;
            }
            if (Objects.equals(key, nodes[i].getKey()))
                return i;
        }

        return -1;
    }

    private void addEdge(int startIndex,int endIndex,W weight){
        if (directed) {
            matrix[startIndex][endIndex] = weight;
        }else {
            matrix[startIndex][endIndex] = weight;
            matrix[endIndex][startIndex] = weight;
        }
        edgeNum++;
    }

    public void print(){
        for (int i = 0; i <nodes.length ; i++) {
            System.out.print(nodes[i].getData().toString() + " : ");
            for (int j = 0; j < matrix[i].length; j++)
                if (matrix[i][j] != null){
                    System.out.print("-");
                    System.out.print(matrix[i][j] == null || matrix[i][j].equals(Boolean.TRUE) ? "" : matrix[i][j].toString());
                    System.out.print("->" + nodes[j].getData());
                }
            System.out.println();
        }

//        for (Node node : nodes) {
//            System.out.print(node.getData() + " | ");
//        }
//        System.out.println();
//        for (int i = 0; i < matrix.length; i++) {
//            for (int j = 0; j < matrix[i].length; j++) {
//                System.out.print(matrix[i][j]+" | ");
//            }
//            System.out.println();
//        }
    }
}

(4),单元测试

@Test
void matrixGraph() {
    // 有向图带权重
    System.out.println("有向图带权重");
    MatrixGraph graph = new MatrixGraph(3,Integer.class,true);
    graph.addEdge(new Node<>("aaa"),new Node<>("bbb"),100);
    graph.addEdge(new Node<>("aaa"),new Node<>("bbb"),23);
    graph.addEdge(new Node<>("bbb"),new Node<>("ccc"),73);
    graph.addEdge(new Node<>("ccc"),new Node<>("aaa"),37);
    graph.addEdge(new Node<>("ccc"),new Node<>("bbb"),1);
    graph.print();

    // 有向图不带权重
    System.out.println("有向图不带权重");
    MatrixGraph graph1 = new MatrixGraph(3,null,true);
    graph1.addEdge(new Node<>("aaa"),new Node<>("bbb"));
    graph1.addEdge(new Node<>("aaa"),new Node<>("bbb"));
    graph1.addEdge(new Node<>("bbb"),new Node<>("ccc"));
    graph1.addEdge(new Node<>("ccc"),new Node<>("aaa"));
    graph1.addEdge(new Node<>("ccc"),new Node<>("bbb"));
    graph1.print();

    // 无向图带权重
    System.out.println("无向图带权重");
    MatrixGraph graph2 = new MatrixGraph(3,Integer.class,false);
    graph2.addEdge(new Node<>("aaa"),new Node<>("bbb"),100);
    graph2.addEdge(new Node<>("aaa"),new Node<>("bbb"),23);
    graph2.addEdge(new Node<>("bbb"),new Node<>("ccc"),73);
    graph2.addEdge(new Node<>("ccc"),new Node<>("aaa"),37);
    graph2.addEdge(new Node<>("ccc"),new Node<>("bbb"),1);
    graph2.print();

    // 无向图不带权重
    System.out.println("无向图不带权重");
    MatrixGraph graph3 = new MatrixGraph(3,null,false);
    graph3.addEdge(new Node<>("aaa"),new Node<>("bbb"));
    graph3.addEdge(new Node<>("aaa"),new Node<>("bbb"));
    graph3.addEdge(new Node<>("bbb"),new Node<>("ccc"));
    graph3.addEdge(new Node<>("ccc"),new Node<>("aaa"));
    graph3.addEdge(new Node<>("ccc"),new Node<>("bbb"));
    graph3.print();
}

(5),测试结果

二,邻接表

 1,特点:

适合节点比较多,边比较少
数组+链表实现 | 数组+集合实现
只需要记录存在的边,所以比较节省空间

2,JAVA实现(数组+链表)

(1),图接口

public interface Graph<T,W> {

    /**
     * 添加节点
     * @param node
     */
    int addNode(T node);

    /**
     * 添加边（同时添加节点）
     * @param startNode
     * @param  endNode
     */
    void addEdge(T startNode,T endNode);

    /**
     * 添加边（同时添加节点）（带权）
     * @param startNode
     * @param  endNode
     */
    void addEdge(T startNode,T endNode,W weight);

    /**
     * 添加边
     * @param startKey
     * @param endKey
     */
    void addEdge(NodeKey startKey, NodeKey endKey,W weight) throws MissingResourceException;
}

(2),节点类

@Data
public class Node<E> {

    /**
     * 节点唯一性标识
     */
    private NodeKey key;

    /**
     * 节点数据
     */
    private E data;

    /**
     * 边链
     */
    private Edge fastEdge;

    public Node(E data) {
        this.data = data;
        this.key = new NodeKey(data.toString());
    }

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

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

(3),边类

@Data
@AllArgsConstructor
@NoArgsConstructor
public class Edge<W> {
    /**
     * 边节点位置
     */
    private int index;

    /**
     * 下一个节点
     */
    private Edge next;

    /**
     * 权值
     */
    private W weight;

    public Edge(int index) {
        this.index = index;
    }

    public Edge(int index, W weight) {
        this.index = index;
        this.weight = weight;
    }
}

(4),图类

public class ListGraph<W> implements Graph<Node,W> {

    /**
     * 节点
     */
    private List<Node> nodes = new ArrayList<>();

    /**
     * 节点数量
     */
    private int nodeNum;

    /**
     * 是否有向图
     */
    private boolean directed = true;

    public ListGraph(){}

    public ListGraph(boolean directed){
        this.directed = directed;
    }


    @Override
    public int addNode(Node node){
        int i = nodes.indexOf(node);
        if (i == -1) {
            nodes.add(node);
            nodeNum++;
            return nodes.size()-1;
        }
        return i;
    }

    @Override
    public void addEdge(Node startNode, Node endNode) {
        addEdge(startNode,endNode,null);
    }

    @Override
    public void addEdge(Node startNode, Node endNode, W weight) {
        int startIndex = addNode(startNode);
        int endIndex = addNode(endNode);

        startNode = nodes.get(startIndex);
        addEdge(startNode,endIndex,weight);
        if (!directed) {
            endNode = nodes.get(endIndex);
            addEdge(endNode, startIndex, weight);
        }
    }

    private void addEdge(Node node,int index,W weight){
        Edge fastEdge = node.getFastEdge();
        if (fastEdge == null) {
            node.setFastEdge(new Edge(index,weight));
            return;
        }
        if (fastEdge.getIndex() == index){
            fastEdge.setWeight(weight);
            return;
        }

        while (fastEdge.getNext() != null) {
            fastEdge = fastEdge.getNext();
            if (fastEdge!= null && fastEdge.getIndex() == index)
                fastEdge.setWeight(weight);
                return;
        }
        fastEdge.setNext(new Edge(index,weight));
    }
    @Override
    public void addEdge(NodeKey startKey, NodeKey endKey,W weight){
        putEdge(startKey,endKey,weight);
        if (!directed) {
            putEdge(endKey,startKey,weight);
        }
    }


    private void putEdge(NodeKey start, NodeKey endKey,W weight){
        Node startNode = null;
        int endIndex = -1;
        for (int i = 0; i <nodeNum; i++) {
            if (nodes.get(i).getKey().equals(start))
                startNode = nodes.get(i);
            if (nodes.get(i).getKey().equals(endKey))
                endIndex = i;
            if (startNode != null && endIndex != -1)
                break;
        }
        if (endIndex == -1)
            throw new MissingResourceException("节点不存在",NodeKey.class.toString(), endKey.getKey());
        if (startNode == null)
            throw new MissingResourceException("节点不存在",NodeKey.class.toString(), start.getKey());
        Edge next = startNode.getFastEdge();
        if (next == null) {
            startNode.setFastEdge(new Edge(endIndex));
            return;
        }
        if (next.getIndex() == endIndex)
            return;
        while (next.getNext() != null) {
            if (next.getIndex() == endIndex) {
                return;
            }
            next = next.getNext();
        }
        next.setNext(new Edge(endIndex,weight));
    }

    /**
     * 获取每个边的连接
     */
    public void print(){
        for (Node node : nodes) {
            System.out.print(node.getData());
            Edge edge = node.getFastEdge();
            if (edge == null) {
                continue;
            }
            System.out.print("-");
            System.out.print(edge.getWeight() != null ? edge.getWeight() : "");
            System.out.print("->"+nodes.get(edge.getIndex()).getData());
            while (edge.getNext() != null) {
                edge = edge.getNext();
                System.out.print("-");
                System.out.print(edge.getWeight() != null ? edge.getWeight() : "");
                System.out.print("->"+nodes.get(edge.getIndex()).getData());
            }
            System.out.println();
        }
    }
}

(5),单元测试

@Test
void list1Graph() {
    // 有向图带权重
    System.out.println("有向图带权重");
    ListGraph listGraph = new ListGraph();
    listGraph.addEdge(new com.dane.graph.list.Node<>("aaa"),new com.dane.graph.list.Node<>("bbb"),100);
    listGraph.addEdge(new com.dane.graph.list.Node<>("aaa"),new com.dane.graph.list.Node<>("bbb"),23);
    listGraph.addEdge(new com.dane.graph.list.Node<>("bbb"),new com.dane.graph.list.Node<>("ccc"),73);
    listGraph.addEdge(new com.dane.graph.list.Node<>("ccc"),new com.dane.graph.list.Node<>("aaa"),37);
    listGraph.addEdge(new com.dane.graph.list.Node<>("ccc"),new com.dane.graph.list.Node<>("bbb"),1);
    listGraph.print();


    // 有向图不带权重
    System.out.println("有向图不带权重");
    ListGraph listGraph1 = new ListGraph();
    listGraph1.addEdge(new com.dane.graph.list.Node<>("aaa"),new com.dane.graph.list.Node<>("bbb"));
    listGraph1.addEdge(new com.dane.graph.list.Node<>("aaa"),new com.dane.graph.list.Node<>("bbb"));
    listGraph1.addEdge(new com.dane.graph.list.Node<>("bbb"),new com.dane.graph.list.Node<>("ccc"));
    listGraph1.addEdge(new com.dane.graph.list.Node<>("ccc"),new com.dane.graph.list.Node<>("aaa"));
    listGraph1.addEdge(new com.dane.graph.list.Node<>("ccc"),new com.dane.graph.list.Node<>("bbb"));
    listGraph1.print();


    // 无向图带权重
    System.out.println("无向图带权重");
    ListGraph listGraph2 = new ListGraph(false);
    listGraph2.addEdge(new com.dane.graph.list.Node<>("aaa"),new com.dane.graph.list.Node<>("bbb"),100);
    listGraph2.addEdge(new com.dane.graph.list.Node<>("aaa"),new com.dane.graph.list.Node<>("bbb"),23);
    listGraph2.addEdge(new com.dane.graph.list.Node<>("bbb"),new com.dane.graph.list.Node<>("ccc"),73);
    listGraph2.addEdge(new com.dane.graph.list.Node<>("ccc"),new com.dane.graph.list.Node<>("aaa"),37);
    listGraph2.addEdge(new com.dane.graph.list.Node<>("ccc"),new com.dane.graph.list.Node<>("bbb"),1);
    listGraph2.print();

    // 无向图不带权重
    System.out.println("无向图不带权重");
    ListGraph listGraph3 = new ListGraph(false);
    listGraph3.addEdge(new com.dane.graph.list.Node<>("aaa"),new com.dane.graph.list.Node<>("bbb"));
    listGraph3.addEdge(new com.dane.graph.list.Node<>("aaa"),new com.dane.graph.list.Node<>("bbb"));
    listGraph3.addEdge(new com.dane.graph.list.Node<>("bbb"),new com.dane.graph.list.Node<>("ccc"));
    listGraph3.addEdge(new com.dane.graph.list.Node<>("ccc"),new com.dane.graph.list.Node<>("aaa"));
    listGraph3.addEdge(new com.dane.graph.list.Node<>("ccc"),new com.dane.graph.list.Node<>("bbb"));
    listGraph3.print();
}

(6),测试结果

2,JAVA实现(数组+集合)

(1),节点类

@Data
public class Node<E> {

    /**
     * 节点唯一性标识
     */
    private NodeKey key;

    /**
     * 节点数据
     */
    private E data;

    public Node(E data) {
        this.data = data;
        this.key = new NodeKey(data.toString());
    }

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

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

(2),边类

@Data
@NoArgsConstructor
public class Edge<W> {
    /**
     * 边节点位置
     */
    private NodeKey start,end;

    /**
     * 权值
     */
    private W weight;

    public Edge(NodeKey start,NodeKey end) {
        this.start = start;
        this.end = end;
    }

    public Edge(NodeKey start,NodeKey end,W weight){
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    @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(start, edge.start) && Objects.equals(end, edge.end);
    }

    @Override
    public int hashCode() {
        return Objects.hash(start, end);
    }
}

(3),图类

public class ListGraph<W> implements Graph<Node,W> {

    /**
     * 节点
     */
    private Map<NodeKey,Node> nodes = new HashMap<>();

    /**
     * 节点数量
     */
    private int nodeNum;

    /**
     * 是否有向图
     */
    private boolean directed = true;

    /**
     * 边集合
     */
    private Set<Edge> edges = new HashSet<>();


    public ListGraph(){}

    public ListGraph(boolean directed){
        this.directed = directed;
    }

    @Override
    public int addNode(Node node){
        if (nodes.putIfAbsent(node.getKey(),node) == null) {
            nodeNum++;
        }
        return 0;
    }

    @Override
    public void addEdge(Node startNode, Node endNode) {
        addEdge(startNode,endNode,null);
    }

    @Override
    public void addEdge(Node startNode, Node endNode, W weight) {
        addNode(startNode);
        addNode(endNode);
        addEdge(startNode.getKey(),endNode.getKey(),weight);
    }

    @Override
    public void addEdge(NodeKey startKey, NodeKey endKey,W weight){
        if (!nodes.containsKey(startKey)){
            throw new MissingResourceException("节点不存在",NodeKey.class.toString(),startKey.getKey());
        }
        if (!nodes.containsKey(endKey)) {
            throw new MissingResourceException("节点不存在",NodeKey.class.toString(),endKey.getKey());
        }
        Edge edge = new Edge(startKey, endKey, weight);
        if(!edges.add(edge)) {
            edges.remove(edge);
            edges.add(edge);
        }
        if (!directed) {
            Edge edgeDirected = new Edge(endKey, startKey, weight);
            if(!edges.add(edgeDirected)) {
                edges.remove(edgeDirected);
                edges.add(edgeDirected);
            }
        }
    }

    public void print(){
        for (Map.Entry<NodeKey,Node> entry : nodes.entrySet()) {
            Node node = entry.getValue();
            System.out.print(node.getData());
            for (Edge edge : edges) {
                if (edge.getStart().equals(entry.getKey())) {
                    System.out.print("-");
                    if (edge.getWeight() != null) {
                        System.out.print(edge.getWeight().toString());
                    }
                    System.out.print("->" + nodes.get(edge.getEnd()).getData());
                }
            }
            System.out.println();
        }
    }
}

(4),单元测试

@Test
void list2Graph() {
    // 有向图带权重
    System.out.println("有向图带权重");
    com.dane.graph.list2.ListGraph listGraph = new com.dane.graph.list2.ListGraph();
    listGraph.addEdge(new com.dane.graph.list2.Node<>("aaa"),new com.dane.graph.list2.Node<>("bbb"),100);
    listGraph.addEdge(new com.dane.graph.list2.Node<>("aaa"),new com.dane.graph.list2.Node<>("bbb"),23);
    listGraph.addEdge(new com.dane.graph.list2.Node<>("bbb"),new com.dane.graph.list2.Node<>("ccc"),73);
    listGraph.addEdge(new com.dane.graph.list2.Node<>("ccc"),new com.dane.graph.list2.Node<>("aaa"),37);
    listGraph.addEdge(new com.dane.graph.list2.Node<>("ccc"),new com.dane.graph.list2.Node<>("bbb"),1);
    listGraph.print();


    // 有向图不带权重
    System.out.println("有向图不带权重");
    com.dane.graph.list2.ListGraph listGraph1 = new com.dane.graph.list2.ListGraph();
    listGraph1.addEdge(new com.dane.graph.list2.Node<>("aaa"),new com.dane.graph.list2.Node<>("bbb"));
    listGraph1.addEdge(new com.dane.graph.list2.Node<>("aaa"),new com.dane.graph.list2.Node<>("bbb"));
    listGraph1.addEdge(new com.dane.graph.list2.Node<>("bbb"),new com.dane.graph.list2.Node<>("ccc"));
    listGraph1.addEdge(new com.dane.graph.list2.Node<>("ccc"),new com.dane.graph.list2.Node<>("aaa"));
    listGraph1.addEdge(new com.dane.graph.list2.Node<>("ccc"),new com.dane.graph.list2.Node<>("bbb"));
    listGraph1.print();


    // 无向图带权重
    System.out.println("无向图带权重");
    com.dane.graph.list2.ListGraph listGraph2 = new com.dane.graph.list2.ListGraph(false);
    listGraph2.addEdge(new com.dane.graph.list2.Node<>("aaa"),new com.dane.graph.list2.Node<>("bbb"),100);
    listGraph2.addEdge(new com.dane.graph.list2.Node<>("aaa"),new com.dane.graph.list2.Node<>("bbb"),23);
    listGraph2.addEdge(new com.dane.graph.list2.Node<>("bbb"),new com.dane.graph.list2.Node<>("ccc"),73);
    listGraph2.addEdge(new com.dane.graph.list2.Node<>("ccc"),new com.dane.graph.list2.Node<>("aaa"),37);
    listGraph2.addEdge(new com.dane.graph.list2.Node<>("ccc"),new com.dane.graph.list2.Node<>("bbb"),1);
    listGraph2.print();

    // 无向图不带权重
    System.out.println("无向图不带权重");
    com.dane.graph.list2.ListGraph listGraph3 = new com.dane.graph.list2.ListGraph(false);
    listGraph3.addEdge(new com.dane.graph.list2.Node<>("aaa"),new com.dane.graph.list2.Node<>("bbb"));
    listGraph3.addEdge(new com.dane.graph.list2.Node<>("aaa"),new com.dane.graph.list2.Node<>("bbb"));
    listGraph3.addEdge(new com.dane.graph.list2.Node<>("bbb"),new com.dane.graph.list2.Node<>("ccc"));
    listGraph3.addEdge(new com.dane.graph.list2.Node<>("ccc"),new com.dane.graph.list2.Node<>("aaa"));
    listGraph3.addEdge(new com.dane.graph.list2.Node<>("ccc"),new com.dane.graph.list2.Node<>("bbb"));
    listGraph3.print();
}

(5),测试结果

其他的一些图的遍历、求出度入度比较简单,这里就不做演示了.

 

GRAPH
关于作者
Dane.shang
快30岁了还没去过酒吧
获得点赞
文章被阅读