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();
}

}

</abstractgraph.edge>登录后复制

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<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);

}

登录后复制

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, 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 &amp;&amp; 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 &gt;= 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 

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）中分别介绍。 

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