简单图（simple graph）的原理及其实现（java）

  简单图（simple graph）：既不包含平行边，也没有自环的图。
Operation

    Graph(int v);  // Create empty graph with v vertices
    public void addEdge(int v, int w);  // add an edge v-w
    Iterable<Integer> adj(int v);  // vertices adjacent to v
    public int V();  // number of vertices
    public int E();  // number of edges

底层实现
  使用邻接List存放与各个顶点邻接的点。

java代码

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

public class Graph {
    private List<Integer>[] ver;

    Graph(int v) {
        /* Create empty graph with v vertices
         */
        ver = new List[v];
    }

    public void addEdge(int v, int w) {
        /* add an edge v-w
         */
        if (ver[v - 1] == null) {
            ver[v - 1] = new ArrayList<>();
        }
        if (ver[w - 1] == null) {
            ver[w - 1] = new ArrayList<>();
        }
        ver[v - 1].add(w);
        ver[w - 1].add(v);
    }

    Iterable<Integer> adj(int v) {
        /* vertices adjacent to v
         */
        return ver[v];
    }

    public int V() {
        /* number of vertices
         */
        return ver.length;
    }

    public int E() {
        /* number of edges
         */
        int res = 0;
        for (int i = 0; i < ver.length; i++) {
            res += ver[i].size();
        }
        return res / 2;
    }

    public static void main(String[] args) {
        Graph test = new Graph(5);
        test.addEdge(1, 2);
        test.addEdge(2, 3);
        test.addEdge(3, 4);
        test.addEdge(4, 5);
        test.addEdge(5, 2);
        test.addEdge(5, 1);
        for (int i = 0; i < test.V(); i++) {
            System.out.println("和" + (i + 1) + "邻接的顶点为：" + test.adj(i));
        }
        System.out.println("顶点的数量：" + test.V());   // 顶点的数量应该为5
        System.out.println("边的的数量：" + test.E());   // 边的数量应该为6
    }
}

To be a sailor of the world bound for all ports.