建模图

graph 接口定义了图的常用操作。 java 集合框架是设计复杂数据结构的一个很好的例子。数据结构的共同特征在接口中定义（例如collection、set、list、queue），如图20.1所示。抽象类（例如，abstractcollection、abstractset、abstractlist）部分实现了接口。具体类（例如，hashset、linkedhashset、treeset、arraylist、linkedlist、priorityqueue）提供具体的实现。这种设计模式对于图形建模很有用。我们将定义一个名为 graph 的接口，其中包含图的所有常见操作，以及一个名为 abstractgraph 的抽象类，它部分实现 graph 接口。许多具体的图表可以添加到设计中。例如，我们将定义名为unweightedgraph和weightedgraph的图。这些接口和类的关系如下图所示。

图表的常见操作有哪些？一般来说，您需要获取图中的顶点数量，获取图中的所有顶点，获取指定索引的顶点对象，获取指定名称的顶点的索引，获取顶点的邻居，获取顶点的度数，清除图，添加新顶点，添加新边，执行深度优先搜索，并执行广度优先搜索。深度优先搜索和广度优先搜索将在下一节中介绍。下图在 uml 图中说明了这些方法。

abstractgraph没有引入任何新方法。顶点列表和边邻接列表在 abstractgraph 类中定义。有了这些数据字段，就足以实现 graph 接口中定义的所有方法。为了方便起见，我们假设该图是一个简单图，即一个顶点本身没有边，并且从顶点 u 到 v 没有平行边。

abstractgraph 实现了graph 中的所有方法，除了方便的 addedge(edge) 方法（将 edge 对象添加到邻接边列表）之外，它没有引入任何新方法。 unweightedgraph 只是用五个构造函数扩展了 abstractgraph，用于创建具体的 graph 实例。

您可以创建具有任何类型顶点的图形。每个顶点都与一个索引相关联，该索引与顶点列表中该顶点的索引相同。如果您创建图形时未指定顶点，则顶点与其索引相同。

abstractgraph类实现了graph接口中的所有方法。那么为什么它被定义为抽象呢？将来，您可能需要向 graph 接口添加无法在 abstractgraph 中实现的新方法。为了使类易于维护，最好将 abstractgraph 类定义为抽象类。

可图大模型

可图大模型（Kolors）是快手大模型团队自研打造的文生图AI大模型

下载

假设所有这些接口和类都可用。下面的代码给出了一个测试程序，该程序创建上图所示的图形以及下图 (a) 中的另一个图形。

public class testgraph {

    public static void main(string[] args) {
        string[] vertices = {"seattle", "san francisco", "los angeles", "denver", "kansas city", "chicago", "boston", "new york", "atlanta", "miami", "dallas", "houston"};

        // edge array for graph
        int[][] edges = {
                {0, 1}, {0, 3}, {0, 5},
                {1, 0}, {1, 2}, {1, 3},
                {2, 1}, {2, 3}, {2, 4}, {2, 10},
                {3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5},
                {4, 2}, {4, 3}, {4, 5}, {4, 7}, {4, 8}, {4, 10},
                {5, 0}, {5, 3}, {5, 4}, {5, 6}, {5, 7},
                {6, 5}, {6, 7},
                {7, 4}, {7, 5}, {7, 6}, {7, 8},
                {8, 4}, {8, 7}, {8, 9}, {8, 10}, {8, 11},
                {9, 8}, {9, 11},
                {10, 2}, {10, 4}, {10, 8}, {10, 11},
                {11, 8}, {11, 9}, {11, 10}
        };

        graph graph1 = new unweightedgraph<>(vertices, edges);
        system.out.println("the number of vertices in graph1: " + graph1.getsize());
        system.out.println("the vertex with index 1 is " + graph1.getvertex(1));
        system.out.println("the index for miami is " + graph1.getindex("miami"));
        system.out.println("the edges for graph1:");
        graph1.printedges();

        // list of edge objects for graph
        string[] names = {"peter", "jane", "mark", "cindy", "wendy"};
        java.util.arraylist edgelist = new java.util.arraylist<>();
        edgelist.add(new abstractgraph.edge(0, 2));
        edgelist.add(new abstractgraph.edge(1, 2));
        edgelist.add(new abstractgraph.edge(2, 4));
        edgelist.add(new abstractgraph.edge(3, 4));
        // create a graph with 5 vertices
        graph graph2 = new unweightedgraph<>(java.util.arrays.aslist(names), edgelist);
        system.out.println("\nthe number of vertices in graph2: " + graph2.getsize());
        system.out.println("te edges for graph2:");
        graph2.printedges();
    }

}

