爪哇国新游记之二十五----图及其遍历查找-白红宇

代码：

import java.util.ArrayList;import java.util.Collections;import java.util.HashSet;import java.util.LinkedHashMap;import java.util.LinkedList;import java.util.List;import java.util.Map;import java.util.Queue;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
     
       vertexSet;// 包含不重复顶点的集合    private Map
      
        connMap;// 包含连接的哈希表        // 添加顶点之间的连接关系    public void addConn(String from,String[] toArr){        if(vertexSet==null){            vertexSet=new HashSet
       
        ();        }                vertexSet.add(from);        for(String to:toArr){            vertexSet.add(to);        }                if(connMap==null){            connMap=new LinkedHashMap
        
         ();        }                connMap.put(from, toArr);    }        // 建立图（即其中的顶点数组和邻接矩阵）    public void rebuildGraph(){        // 初始化顶点数组        List
         
           ls=new ArrayList
          
           (); ls.addAll(vertexSet); Collections.sort(ls); int size=ls.size(); arr=new Vertex[size]; for(int i=0;i
           
             stack=new Stack
            
             (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; } // 广度优先搜索 public String getPath2(String from,String to){ resetArr(); // 初始化 int fromIndex=findVertexIndex(from); if(fromIndex==-1){ return "找不到顶点:"+from; } int toIndex=findVertexIndex(to); if(toIndex==-1){ return "找不到顶点:"+to; } // 用于记住路径的队列 Queue
             
               queue=new LinkedList
              
               (); // 开始寻找 StringBuilder sb=new StringBuilder(); arr[fromIndex].visited=true; queue.add(fromIndex); sb.append(arr[fromIndex].name+"->"); int j; while(queue.isEmpty()==false){ int i=queue.remove(); while((j=getConnVertex(i))!=-1){ arr[j].visited=true; sb.append(arr[j].name+"->"); queue.add(j); if(arr[j].name.equals(to)){ // 找到了 return sb.substring(0, sb.length()-2); } } } return "不可能从"+from+"到"+to; } /** * 重置顶点访问情况 */ private void resetArr(){ int n=arr.length; for(int j=0;j

输出：

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->BA->B->D->C->E->F->GF->E->G->C->B

顶点示意图：

本文转自张昺华-sky博客园博客，原文链接：http://www.cnblogs.com/xiandedanteng/p/3885477.html，如需转载请自行联系原作者