算法是作用于数据结构之上的，深度优先搜索算法和广度优先搜索算法都是基于“图”这种数据结构。

如何理解图（Graph）

图是一种非线性表数据结构，图中的元素叫做顶点(vertex)。顶点可以与任意其它顶点建立连接关系，这种关系叫做连(edge)
graph1.jpg

邻接表存储方法

graph2.jpg
每个顶点对应一条链表，链表中存储的是与这个顶点相连接的期货顶点。

Graph的代码实现

  2. import java.util.LinkedList;
  3. import java.util.Queue;
  5. public class Graph {
  6.     private int vertex; // 图的顶点数
  7.     private LinkedList<Integer> adj[]; // 邻接表
  9.     public Graph(int v){
  10.         this.vertex = v;
  11.         adj = new LinkedList[v];
  12.         for (int i = 0; i < v; i++){
  13.             adj[i] = new LinkedList<>();
  14.         }
  15.     }
  17.     // 无向图的边存两次
  18.     public void addEdge(int s, int t){
  19.         adj[s].add(t);
  20.         adj[t].add(s);
  21.     }
  23.     /**
  24.      * 广度优先搜索
  25.      * @param s 源点数
  26.      * @param t 目标数
  27.      */
  28.     public void bfs(int s, int t){
  29.         if(s == t) return;
  30.         // 记录已访问的点，防上重复访问
  31.         boolean[] visited = new boolean[vertex];
  32.         visited[s] = true;
  33.         // 记录搜索路径
  34.         int[] pre = new int[vertex];
  35.         for (int i = 0; i < pre.length; i++){
  36.             pre[i] = -1;
  37.         }
  38.         //队列用于存储已被访问，但相连的顶点还没有访问的顶点
  39.         Queue<Integer> queue = new LinkedList<>();
  40.         queue.add(s);
  41.         while (queue.size() != 0){
  42.             int w = queue.poll();
  43.             for (int i =0; i < adj[w].size(); i++){
  44.                 int q = adj[w].get(i);
  45.                 if(!visited[q]){
  46.                     pre[q] = w;
  47.                     if(q == t){
  48.                         print(pre, s, t);
  49.                         return;
  50.                     }
  51.                     visited[q] = true;
  52.                     queue.add(q);
  53.                 }
  54.             }
  55.         }
  56.     }
  58.     public void print(int[] prev, int s, int t){
  59.         if (prev[t] != -1 && t !=s){
  60.             print(prev, s, prev[t]);
  61.         }
  62.         System.out.print(t + " ");
  63.     }
  65.     public static void main(String[] args) {
  66.         Graph graph = new Graph(8);
  67.         graph.addEdge(0,1);
  68.         graph.addEdge(0,3);
  69.         graph.addEdge(1,2);
  70.         graph.addEdge(1,4);
  71.         graph.addEdge(2,5);
  72.         graph.addEdge(4,5);
  73.         graph.addEdge(4,6);
  74.         graph.addEdge(5,7);
  75.         graph.addEdge(6,7);
  76.         graph.bfs(0,1);
  77.     }
  78. }