graph1 中的顶点数量：12
索引为 1 的顶点是旧金山
迈阿密的指数是9
图 1 的边：
西雅图 (0): (0, 1) (0, 3) (0, 5)
旧金山 (1): (1, 0) (1, 2) (1, 3)
洛杉矶 (2): (2, 1) (2, 3) (2, 4) (2, 10)
丹佛 (3): (3, 0) (3, 1) (3, 2) (3, 4) (3, 5)
堪萨斯城 (4): (4, 2) (4, 3) (4, 5) (4, 7) (4, 8) (4, 10)
芝加哥 (5): (5, 0) (5, 3) (5, 4) (5, 6) (5, 7)
波士顿 (6): (6, 5) (6, 7)
纽约 (7): (7, 4) (7, 5) (7, 6) (7, 8)
亚特兰大 (8): (8, 4) (8, 7) (8, 9) (8, 10) (8, 11)
迈阿密 (9): (9, 8) (9, 11)
达拉斯 (10): (10, 2) (10, 4) (10, 8) (10, 11)
休斯顿 (11): (11, 8) (11, 9) (11, 10)

graph2 中的顶点数量：5
graph2 的边：
彼得 (0): (0, 2)
简 (1): (1, 2)
马克 (2): (2, 4)
辛迪 (3): (3, 4)
温蒂 (4):

程序为图 28.1 中的第 3-23 行中的图表创建 graph1。 graph1 的顶点在第 3-5 行中定义。 graph1 的边在 8-21 中定义。边缘使用二维数组表示。对于数组中的每一行i，edges[i][0]和edges[i][1]表示从顶点edges[i][0]到顶点edges有一条边[我][1]。例如，第一行 {0, 1} 表示从顶点 0 (edges[0][0]) 到顶点 1 (edges[0][1]) 的边）。行 {0, 5} 表示从顶点 0 (edges[2][0]) 到顶点 5 (edges[2][1]) 的边。该图在第 23 行中创建。第 31 行调用 graph1 上的 printedges() 方法来显示 graph1.

程序为图 28.3a 中第 34-43 行的图创建 graph2。 graph2 的边在第 37-40 行中定义。 graph2 是使用第 43 行中的 edge 对象列表创建的。第 47 行调用 graph2 上的 printedges() 方法来显示 graph2 中的所有边。

注意graph1和graph2都包含字符串的顶点。顶点与索引 0、1、 相关联。 。 。 ，n-1。索引是顶点在vertices中的位置。例如，顶点miami的索引是9.

现在我们将注意力转向实现接口和类。下面的代码分别给出了graph接口、abstractgraph类和unweightedgraph类。

public interface graph {
    /** return the number of vertices in the graph */
    public int getsize();

    /** return the vertices in the graph */
    public java.util.list getvertices();

    /** return the object for the specified vertex index */
    public v getvertex(int index);

    /** return the index for the specified vertex object */
    public int getindex(v v);

    /** return the neighbors of vertex with the specified index */
    public java.util.list getneighbors(int index);

    /** return the degree for a specified vertex */
    public int getdegree(int v);

    /** print the edges */
    public void printedges();

    /** clear the graph */
    public void clear();

    /** add a vertex to the graph */
    public void addvertex(v vertex);

    /** add an edge to the graph */
    public void addedge(int u, int v);

    /** obtain a depth-first search tree starting from v */
    public abstractgraph.tree dfs(int v);

    /** obtain a breadth-first search tree starting from v */
    public abstractgraph.tree bfs(int v);
}

import java.util.*;

public abstract class abstractgraph implements graph {
    protected list vertices = new arraylist<>(); // store vertices
    protected list> neighbors = new arraylist<>(); // adjacency lists

    /** construct an empty graph */
    protected abstractgraph() {}

    /** construct a graph from vertices and edges stored in arrays */
    protected abstractgraph(v[] vertices, int[][] edges) {
        for(int i = 0; i < vertices.length; i++)
            addvertex(vertices[i]);

        createadjacencylists(edges, vertices.length);
    }

    /** construct a graph from vertices and edges stored in list */
    protected abstractgraph(list vertices, list edges) {
        for(int i = 0; i < vertices.size(); i++)
            addvertex(vertices.get(i));

        createadjacencylists(edges, vertices.size());
    }

