广度优先和深度优先

  1 package test;
  2 
  3 import java.util.ArrayList;
  4 import java.util.LinkedList;
  5 
  6 public class Graph {
  7     private int[][] edges;
  8     private ArrayList vertexList;
  9     private boolean[] isVisited;
 10     private int numVertex;
 11 
 12     public Graph(int n) {
 13         edges = new int[n][n];
 14         vertexList = new ArrayList(n);
 15         isVisited = new boolean[n];
 16         numVertex = n;
 17         // 每个顶点初始化为false
 18         for (int i = 0; i < n; i++) {
 19             isVisited[i] = false;
 20         }
 21     }
 22 
 23     public void insertVertex(String vertex) {
 24         vertexList.add(vertex);
 25     }
 26 
 27     public void insertEdge(int v1, int v2, int weight) {
 28         edges[v1][v2] = weight;
 29     }
 30 
 31     public void depthFirstSearch() {
 32         for (int i = 0; i < numVertex; i++) {
 33             if (!isVisited[i])// 如果某个点没访问的话，那么去遍历
 34             {
 35                 depthFirstSearch(isVisited, i);
 36             }
 37         }
 38     }
 39 
 40     public int getFirstNeighbor(int index) {
 41         for (int j = 0; j < numVertex; j++) {
 42             if (edges[index][j] > 0) {
 43                 return j;
 44             }
 45         }
 46         return -1;// 表示此点没有与之相邻的点
 47     }
 48 
 49     // 从v2开始检查，可以减少计算量
 50     public int getNextNeighbor(int v1, int v2) {
 51         for (int j = v2 + 1; j < numVertex; j++) {
 52             if (edges[v1][j] > 0) {
 53                 return j;
 54             }
 55         }
 56         return -1;
 57     }
 58 
 59     public void depthFirstSearch(boolean[] isVisited, int i) {
 60         //
 61         System.out.print(vertexList.get(i) + " ");
 62         isVisited[i] = true;
 63         int newStartNode = getFirstNeighbor(i);
 64         while (newStartNode != -1) {
 65             if (!isVisited[newStartNode])// 如果这个点没有被访问
 66             {
 67                 depthFirstSearch(isVisited, newStartNode);
 68             }
 69             newStartNode = getNextNeighbor(i, newStartNode);
 70         }
 71     }
 72 
 73     // 广度优先
 74     public void broadFirstSearch() {
 75         for (int i = 0; i < numVertex; i++) {
 76             broadFirstSearch(isVisited, i);
 77         }
 78     }
 79 
 80     private void broadFirstSearch(boolean[] isVisited, int i) {
 81         int currentVisitedNode, adjacentCurrentVisitedNode;
 82         LinkedList queue = new LinkedList();
 83         // 访问该节点
 84         System.out.print(vertexList.get(i) + " ");
 85         isVisited[i] = true;
 86         // 节点入队列
 87         queue.add(i);
 88         while (!queue.isEmpty()) {
 89             currentVisitedNode = ((Integer) queue.removeFirst()).intValue();// 移除队列的第一个元素，即头
 90             adjacentCurrentVisitedNode = getFirstNeighbor(currentVisitedNode);
 91 
 92             while (adjacentCurrentVisitedNode != -1) {
 93                 if (!isVisited[adjacentCurrentVisitedNode]) {
 94                     // 访问该节点
 95                     System.out.print(vertexList.get(adjacentCurrentVisitedNode) + " ");
 96                     // 标记该节点
 97                     isVisited[adjacentCurrentVisitedNode] = true;
 98                     // 入队列
 99                     queue.addLast(adjacentCurrentVisitedNode);
100                 }
101                 // 寻找下一个邻接节点
102                 adjacentCurrentVisitedNode = getNextNeighbor(currentVisitedNode, adjacentCurrentVisitedNode);
103             }
104         }
105 
106     }
107 }

 1 package test;
 2 
 3 public class TestSearch {
 4     public static void main(String args[]) {
 5 
 6         String labels[] = { "1", "2", "3", "4", "5" };// 结点的标识
 7         int n = labels.length;
 8         Graph graph = new Graph(n);
 9         for (String label : labels) {
10             graph.insertVertex(label);// 插入结点
11         }
12         // 插入四条边
13         graph.insertEdge(0, 1, 1);
14         graph.insertEdge(0, 2, 1);
15         graph.insertEdge(1, 3, 1);
16         graph.insertEdge(1, 4, 1);
17 
18         System.out.println("深度优先搜索序列为：");
19         graph.depthFirstSearch();
20         
21          System.out.println();
22          System.out.println("广度优先搜索序列为：");
23          graph.broadFirstSearch();
24     }
25 }