分享一个，望版主不要再无缘无故删帖：

1. /**
   
2. * 图
   
3. * @author DBJ(dubenju@126.com)
   
4. */
   
5. public class DefaultGraph implements Graph {
   
6. 
   
7.     /** 顶点集  */
   
8.     private ArrayList<Vertex> vertexes;
   
9.     /** 邻接表  */
   
10.     private ArrayList<LinkedList<Edge>> adjacencyList;
    
11.     private int edgeSize;
    
12. 
    
13.     /**
    
14.      * 遍历
    
15.      */
    
16. 
    
17.     /**
    
18.      * 深度优先遍历(DFS)
    
19.      */
    
20.     public void depthFirstTraversal(GraphVisitor visitor) {
    
21.         // reset Visited
    
22.         initVisit();
    
23.         for(int i = 0; i < this.vertexes.size(); i ++) {
    
24.             Vertex vertex = this.vertexes.get(i);
    
25.             if(vertex.isVisited() == false) {
    
26.                 do_DFS(vertex, visitor);
    
27.             }
    
28.         }
    
29.     }
    
30. 
    
31.     /**
    
32.      * 深度优先遍历x
    
33.      * @param v 顶点
    
34.      * @param visitor
    
35.      */
    
36.     private final void do_DFS(Vertex v, GraphVisitor visitor) {
    
37.         // first visit this vertex
    
38.         visitor.visit(this, v);
    
39.         v.setVisit(true);
    
40. 
    
41.         // for each edge from this vertex, we do one time and this for loop is very classical in all graph algorithms
    
42.         for(Edge e = firstEdge(v); isEdge(e); e = e.getNextEdge()) {
    
43.             if(e.getTo().isVisited() == false) {
    
44.                 do_DFS(e.getTo(), visitor);
    
45.             }
    
46.         }
    
47.     }
    
48. 
    
49.     /**
    
50.      * 广度优先遍历(BFS)
    
51.      */
    
52.     public void breathFirstTraversal(GraphVisitor visitor) {
    
53.         // reset Visited
    
54.         initVisit();
    
55.         for(int i = 0; i < this.vertexes.size(); i ++) {
    
56.             Vertex vertex = this.vertexes.get(i);
    
57.             if(vertex.isVisited() == false) {
    
58.                 do_BFS(vertex, visitor);
    
59.             }
    
60.         }
    
61.     }
    
62. 
    
63.     /**
    
64.      * 广度优先遍历x
    
65.      * @param v 顶点
    
66.      * @param visitor
    
67.      */
    
68.     private void do_BFS(Vertex v, GraphVisitor visitor) {
    
69.         // BFS will use an queue to keep the unvisited vertexes. we can also just use java.util.LinkedList
    
70.         LinkedList<Vertex> queue = new LinkedList<Vertex>();
    
71.         queue.add(v);
    
72.         while(!queue.isEmpty()) {
    
73.             Vertex fromV = queue.poll();
    
74.             if (fromV.isVisited() == false) {
    
75.                 visitor.visit(this, fromV);
    
76.                 fromV.setVisit(true);
    
77.                 for(Edge e = firstEdge(fromV); isEdge(e); e = e.getNextEdge()) {
    
78.                     Vertex toV = e.getTo();
    
79.                     if(toV.isVisited() == false) {
    
80.                         queue.add(toV);
    
81.                     }
    
82.                 }
    
83.             }
    
84.         }
    
85.     }
    
86.    
    
87. }

复制代码

分享一个，望版主不要再无缘无故删帖：

1. /**
   
2. * 图
   
3. * @author DBJ(dubenju@126.com)
   
4. */
   
5. public class DefaultGraph implements Graph {
   
6. 
   
7.     /** 顶点集  */
   
8.     private ArrayList<Vertex> vertexes;
   
9.     /** 邻接表  */
   
10.     private ArrayList<LinkedList<Edge>> adjacencyList;
    
11.     private int edgeSize;
    
12. 
    
13.     /**
    
14.      * 遍历
    
15.      */
    
16. 
    
17.     /**
    
18.      * 深度优先遍历(DFS)
    
19.      */
    
20.     public void depthFirstTraversal(GraphVisitor visitor) {
    
21.         // reset Visited
    
22.         initVisit();
    
23.         for(int i = 0; i < this.vertexes.size(); i ++) {
    
24.             Vertex vertex = this.vertexes.get(i);
    
25.             if(vertex.isVisited() == false) {
    
26.                 do_DFS(vertex, visitor);
    
27.             }
    
28.         }
    
29.     }
    
30. 
    
31.     /**
    
32.      * 深度优先遍历x
    
33.      * @param v 顶点
    
34.      * @param visitor
    
35.      */
    
36.     private final void do_DFS(Vertex v, GraphVisitor visitor) {
    
37.         // first visit this vertex
    
38.         visitor.visit(this, v);
    
39.         v.setVisit(true);
    
40. 
    
41.         // for each edge from this vertex, we do one time and this for loop is very classical in all graph algorithms
    
42.         for(Edge e = firstEdge(v); isEdge(e); e = e.getNextEdge()) {
    
43.             if(e.getTo().isVisited() == false) {
    
44.                 do_DFS(e.getTo(), visitor);
    
45.             }
    
46.         }
    
47.     }
    
48. 
    
49.     /**
    
50.      * 广度优先遍历(BFS)
    
51.      */
    
52.     public void breathFirstTraversal(GraphVisitor visitor) {
    
53.         // reset Visited
    
54.         initVisit();
    
55.         for(int i = 0; i < this.vertexes.size(); i ++) {
    
56.             Vertex vertex = this.vertexes.get(i);
    
57.             if(vertex.isVisited() == false) {
    
58.                 do_BFS(vertex, visitor);
    
59.             }
    
60.         }
    
61.     }
    
62. 
    
63.     /**
    
64.      * 广度优先遍历x
    
65.      * @param v 顶点
    
66.      * @param visitor
    
67.      */
    
68.     private void do_BFS(Vertex v, GraphVisitor visitor) {
    
69.         // BFS will use an queue to keep the unvisited vertexes. we can also just use java.util.LinkedList
    
70.         LinkedList<Vertex> queue = new LinkedList<Vertex>();
    
71.         queue.add(v);
    
72.         while(!queue.isEmpty()) {
    
73.             Vertex fromV = queue.poll();
    
74.             if (fromV.isVisited() == false) {
    
75.                 visitor.visit(this, fromV);
    
76.                 fromV.setVisit(true);
    
77.                 for(Edge e = firstEdge(fromV); isEdge(e); e = e.getNextEdge()) {
    
78.                     Vertex toV = e.getTo();
    
79.                     if(toV.isVisited() == false) {
    
80.                         queue.add(toV);
    
81.                     }
    
82.                 }
    
83.             }
    
84.         }
    
85.     }
    
86.    
    
87. }

复制代码