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 类定义为抽象类。
假设所有这些接口和类都可用。下面的代码给出了一个测试程序，该程序创建上图所示的图形以及下图 (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]表示从顶点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<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（第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）中分别介绍。
以上就是建模图的详细内容，更多请关注php中文网其它相关文章！
