数据结构/图：图的代码实现

图的实现方式

图的实现有两种方式，矩阵和邻接链表。

图可以使用多种数据结构来实现，其中最常见的是邻接矩阵和邻接表。

1. 邻接矩阵

邻接矩阵是一个二维数组，其中数组的行和列分别表示图的顶点，如果两个顶点之间有边相连，则数组中对应位置的值为1或者边的权重，否则为0或者无穷大。由于邻接矩阵需要存储每个顶点之间的关系，因此其空间复杂度为O(n^2)，其中n为图的顶点数。邻接矩阵支持常数时间O(1)的查找两个顶点之间是否相连，但是在稀疏图中可能会浪费大量的空间。

2. 邻接表

邻接表是一个由链表组成的数组，其中数组的每个元素对应图中的一个顶点，每个元素所对应的链表存储了该顶点的所有相邻顶点。由于邻接表只需要存储每个顶点的相邻顶点，因此在稀疏图中可以大大减少空间占用。邻接表的空间复杂度为O(n+m)，其中n为图的顶点数，m为边数。但是邻接表在查找两个顶点之间是否相连时的时间复杂度为O(d)，其中d为该顶点的度数，即与该顶点相邻的顶点个数。

在实现图时，我们可以根据具体的需求和图的特性选择邻接矩阵或者邻接表。如果图是稠密图或者我们需要频繁地查找两个顶点之间是否相连，那么邻接矩阵可能是更好的选择；如果图是稀疏图或者我们需要节省空间，那么邻接表可能是更好的选择。

Java代码实现

Graph

public class Graph{
    int vertices;
    DoublyLinkedList<Integer> adjacencyList[];
    
    @SuppressWarnings("unchecked")
    public Graph(int vertices) {
        this.vertices = vertices;
        adjacencyList = new DoublyLinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjacencyList[i] = new DoublyLinkedList<>();
        }
    }

    public void addEdge(int source, int destination){
        if (source < vertices && destination < vertices){
        this.adjacencyList[source].insertAtEnd(destination);
        }
    }
    public void printGraph(){
        System.out.println(">>Adjacency List of Directed Graph<<");
        for (int i = 0; i < vertices; i++){
            if(adjacencyList[i]!=null){
                System.out.print("|" + i + "| => ");
                DoublyLinkedList<Integer>.Node temp = adjacencyList[i].getHeadNode();
                while (temp != null){
                    System.out.print("[" + temp.data + "] -> ");
                    temp = temp.nextNode;
                }
                System.out.println("null");
            }else{
                System.out.println("|" + i + "| => "+ "null");
            }
        }
    }
}

DoublyLinkedList

public class DoublyLinkedList<T> {

    public class Node {
        public T data;
        public Node nextNode;
        public Node prevNode;
    }

    public Node headNode;
    public Node tailNode;
    public int size;

    public DoublyLinkedList() {
        this.headNode = null;
        this.tailNode = null;
    }

    public boolean isEmpty() {
        if (headNode == null && tailNode == null)
            return true;
        return false;
    }

    public Node getHeadNode() {
        return headNode;
    }

    public Node getTailNode() {
        return tailNode;
    }

    public int getSize() {
        return size;
    }

    public void insertAtHead(T data) {
        Node newNode = new Node();
        newNode.data = data;
        newNode.nextNode = this.headNode; 
        newNode.prevNode = null;
        if (headNode != null)
            headNode.prevNode = newNode;
        else
            tailNode = newNode;
        this.headNode = newNode;
        size++;
    }

    public void insertAtEnd(T data) {
        if(isEmpty()) {
            insertAtHead(data);
            return;
        }
        Node newNode = new Node();
        newNode.data = data;
        newNode.nextNode = null;
        newNode.prevNode = tailNode;
        tailNode.nextNode = newNode;
        tailNode = newNode;
        size++;
    }

    public void printList() {
        if (isEmpty()) {
            System.out.println("List is Empty!");
            return;
        }
        Node temp = headNode;
        System.out.print("List : null <- ");
        while (temp.nextNode != null) {
            System.out.print(temp.data.toString() + " <-> ");
            temp = temp.nextNode;
        }
        System.out.println(temp.data.toString() + " -> null");
    }

    public void printListReverse() {
        if (isEmpty()) {
            System.out.println("List is Empty!");
        }
        Node temp = tailNode;
        System.out.print("List : null <- ");
        while (temp.prevNode != null) {
            System.out.print(temp.data.toString() + " <-> ");
            temp = temp.prevNode;
        }
        System.out.println(temp.data.toString() + " -> null");
    }

    public void deleteAtHead() {
        if (isEmpty())
            return;

        headNode = headNode.nextNode;
        if (headNode == null)
            tailNode = null;
        else
            headNode.prevNode = null;
        size--;
    }

    public void deleteAtTail() {
        if (isEmpty())
            return;
        tailNode = tailNode.prevNode;
        if (tailNode == null)
            headNode = null;
        else
            tailNode.nextNode = null;
        size--;
    }
}