图的表示

由 笔尖 发布

邻接矩阵(AdjMatrix)

public class AdjMatrix {
    private int V;
    private int E;
    private int[][] adj;

    public AdjMatrix(String filename) {
        File file = new File(filename);
        try (Scanner scanner = new Scanner(file)) {//建立邻接矩阵
            V = scanner.nextInt();
            if (V < 0)
                throw new IllegalArgumentException("V must be positive");
            adj = new int[V][V];
            E = scanner.nextInt();
            for (int i = 0; i < E; i++) {
                int a = scanner.nextInt();
                ValidateVertex(a);
                int b = scanner.nextInt();
                ValidateVertex(b);
                if (a == b)
                    throw new IllegalArgumentException("Self-loop founded");
                if (adj[a][b] == 1)
                    throw new IllegalArgumentException("Parallel edges founded");
                adj[a][b] = 1;
                adj[b][a] = 1;
            }

        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private void ValidateVertex(int vertex) {
        if (vertex < 0 || vertex >= V)
            throw new IllegalArgumentException("vertex " + vertex + "is invalid");
    }

    public int getV() {
        return V;
    }

    public int getE() {
        return E;
    }

    public boolean hasEdge(int a, int b) {//查找两点是否相连
        ValidateVertex(a);
        ValidateVertex(b);
        return adj[a][b] == 1;
    }

    public ArrayList<Integer> adj(int a) {//返回所有邻接顶点
        ValidateVertex(a);
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            if (adj[a][i] == 1)
                list.add(i);
        }
        return list;
    }

    public int degree(int a) {
        return adj(a).size();
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("V=%d,E=%d\n ", V, E));
        for (int i = 0; i < V; i++) {
            sb.append(String.format(" %d", i));
        }
        sb.append("\n");
        for (int i = 0; i < V; i++) {
            sb.append(i + " ");
            for (int j = 0; j < V; j++) {
                sb.append(String.format("%d ", adj[i][j]));
            }
            sb.append("\n");
        }
        return sb.toString();
    }
}

image-20200921160929926

缺点:

空间复杂度较高,对于n个顶点,最多有n*(n-1)/2条边,前提是每个顶点的度要为n-1,然而大多数情况下都比最大度的1/2还要小,因此造成了空间上的浪费,其次,查找一个点的相邻节点也是这样的道理。由此引出稀疏图。

邻接表(AdjList)

public class AdjList {
    private int V;
    private int E;
    private TreeSet<Integer>[] adj;

    public AdjList(String filename) {
        File file = new File(filename);
        try (Scanner scanner = new Scanner(file)) {
            V = scanner.nextInt();
            if (V < 0)
                throw new IllegalArgumentException("V must be positive");
            adj = new TreeSet[V];
            for (int i = 0; i < V; i++) {
                adj[i] = new TreeSet<>();
            }
            E = scanner.nextInt();
            for (int i = 0; i < E; i++) {
                int a = scanner.nextInt();
                ValidateVertex(a);
                int b = scanner.nextInt();
                ValidateVertex(b);
                if (a == b)
                    throw new IllegalArgumentException("Self-loop founded");
                if (adj[a].contains(b))
                    throw new IllegalArgumentException("Parallel edges founded");
                adj[a].add(b);
                adj[b].add(a);
            }

        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private void ValidateVertex(int vertex) {
        if (vertex < 0 || vertex >= V)
            throw new IllegalArgumentException("vertex " + vertex + "is invalid");
    }

    public int getV() {
        return V;
    }

    public int getE() {
        return E;
    }

    public boolean hasEdge(int a, int b) {
        ValidateVertex(a);
        ValidateVertex(b);
        return adj[a].contains(b);
    }

    public ArrayList<Integer> adj(int a) {
        ValidateVertex(a);
        ArrayList<Integer> list = new ArrayList();
        for (int v : adj[a])
            list.add(v);
        return list;
    }

    public int degree(int a) {
        return adj(a).size();
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("V=%d,E=%d\n", V, E));
        for (int i = 0; i < V; i++) {
            sb.append(i + ":");
            for (int v : adj[i])
                sb.append(v + " ");
            sb.append("\n");
        }
        return sb.toString();
    }
}

image-20200921165511389

性能瓶颈:建图,需要快速查重,即查找两点是否相连,解决方案如下:

image-20200921165855273

hashset更加快速,首选;红黑树,时间高了一点儿,空间更省,但却保证了节点遍历的有序性,这在分析图论算法时有较大帮助。(在TreeSet中iterator返回一个navigableKeySet().iterator(),即按照key升序返回迭代器)

image-20200921172225121

后续关于图论算法全部使用基于TreeSet的图


暂无评论

发表评论