    /** construct a graph for integer vertices 0, 1, 2 and edge list */
    protected abstractgraph(list edges, int numberofvertices) {
        for(int i = 0; i < numberofvertices; i++)
            addvertex((v)(new integer(i))); // vertices is {0, 1, ...}

        createadjacencylists(edges, numberofvertices);
    }

    /** construct a graph from integer vertices 0, 1, and edge array */
    protected abstractgraph(int[][] edges, int numberofvertices) {
        for(int i = 0; i < numberofvertices; i++)
            addvertex((v)(new integer(i))); // vertices is {0, 1, ...}

        createadjacencylists(edges, numberofvertices);
    }

    /** create adjacency lists for each vertex */
    private void createadjacencylists(int[][] edges, int numberofvertices) {
        for(int i = 0; i < edges.length; i++) {
            addedge(edges[i][0], edges[i][1]);
        }
    }

    /** create adjacency lists for each vertex */
    private void createadjacencylists(list edges, int numberofvertices) {
        for(edge edge: edges) {
            addedge(edge.u, edge.v);
        }
    }

    @override /** return the number of vertices in the graph */
    public int getsize() {
        return vertices.size();
    }

    @override /** return the vertices in the graph */
    public list getvertices() {
        return vertices;
    }

    @override /** return the object for the specified vertex */
    public v getvertex(int index) {
        return vertices.get(index);
    }

    @override /** return the index for the specified vertex object */
    public int getindex(v v) {
        return vertices.indexof(v);
    }

    @override /** return the neighbors of the specified vertex */
    public list getneighbors(int index) {
        list result = new arraylist<>();
        for(edge e: neighbors.get(index))
            result.add(e.v);

        return result;
    }

    @override /** return the degree for a specified vertex */
    public int getdegree(int v) {
        return neighbors.get(v).size();
    }

    @override /** print the edges */
    public void printedges() {
        for(int u = 0; u < neighbors.size(); u++) {
            system.out.print(getvertex(u) + " (" + u + "): ");
            for(edge e: neighbors.get(u)) {
                system.out.print("(" + getvertex(e.u) + ", " + getvertex(e.v) + ") ");
            }
            system.out.println();
        }
    }

    @override /** clear the graph */
    public void clear() {
        vertices.clear();
        neighbors.clear();
    }

    @override /** add a vertex to the graph */
    public void addvertex(v vertex) {
        if(!vertices.contains(vertex)) {
            vertices.add(vertex);
            neighbors.add(new arraylist());
        }
    }

    /** add an edge to the graph */
    protected boolean addedge(edge e) {
        if(e.u < 0 || e.u > getsize() - 1)
            throw new illegalargumentexception("no such index: " + e.u);

        if(e.v < 0 || e.v > getsize() - 1)
            throw new illegalargumentexception("no such index: " + e.v);

        if(!neighbors.get(e.u).contains(e)) {
            neighbors.get(e.u).add(e);
            return true;
        }
        else {
            return false;
        }
    }

    @override /** add an edge to the graph */
    public void addedge(int u, int v) {
        addedge(new edge(u, v));
    }

    /** edge inner class inside the abstractgraph class */
    public static class edge {
        public int u; // starting vertex of the edge
        public int v; // ending vertex of the edge

        /** construct an edge for (u, v) */
        public edge(int u, int v) {
            this.u = u;
            this.v = v;
        }

        public boolean equals(object o) {
            return u == ((edge)o).u && v == ((edge)o).v;
        }
    }

    @override /** obtain a dfs tree starting from vertex v */
    public tree dfs(int v) {
        list searchorder = new arraylist<>();
        int[] parent = new int[vertices.size()];
        for(int i = 0; i < parent.length; i++)
            parent[i] = -1; // initialize parent[i] to -1

        // mark visited vertices
        boolean[] isvisited = new boolean[vertices.size()];

        // recursively search
        dfs(v, parent, searchorder, isvisited);

        // return a search tree
        return new tree(v, parent, searchorder);
    }

    /** recursive method for dfs search */
    private void dfs(int u, int[] parent, list searchorder, boolean[] isvisited) {
        // store the visited vertex
        searchorder.add(u);
        isvisited[u] = true; // vertex v visited

        for(edge e: neighbors.get(u)) {
            if(!isvisited[e.v]) {
                parent[e.v] = u; // the parent of vertex e.v is u
                dfs(e.v, parent, searchorder, isvisited); // recursive search
            }
        }
    }

