Graph Introduction - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

public class AdjListNode {

    // 图中每个结点在邻接表的下标
    private int index;
    // 每个结点之间的权重，无权图默认为0
    private int weight;

    public AdjListNode(int index) {
        this.index = index;
        this.weight = 0;
    }

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

    public int getIndex() {
        return index;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj instanceof AdjListNode) {
            AdjListNode adjListNode = (AdjListNode)obj;
            return this.getIndex() == adjListNode.getIndex();
        } else {
            return false;
        }
    }
}

public class Node<T> {

    // 结点值
    private T data;
    // 邻接表中的头结点
    private ArrayList<AdjListNode> root;

    public Node(T data) {
        this.data = data;
        this.root = new ArrayList<>();
    }

    public void add(int index, int weight) {
        AdjListNode adjListNode = new AdjListNode(index, weight);
        // 若结点不存在，则添加结点
        if (!root.contains(adjListNode)) {
            root.add(adjListNode);
        }
        // 若结点已存在，则更新权重
        else {
            root.get(root.indexOf(adjListNode)).setWeight(weight);
        }
    }

    public void remove(int index) {
        // 要转型，否则remove的是下标为index的元素
        // override了AdjListNode的equals方法，确保index一样即代表AdjListNode一样
        root.remove(new AdjListNode(index));
    }

    public int size() {
        return root.size();
    }

    public ArrayList<AdjListNode> getRoot() {
        return root;
    }

    public T getData() {
        return data;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj instanceof Node<?>) {
            Node<?> node = (Node<?>)obj;
            return this.getData().equals(node.getData());
        } else {
            return false;
        }
    }
}

public class AdjacencyList<T> {

    private ArrayList<Node<T>> nodes;

    // 结点v的数量
    public AdjacencyList(ArrayList<Node<T>> nodes) {
        this.nodes = nodes;
    }

    public int size() {
        return nodes.size();
    }

    // 在下标为i的结点v和在下标为j的结点w之间添加一条边，权重为w
    public void addEdge(int i, int j, int w) {
        nodes.get(i).add(j, w);
    }

    // 在下标为i的结点v和在下标为j的结点w之间移除一条边
    public void removeEdge(int i, int j) {
        nodes.get(i).remove(j);
    }

    public ArrayList<Node<T>> getNodes() {
        return nodes;
    }

    public void print() {
        for (Node<T> node : nodes) {
            System.out.println("这是顶点: " + node.getData() + " 的链表: ");
            for (int j = 0; j < node.size() - 1; j++) {
                System.out.print(nodes.get(node.getRoot().get(j).getIndex()).getData() + " -> ");
            }
            if (node.size() > 0) {
                System.out.print(nodes.get(node.getRoot().get(node.size() - 1).getIndex()).getData());
            }
            System.out.println();
        }
    }
}

public class AdjacencyMatrix {

    // 邻接矩阵
    private int[][] adjMatrix;

    // n代表结点数
    public AdjacencyMatrix(int n) {
        adjMatrix = new int[n][n];
    }

    // 在结点v添加一条v与w相连的边
    // 注意：这里只是代表v指向w的边，若是无向图，就需要再调用addEdge(w, v)
    public void addEdge(int v, int w) {
        adjMatrix[v][w] = 1;
    }

    // 在结点v移除一条v与w相连的边
    // 注意：这里只是代表v指向w的边，若是无向图，就需要再调用removeEdge(w, v)
    public void removeEdge(int v, int w) {
        adjMatrix[v][w] = 0;
    }
}