建模图
2024-08-14 11:12:02
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 实例。
您可以创建具有任何类型顶点的图形。每个顶点都与索引相关，与顶点列表中的索引相同。如果您在创建图形时没有指定顶点，则顶点与索引相同。
graph接口中的所有方法都实现了abstractgraph类。那么为什么它被定义为抽象呢？在未来，你可能需要前进 graph 不能添加接口 abstractgraph 实现的新方法。为了使类容易维护，最好是 abstractgraph 类别被定义为抽象类。
假设所有这些接口和类别都可以使用。下面的代码提供了一个创建上图和下图所示图形的测试程序 (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<string> 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<abstractgraph.edge> 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<string> 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();
}
}
</string></abstractgraph.edge></string>
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]表示从顶点edgess[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<v> {
/** return the number of vertices in the graph */
public int getsize();
/** return the vertices in the graph */
public java.util.list<v> 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<integer> 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<v>.tree dfs(int v);
/** obtain a breadth-first search tree starting from v */
public abstractgraph<v>.tree bfs(int v);
}
</v></v></integer></v></v>
import java.util.*;
public abstract class abstractgraph<v> implements graph<v> {
protected list<v> 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, list<edge> edges) {
for(int i = 0; i edges, int numberofvertices) {
for(int i = 0; i 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<v> 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<integer> getneighbors(int index) {
list<integer> 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 ());
}
}
/** 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<integer> searchorder = new arraylist();
int[] parent = new int[vertices.size()];
for(int i = 0; i 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<integer> searchorder = new arraylist();
int[] parent = new int[vertices.size()];
for(int i = 0; i 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<integer> searchorder; // store the search order
/** construct a tree with root, parent, and searchorder */
public tree(int root, int[] parent, list<integer> 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<integer> 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<v> getpath(int index) {
arraylist<v> 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<v> 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
<pre class="brush:php;toolbar:false">import java.util.*;
public class UnweightedGraph<v> extends AbstractGraph<v> {
/** 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<v> vertices, List<edge> edges) {
super(vertices, edges);
}
/** Construct a graph for integer vertices 0, 1, 2, and edge list */
public UnweightedGraph(List<edge> 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);
}
}
</edge></edge></v></v></v>
graph接口和unweightedgraph中的代码非常简单。让我们消化一下 abstractgraph 类中的代码。
abstractgraph定义数据字段vertices(第4行)存储顶点，neighbors(第五行)存储相邻列表中的边缘。 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）分别介绍。
以上是建模图的详细内容，请关注图灵教育的其他相关文章！
