1 import java.util.HashMap;  2 import java.util.LinkedList;  3 import java.util.Queue;  4 import java.util.Stack;  5   6 public class task1  7 {  8     public static void main(String[] args)  9     {     10         Graph g = new Graph(5); 11         g.createGraph(); 12          13         System.out.println("DFS(递归)"); 14         DFS(g, 0); 15         System.out.println(); 16         for(Vertex p : g.vertex) //数组元素的拷贝 17             p.isvisited = false; 18         System.out.println("DFS(迭代)"); 19         DFS_iterative(g, 0); 20         for(Vertex p : g.vertex) 21             p.isvisited = false; 22         System.out.print('\n' + "BFS" + '\n'); 23         BFS(g, 0); 24     } 25      26     //递归 27     public static void DFS(Graph g, int index) 28     { 29         System.out.print(g.vertex[index].name + " "); 30         g.vertex[index].isvisited = true; 31          32         for(Vertex v : g.adjacencyMap.get(g.vertex[index])) 33             if(v.isvisited == false) 34             { 35                 int i = g.locateVex(v.name); 36                 DFS(g, i); 37             } 38     } 39      40     //非递归 41     public static void DFS_iterative(Graph g, int index) 42     { 43         Stack
     
       stack = new Stack<>(); 44         stack.push(g.vertex[index]); 45         Vertex p; 46          47         while(!stack.isEmpty()) 48         { 49             p = stack.pop(); 50             if(p.isvisited == false) 51             { 52                 System.out.print(p.name + " "); 53                 p.isvisited = true; 54                 for(Vertex q : g.adjacencyMap.get(p)) 55                     if(q.isvisited == false)  //可避免重复入栈 56                         stack.push(q);  57             } 58         } 59     } 60      61     //BFS 62     public static void BFS(Graph g, int index) 63     { 64         Queue
      
        queue = new LinkedList<>(); 65         Vertex p; 66         System.out.print(g.vertex[index].name + " "); 67         g.vertex[index].isvisited = true; 68         queue.add(g.vertex[index]);  //每个元素仅入队一次 69          70         while(!queue.isEmpty()) 71         { 72             p = queue.poll(); 73             for(Vertex q : g.adjacencyMap.get(p)) 74                 if(q.isvisited == false) 75                 { 76                     System.out.print(q.name + " "); 77                     q.isvisited = true; 78                     queue.add(q); 79                 } 80         } 81     } 82 } 83  84 class Vertex 85 { 86     char name; 87     boolean isvisited; 88      89     public Vertex(char name) 90     { 91         this.name = name; 92         this.isvisited = false; 93     } 94 } 95  96 class Graph 97 { 98     Vertex[] vertex;  //顶点数组 99     int vexnum;  //顶点数100     HashMap
       
        > adjacencyMap;  //邻接表101     102     public Graph(int vexnum)103     {104         this.vertex = new Vertex[vexnum];105         for(int i = 0; i < this.vertex.length; i++)106             this.vertex[i] = new Vertex((char)('a' + i));107         this.vexnum = vexnum;108     }109     110     public void createGraph()111     {112         //各点与其邻接点的映射113         this.adjacencyMap = new HashMap<>();114         115         116         //无向图117         //a的邻接点118         /*LinkedList
        
          aNeighbors = new LinkedList<>();119         aNeighbors.add(vertex[1]);120         aNeighbors.add(vertex[2]);121         //b的邻接点    122         LinkedList
         
           bNeighbors = new LinkedList<>();123         bNeighbors.add(vertex[0]);124         bNeighbors.add(vertex[3]);125         bNeighbors.add(vertex[4]);126         //c的邻接点127         LinkedList
          
            cNeighbors = new LinkedList<>();128 cNeighbors.add(vertex[0]);129 cNeighbors.add(vertex[3]);130 //d的邻接点131 LinkedList
           
             dNeighbors = new LinkedList<>();132 dNeighbors.add(vertex[1]);133 dNeighbors.add(vertex[2]);134 dNeighbors.add(vertex[4]);135 //e的邻接点136 LinkedList
            
              eNeighbors = new LinkedList<>();137 eNeighbors.add(vertex[1]);138 eNeighbors.add(vertex[3]);139 //建立映射140 adjacencyMap.put(vertex[0], aNeighbors);141 adjacencyMap.put(vertex[1], bNeighbors);142 adjacencyMap.put(vertex[2], cNeighbors);143 adjacencyMap.put(vertex[3], dNeighbors);144 adjacencyMap.put(vertex[4], eNeighbors);*/145 146 147 //有向图148 //a的邻接点149 LinkedList
             
               aNeighbors = new LinkedList<>();150 aNeighbors.add(vertex[2]);151 //b的邻接点152 LinkedList
              
                bNeighbors = new LinkedList<>();153 bNeighbors.add(vertex[0]);154 //c的邻接点155 LinkedList
               
                 cNeighbors = new LinkedList<>();156 cNeighbors.add(vertex[3]);157 //d的邻接点158 LinkedList
                
                  dNeighbors = new LinkedList<>();159 dNeighbors.add(vertex[1]);160 dNeighbors.add(vertex[4]);161 //e的邻接点162 LinkedList
                 
                   eNeighbors = new LinkedList<>();163 eNeighbors.add(vertex[1]);164 //建立映射165 adjacencyMap.put(vertex[0], aNeighbors);166 adjacencyMap.put(vertex[1], bNeighbors);167 adjacencyMap.put(vertex[2], cNeighbors);168 adjacencyMap.put(vertex[3], dNeighbors);169 adjacencyMap.put(vertex[4], eNeighbors);170 }171 172 public int locateVex(char name)173 {174 int i;175 for(i = 0; /*i != this.vertex.length && */name != this.vertex[i].name; i++);176 return i;177 }178 }