    @override /** starting bfs search from vertex v */
    public tree bfs(int v) {
        list searchorder = new arraylist<>();
        int[] parent = new int[vertices.size()];
        for(int i = 0; i < parent.length; i++)
            parent[i] = -1; // initialize parent[i] to -1

        java.util.linkedlist queue = new java.util.linkedlist<>(); // list used as queue
        boolean[] isvisited = new boolean[vertices.size()];
        queue.offer(v); // enqueue v
        isvisited[v] = true; // mark it visited

        while(!queue.isempty()) {
            int u = queue.poll(); // dequeue to u
            searchorder.add(u); // u searched
            for(edge e: neighbors.get(u)) {
                if(!isvisited[e.v]) {
                    queue.offer(e.v); // enqueue w
                    parent[e.v] = u; // the parent of w is u
                    isvisited[e.v] = true; // mark it visited
                }
            }
        }

        return new tree(v, parent, searchorder);
    }

    /** tree inner class inside the abstractgraph class */
    public class tree {
        private int root; // the root of the tree
        private int[] parent; // store the parent of each vertex
        private list searchorder; // store the search order

        /** construct a tree with root, parent, and searchorder */
        public tree(int root, int[] parent, list searchorder) {
            this.root = root;
            this.parent = parent;
            this.searchorder = searchorder;
        }

        /** return the root of the tree */
        public int getroot() {
            return root;
        }

        /** return the parent of vertex v */
        public int getparent(int v) {
            return parent[v];
        }

        /** return an array representing search order */
        public list getsearchorder() {
            return searchorder;
        }

        /** return number of vertices found */
        public int getnumberofverticesfound() {
            return searchorder.size();
        }

        /** return the path of vertices from a vertex to the root */
        public list getpath(int index) {
            arraylist path = new arraylist<>();

            do {
                path.add(vertices.get(index));
                index = parent[index];
            }
            while(index != -1);

            return path;
        }

        /** print a path from the root vertex v */
        public void printpath(int index) {
            list path = getpath(index);
            system.out.print("a path from " + vertices.get(root) + " to " + vertices.get(index) + ": ");
            for(int i = path.size() - 1; i >= 0; i--)
                system.out.print(path.get(i) + " ");
        }

        /** print the whole tree */
        public void printtree() {
            system.out.println("root is: " + vertices.get(root));
            system.out.print("edges: ");
            for(int i = 0; i < parent.length; i++) {
                if(parent[i] != -1) {
                    // display an edge
                    system.out.print("(" + vertices.get(parent[i]) + "' " + vertices.get(i) + ") ");
                }
            }
            system.out.println();
        }
    }
}

import java.util.*;

public class UnweightedGraph extends AbstractGraph {
    /** Construct an empty graph */
    public UnweightedGraph() {}

    /** Construct a graph from vertices and edges stored in arrays */
    public UnweightedGraph(V[] vertices, int[][] edges) {
        super(vertices, edges);
    }
    /** Construct a graph from vertices and edges stored in List */
    public UnweightedGraph(List vertices, List edges) {
        super(vertices, edges);
    }

    /** Construct a graph for integer vertices 0, 1, 2, and edge list */
    public UnweightedGraph(List edges, int numberOfVertices) {
        super(edges, numberOfVertices);
    }

    /** Construct a graph from integer vertices 0, 1, and edge array */
    public UnweightedGraph(int[][] edges, int numberOfVertices) {
        super(edges, numberOfVertices);
    }
}

graph接口和unweightedgraph类中的代码很简单。让我们来消化一下 abstractgraph 类中的代码。

abstractgraph类定义数据字段vertices（第4行）来存储顶点，neighbors（第5行）来存储邻接列表中的边。 neighbors.get(i) 存储与顶点 i 相邻的所有边。第 9-42 行定义了四个重载构造函数，用于创建默认图，或者从数组或边和顶点列表创建图。 createadjacencylists(int[][] edges, int numberofvertices) 方法根据数组中的边创建邻接列表（第 45-50 行）。 createadjacencylists(list edges, int numberofvertices) 方法从列表中的边创建邻接列表（第 53-58 行）。

方法（第 81-87 行）返回与顶点 u 相邻的顶点列表。 clear() 方法（第 106-110 行）从图中删除所有顶点和边。 addvertex(u) 方法（第 112-122 行）将新顶点添加到 vertices 并返回 true。如果顶点已经在图中，则返回 false（第 120 行）。 addedge(e)

illegalargumentexception（第 126-130 行）。 printedges()

第164-293行代码给出了寻找深度优先搜索树和广度优先搜索树的方法，将在深度优先搜索（dfs）和广度优先搜索（bfs）中分别介绍。