java之图论_java graph 图论

我们采用接口-抽象类-实体类的方式实现一个图类。
1 首先是接口类Graph,提供了图的基本操作方法

import java.util.List;
/*
 *  Interface Graph
 * /
public interface Graph<V> {
    public int getSize();   //返回这个图的结点个数
    public List<V> getVertices();   //返回图的结点
    public V getVertex(int index);  //返回下标index 对应的结点
    public int getIndex(V v);   //返回结点v对应的下标
    public List<Integer> getNeighbors(int index);//返回下标index对应的结点的相邻结点
    public int getDegree(int v);  //返回结点v的度
    public int[][] getAdjacencyMatrix();    //返回邻接距阵
    public void printAdjacencyMatrix();     //打印邻接距阵
    public void printEdges();   //打印所有的邻接表
    public AbstractGraph<V>.Tree dfs(int v);    //以结点v为根，深度优先搜索生成树
    public AbstractGraph<V>.Tree bfs(int v);    //以结点v为根，宽度优先搜索生成树
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2 其次是实现了接口的抽象类AbstractGraph

import java.util.*;
/*
 * 抽象类实现了接口 Graph<V>
 */

public abstract class AbstractGraph<V> implements Graph<V>{

    protected List<V> vertices;  //结点列表
    protected List<List<Integer> > neighbors;  //储存每个结点的相邻结点

    protected AbstractGraph(int[][] edges,V[] vertices) {
        this.vertices = new ArrayList<V>();
        for (int i = 0; i < vertices.length; i++) {
            this.vertices.add(vertices[i]);
        }
        createAdjacencyLists(edges,vertices.length);
    }
    protected AbstractGraph(List<Edge> edges,List<V> vertices){
        this.vertices = vertices;
        createAdjacencyLists(edges, vertices.size());
    }
    protected AbstractGraph(List<Edge> edges,int numOfVertices){
        this.vertices = new ArrayList<V>();
        for (int i = 0; i < numOfVertices; i++) {
            vertices.add((V)(new Integer(i)));
        }
        createAdjacencyLists(edges, numOfVertices);
    }
    protected AbstractGraph(int[][] edges,int numOfVertices){
        vertices = new ArrayList<V>();
        for (int i = 0; i < numOfVertices; i++) {
            vertices.add((V)(new Integer(i)));
        }
        createAdjacencyLists(edges, numOfVertices);
    }
    private void createAdjacencyLists(List<Edge> edges, int numOfVertices){
        neighbors = new ArrayList<List<Integer> >();
        for (int i = 0; i < numOfVertices; i++) {
            neighbors.add(new ArrayList<Integer>());            
        }
        for (Edge edge : edges) {
            neighbors.get(edge.u).add(edge.v);
        }
    }
    private void createAdjacencyLists(int[][] edges,int numOfVertices){
        neighbors = new ArrayList<List<Integer> >();
        for(int i = 0;i< numOfVertices;i++){
            neighbors.add(new ArrayList<Integer>());
        }
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            neighbors.get(u).add(v);
        }
    }
    //inner class，表示边 
    public static class Edge{
        public int u;
        public int v;
        public Edge(int u,int v){
            this.u = u;
            this.v = v;
        }
    }
    @Override
    public int getSize() {
        return vertices.size();
    }

    @Override
    public List<V> getVertices() {
        return vertices;
    }

    @Override
    public V getVertex(int index) {
        return vertices.get(index);
    }

    @Override
    public int getIndex(V v) {
        return vertices.indexOf(v);
    }

    @Override
    public List<Integer> getNeighbors(int index) {
        return neighbors.get(index);
    }

    @Override
    public int getDegree(int v) {
        return neighbors.get(v).size();
    }

    @Override
    public int[][] getAdjacencyMatrix() {
        int[][] adjacencyMatrix = new int[getSize()][getSize()];
        for (int i = 0; i < neighbors.size(); i++) {
            for (int j = 0; j < neighbors.get(i).size(); j++) {
                int v = neighbors.get(i).get(j);
                adjacencyMatrix[i][v] = 1;
            }
        }
        return adjacencyMatrix;
    }

    @Override
    public void printAdjacencyMatrix() {
        int[][] adjacencyMatrix = getAdjacencyMatrix();
        for (int i = 0; i < adjacencyMatrix.length; i++) {
            for (int j = 0; j < adjacencyMatrix[0].length; j++) {
                System.out.print(adjacencyMatrix[i][j]+" ");
            }
            System.out.println();
        }
    }

    @Override
    public void printEdges() {
        for (int u = 0; u < neighbors.size(); u++) {
            System.out.print("Vertex"+u+":");
            for (int i = 0; i < neighbors.get(u).size(); i++) {
                System.out.print("("+u+","+neighbors.get(u).get(i)+") ");
            }
            System.out.println();
        }
    }
    public Tree dfs(int v){
        List<Integer> searchOrders = new ArrayList<Integer>();
        int[] parent = new int[vertices.size()];
        for (int i = 0; i < parent.length; i++) {
            parent[i]=-1;
        }
        boolean[] isVisited = new boolean[vertices.size()];
        dfs(v,parent,searchOrders,isVisited);
        return new Tree(v,parent,searchOrders);
    }
    private void dfs(int v,int[] parent,List<Integer> searchOrders,boolean[] isVisited){
        searchOrders.add(v);
        isVisited[v] = true;
        for (int i : neighbors.get(v)) {
            if(!isVisited[i]){
                parent[i] = v;//the parent of vertex i is v
                dfs(i,parent,searchOrders,isVisited);
            }
        }
    }
    public Tree bfs(int v){
        List<Integer> searchOrders = new ArrayList<Integer>();
        int[] parent = new int[vertices.size()];
        for (int i = 0; i < parent.length; i++) {
            parent[i]=-1;
        }
        LinkedList<Integer> queue = new LinkedList<Integer>();
        boolean[] isVisited = new boolean[vertices.size()];
        queue.offer(v);
        isVisited[v]=true;
        while(!queue.isEmpty()){
            int u = queue.poll();//dequeue to u
            searchOrders.add(u);
            for (int w : neighbors.get(u)) {
                if(!isVisited[w]){
                    queue.offer(w);
                    parent[w] = u;
                    isVisited[w] = true;
                }               
            }
        }
        return new Tree(v,parent,searchOrders);
    }
    public class Tree{
        private int root;
        private int[] parent;
        private List<Integer> searchOrders;
        public Tree(int root,int[] parent, List<Integer> searchOrders){
            this.root = root;
            this.parent = parent;
            this.searchOrders = searchOrders;
        }
        public Tree(int root,int[] parent){
            this.root = root;
            this.parent = parent;
        }
        public int getRoot(){
            return root;
        }
        public int getParent(int v){
            return parent[v];
        }
        public List<Integer> getSearchOrders(){
            return searchOrders;
        }
        public int getNumberOfVerticesFound(){
            return searchOrders.size();
        }
        //return the path of vertices from a vertex index to the root
        public List<V> getPath(int index){
            ArrayList<V> path = new ArrayList<V>();
            do{
                path.add(vertices.get(index));
                index = parent[index];
            }while(index!= -1);
            return path;
        }
        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)+" ");
            }
        }
        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){
                    System.out.println("("+vertices.get(parent[i])+"."+
                            vertices.get(i)+") ");
                }
            }
            System.out.println();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226

