Java图实现

1package MyGraphDemo;
2
3import java.util.ArrayList;
4import java.util.Arrays;
5import java.util.Collections;
6import java.util.LinkedList;
7import java.util.List;
8import java.util.Scanner;
9
10/**
11 * MyGraphDemo
12 */
13public class MyGraphDemo {
14    public static void main(String[] args) {
15        Scanner in = new Scanner(System.in);
16        MyGraph<Integer> gra = new MyGraph<Integer>();
17        gra.add(null, 0, 1);
18        gra.add(0, 1, 1);
19        gra.add(0, 2, 1);
20        gra.add(0, 3, 1);
21        gra.add(1, 2, 1);
22        gra.add(2, 3, 1);
23        gra.testString();
24        // List<MyGraph<Integer>.Vertex> list = gra.BFS(0, 3);
25        // for (MyGraph<Integer>.Vertex var : list) {
26        //     System.out.print(var.data);
27        // }
28        int[][] a = gra.toAssociationMatrix();
29        for (int i = 0; i < 4; i++) {
30            System.out.println(Arrays.toString(a[i]));
31        }
32        in.close();
33    }
34}
35
36/**
37 * MyGraph
38 * Vertex中存放顶点的信息，以及连接点列表
39 * Edge中存放权重，和与之连接点在VertexList中的索引
40 */
41class MyGraph<T extends Comparable> {
42    List<Vertex> vertexList;
43    List<EdgeNoPath> edgeList;
44    MyGraph() {
45        this.vertexList = new LinkedList<Vertex>();
46        this.edgeList = new LinkedList<EdgeNoPath>();
47    }
48    // 顶点类
49    class Vertex {
50        T data;
51        List<Edge> link;
52        Vertex() {}
53        Vertex(T data) {
54            link = new LinkedList<Edge>();
55            this.data = data;
56        }
57    }
58    // 边类
59    class Edge {
60        int prev;
61        int index;
62        int weight;
63        Edge(int index, int weight, int prev) {
64            this.prev = prev;
65            this.index = index;
66            this.weight = weight;
67        }
68    }
69    class EdgeNoPath {
70        int[] index;
71        int weight;
72        EdgeNoPath(int index1, int index2, int weight) {
73            boolean is = true;
74            for (int i = 0; i < edgeList.size(); i++) {
75                if((edgeList.get(i).index[0] == index1 && edgeList.get(i).index[1] == index2) || (edgeList.get(i).index[0] == index2 && edgeList.get(i).index[1] == index1)) {
76                    is = false;
77                    break;
78                }
79            }
80            if(is) {
81                this.weight = weight;
82                this.index = new int[2];
83                this.index[0] = index1;
84                this.index[1] = index2;
85            }
86        }
87    }
88    /**
89     * 添加顶点
90     * @param prevData  连接的上一个顶点的数据
91     * @param nextData  连接的上一个顶点的数据
92     * @param weight    边的权重
93     */
94    public void add(T prevData, T nextData, int weight) {
95        if(prevData == null && vertexList.size() == 0) {
96            vertexList.add(new Vertex(nextData));
97            return;
98        } else if(prevData == null && vertexList.size() != 0) {
99            return;
100        }
101        // 定位上一个节点
102        int prev_index = this.getIndexFromData(prevData);
103        int next_index = this.getIndexFromData(nextData);
104        Vertex new_vertex;
105        if(next_index == -1) {
106            new_vertex = new Vertex(nextData);
107            // 将新节点添加到顶点列表中
108            vertexList.add(new_vertex);
109            next_index = vertexList.size()-1;
110        } else {
111            new_vertex = vertexList.get(next_index);
112        }
113        // 将边的信息添加到新节点
114        new_vertex.link.add(new Edge(prev_index, weight, next_index));
115        // 将边的信息添加到上一个节点
116        vertexList.get(prev_index).link.add(new Edge(next_index, weight, prev_index));
117        edgeList.add(new EdgeNoPath(prev_index, next_index, weight));
118    }
119    /**
120     * 获取制定data的顶点在顶点列表中的索引
121     * @param data 要进行搜索的数据
122     * @return     返回当前数据的顶点在顶点邻接表的索引，若未找到就返回 -1
123     */
124    public int getIndexFromData(T data) {
125        int i = -1;
126        while(vertexList.size() > i+1) {
127            if(vertexList.get(i+1).data.compareTo(data) == 0) {
128                i++;
129                return i;
130            }
131            i++;
132        }
133        return -1;
134    }
135    // public int vertexOfEdge(T data) {
136
137    // }
138    public void testString() {
139        for (Vertex var : vertexList) {
140            System.out.print(var.data.toString() + ",");
141            for (Edge v : var.link) {
142                System.out.print(vertexList.get(v.index).data.toString()+" ");
143            }
144            System.out.println();
145        }
146    }
147    // 深度优先搜索 - 递归隐藏方法
148    private boolean DFS(Vertex vertex, T data, List<Vertex> list, boolean[] visited) {
149        if(vertex == null) return false;
150        if(vertex.data.compareTo(data) == 0) {
151            list.add(vertex);
152            return true;
153        }
154        for (int i = vertex.link.size()-1; i >= 0; i--) {
155            int ver_index = vertex.link.get(i).index;
156            if(!visited[ver_index]) {
157                Vertex tempVertex = vertexList.get(ver_index);
158                visited[ver_index] = true;
159                boolean is = DFS(tempVertex, data, list, visited);
160                if(is) {
161                    list.add(vertex);
162                    return true;
163                }
164                visited[ver_index] = false;
165            }
166        }
167        return false;
168    }
169    /**
170     * 深度优先搜索进行路径查找
171     * @param startData 起点
172     * @param Enddata   终点
173     * @return          返回路径的点列表
174     */
175    public List<Vertex> DFS(T startData, T endData) {
176        int start_index = this.getIndexFromData(startData);
177        boolean[] visited = new boolean[vertexList.size()];
178        visited[start_index] = true;
179        List<Vertex> list = new ArrayList<Vertex>();
180        DFS(vertexList.get(start_index), endData, list, visited);
181        Collections.reverse(list);
182        return list;
183    }
184    /**
185     * 广度优先搜索进行路径查找
186     * @param startData 起点
187     * @param Enddata   终点
188     * @return          返回路径的点列表
189     */
190    public List<Vertex> BFS(T startData, T endData) {
191        int start_index = this.getIndexFromData(startData);
192        BFS_Node endNode = null;
193        List<BFS_Node> queue = new LinkedList<BFS_Node>();
194        queue.add(new BFS_Node(vertexList.get(start_index), null));
195        while (!queue.isEmpty()) {
196            BFS_Node currentNode = queue.remove(0);
197            if(currentNode.vertex.data.compareTo(endData) == 0) {
198                endNode = currentNode;
199                break;
200            }
201            for (int i = 0; i < currentNode.vertex.link.size(); i++) {
202                queue.add(new BFS_Node(vertexList.get(currentNode.vertex.link.get(i).index), currentNode));
203            }
204        }
205        List<Vertex> list = new LinkedList<Vertex>();
206        while (endNode != null) {
207            list.add(endNode.vertex);
208            endNode = endNode.parent;
209        }
210        Collections.reverse(list);
211        return list;
212    }
213    // 广度优先搜索进行路径追踪需要的类
214    class BFS_Node {
215        Vertex vertex;
216        BFS_Node parent;
217        BFS_Node(Vertex vertex, BFS_Node parent) {
218            this.vertex = vertex;
219            this.parent = parent;
220        }
221    }
222
223    /**
224     * 将顶点列表转换为顶点数组
225     * @return 顶点数组
226     */
227    public Object[] toArraysVertex() {
228        Object[] vertexs = vertexList.toArray();
229        return vertexs;
230    }
231    /**
232     * 将邻接表的图转换为邻接矩阵
233     * @return 邻接矩阵数组
234     */
235    public int[][] toAdjacencyMatrix() {
236        int vertexSize = vertexList.size();
237        int[][] matrix = new int[vertexSize][vertexSize];
238        for (int i = 0; i < vertexSize; i++) {
239            Vertex currentVertex = vertexList.get(i);
240            for (int j = 0; j < currentVertex.link.size(); j++) {
241                Edge currentEdge = currentVertex.link.get(j);
242                matrix[i][currentEdge.index] = currentEdge.weight;
243            }
244        }
245        return matrix;
246    }
247
248    /**
249     * 将邻接表图转换为关联矩阵
250     * @return 关联矩阵数组
251     */
252    public int[][] toAssociationMatrix() {
253        int vertexSize = vertexList.size();
254        int edgeSize = edgeList.size();
255        int[][] matrix = new int[vertexSize][edgeSize];
256        for (int j = 0; j < edgeSize; j++) {
257            EdgeNoPath currentEdge = edgeList.get(j);
258            matrix[currentEdge.index[0]][j]++;
259            matrix[currentEdge.index[1]][j]++;
260        }
261        return matrix;
262    }
263}