建模图

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大模型

32 查看详情

假设所有这些接口和类都可用。下面的代码给出了一个测试程序，该程序创建上图所示的图形以及下图 (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<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  getsize() - 1)            throw new illegalargumentexception("no such index: " + e.u);        if(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 行）。

getneighbors(u)

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

方法（第 124-139 行）在邻接边列表中添加一条新边并返回 true。如果边已在图中，则返回 false。如果边无效，此方法可能会抛出

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

方法（第 95-104 行）显示所有顶点以及与每个顶点相邻的边。

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

以上就是建模图的详细内容，更多请关注创想鸟其它相关文章！