3 接着是具体类 UnweightedGraph

import java.util.List;

/*
 *    具体类 UnweightedGraph
 */
public class UnweightedGraph<V> extends AbstractGraph<V> {

    protected UnweightedGraph(int[][] edges, int numOfVertices) {
        super(edges, numOfVertices);
    }

    public UnweightedGraph(int[][] edges, V[] vertices) {
        super(edges, vertices);
    }

    public UnweightedGraph(List<AbstractGraph.Edge> edges, int numOfVertices) {
        super(edges, numOfVertices);
    }

    public UnweightedGraph(List<AbstractGraph.Edge> edges, List<V> vertices) {
        super(edges, vertices);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

4 再写个测试类测试一下

import java.util.Arrays;


public class GraphTest {
    public static void main(String[] args) {
        String[] vertices = {"Settle","San Francisco", "los angeles",
                "denver","kansas City" ,"chicago", "Boston", "new york",
                "atlanta", "miami", "dallas", "houston"};
        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<String>(edges,vertices);
        System.out.println("the number of vertices of graph1 is "+
                graph1.getSize());
        System.out.println("the vertices 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();
        System.out.println("Adjacency matrix for graph1:");
        graph1.printAdjacencyMatrix();

        String[] names = {"Peter", "Jane", "Mark", "Cindy", "Wendy"};
        java.util.ArrayList<AbstractGraph.Edge> edgeList
            = new java.util.ArrayList<AbstractGraph.Edge>();
        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<String>(edgeList,Arrays.asList(names));
        System.out.println("The number of vertices in graph2: "
                 + graph2.getSize());
        System.out.println("The edges for graph2:");
            graph2.printEdges();
        System.out.println("\nAdjacency matrix for graph2:");
        graph2.printAdjacencyMatrix();
        for (int i = 0; i < 5; i++)
        System.out.println("vertex " + i + ": " + graph2.getVertex(i));

        int[][] edge = {
                {0,1},{0,3},{0,4},
                {1,2},{1,4},
                {2,0},{2,2},{2,4},
                {3,0},{3,2},{3,4},
                {4,0},{4,2},{4,4}
        };

        Graph<Integer> graph3 = new UnweightedGraph<Integer>(edge,5);
        System.out.println("the number of vertices in graph3: "+graph3.getSize());
        graph3.printAdjacencyMatrix();
        graph3.printEdges();


    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68