import java.util.ArrayList;import java.util.Collections;import java.util.HashSet;import java.util.LinkedHashMap;import java.util.List;import java.util.Map;import java.util.Set;// 顶点类class Vertex{    String name;// 名称    boolean visited;// 是否已访问过        public Vertex(String name){        this.name=name;        this.visited=false;    }}// 图类public class Graph{    // 图    private Vertex[] arr;// 顶点数组    private int[][] matrix;// 邻接矩阵        // 建立图的数据    private Set<String> vertexSet;// 包含不重复顶点的集合    private Map<String,String[]> connMap;// 包含连接的哈希表        // 添加顶点之间的连接关系    public void addConn(String from,String[] toArr){        if(vertexSet==null){            vertexSet=new HashSet<String>();        }                vertexSet.add(from);        for(String to:toArr){            vertexSet.add(to);        }                if(connMap==null){            connMap=new LinkedHashMap<String,String[]>();        }                connMap.put(from, toArr);    }        // 建立图（即其中的顶点数组和邻接矩阵）    public void rebuildGraph(){        // 初始化顶点数组        List<String> ls=new ArrayList<String>();        ls.addAll(vertexSet);        Collections.sort(ls);                int size=ls.size();        arr=new Vertex[size];        for(int i=0;i<ls.size();i++){            arr[i]=new Vertex(ls.get(i));        }                // 初始化邻接矩阵        matrix=new int[size][size];        for(String key:connMap.keySet()){            String[] values=connMap.get(key);                        for(String value:values){                int x=findVertexIndex(key);                int y=findVertexIndex(value);                                if(x!=-1 && y!=-1){                    matrix[x][y]=1;                    matrix[y][x]=1;                }            }        }    }        // 在顶点数组里找顶点下标    private int findVertexIndex(String name){        for(int i=0;i<arr.length;i++){            if(name.equals(arr[i].name)){                return i;            }        }                return -1;    }        public void displayMatix(){        int n=arr.length;                System.out.print("  ");        for(int i=0;i<n;i++){            System.out.print(arr[i].name+",");        }        System.out.println();                System.out.print("-");        for(int i=0;i<n;i++){            System.out.print("--");        }        System.out.println();                for(int i=0;i<n;i++){            System.out.print(arr[i].name+":");                        for(int j=0;j<n;j++){                System.out.print(matrix[i][j]+",");            }                        System.out.println();        }    }        // 得到两个点之间的路径    public String getPath(String from,String to){        // 初始化        int fromIndex=findVertexIndex(from);        if(fromIndex==-1){            return "找不到顶点:"+from;        }                int toIndex=findVertexIndex(to);        if(toIndex==-1){            return "找不到顶点:"+to;        }                //  用于记住路径的栈        Stack<Integer> stack=new Stack<Integer>(Integer.class,arr.length);                // 开始寻找        arr[fromIndex].visited=true;        stack.push(fromIndex);                while(stack.isEmpty()==false){            int j=getConnVertex(stack.peek());                        if(j==-1){                stack.pop();            }else{                arr[j].visited=true;                stack.push(j);                            if(arr[j].name.equals(to)){                    // 找到了                                        StringBuilder sb=new StringBuilder();                                        while(stack.isEmpty()==false){                        int index=stack.pop();                                                sb.insert(0, arr[index].name+"->");                    }                                        return sb.substring(0, sb.length()-2);                }            }        }                return "不可能从"+from+"到"+to;    }        // 取得连接未访问过的顶点    private int getConnVertex(int i){        int n=arr.length;                for(int j=0;j<n;j++){            if(matrix[i][j]==1 && arr[j].visited==false){                return j;            }        }                return -1;    }        public static void main(String[] args){        Graph g=new Graph();                g.addConn("A", new String[]{"B","D"});        g.addConn("B", new String[]{"A","C"});        g.addConn("C", new String[]{"B","D","E"});        g.addConn("D", new String[]{"A","C"});        g.addConn("E", new String[]{"C"});        g.addConn("F", new String[]{"E","G"});        g.addConn("G", new String[]{"F"});        g.addConn("H", new String[]{"I","J"});        g.addConn("I", new String[]{"H","J"});        g.addConn("J", new String[]{"H","I"});                g.rebuildGraph();        g.displayMatix();        String path=g.getPath("A", "G");        System.out.println(path);                g.rebuildGraph();        path=g.getPath("A", "H");        System.out.println(path);                g.rebuildGraph();        path=g.getPath("J", "H");        System.out.println(path);                g.rebuildGraph();        path=g.getPath("F", "B");        System.out.println(path);    }}

  A,B,C,D,E,F,G,H,I,J,---------------------A:0,1,0,1,0,0,0,0,0,0,B:1,0,1,0,0,0,0,0,0,0,C:0,1,0,1,1,0,0,0,0,0,D:1,0,1,0,0,0,0,0,0,0,E:0,0,1,0,0,1,0,0,0,0,F:0,0,0,0,1,0,1,0,0,0,G:0,0,0,0,0,1,0,0,0,0,H:0,0,0,0,0,0,0,0,1,1,I:0,0,0,0,0,0,0,1,0,1,J:0,0,0,0,0,0,0,1,1,0,A->B->C->E->F->G不可能从A到HJ->HF->E->C->B