图

存储结构

• 二维数组，横纵坐标为点，如果有线连接，value为1
• 数组+链表

遍历

• 深度遍历：递归，可以借助树模型参考想象
• 广度遍历：借助栈

public class Graph {
  // 假设只有5个定点，是无向连通图
  public static void main(String[] args) {
    int n = 5; // 顶点的个数
    String[] vertexValue = {"A", "B", "C", "D", "E"};
    Graph graph = new Graph(n);
    for (String vertex : vertexValue) {
      graph.insertVertex(vertex);
    }
    // A-B A-C B-C B-D B-E
    graph.insertEdge(0, 1, 1); // A-B
    graph.insertEdge(0, 2, 1);
    graph.insertEdge(1, 2, 1);
    graph.insertEdge(1, 3, 1);
    graph.insertEdge(1, 4, 1);
    graph.showGraph();
    // 以树为模型想象图的问题比较简单
//    System.out.println("深度优先");
//    graph.dfs(0);
    System.out.println("广度优先");
    graph.bfs(0);
  }

  List vertexList;
  int[][] edges;
  int numberOfEdge;
  boolean[] isVisited;

  // 有多少个节点
  public Graph(int n) {
    this.vertexList = new ArrayList<String>(n);
    this.edges = new int[n][n]; // 数组存储图
    this.numberOfEdge = 0;
    isVisited = new boolean[5]; // 假设只有5个节点，isVisited的下标和vertexList下标对应，表示第i个节点
  }

  int getNextNeighbor(int index, int current) {
    for (int i = current; i < vertexList.size(); i++) {
      if (edges[index][i] > 0) {
        return i;
      }
    }
    return -1;
  }

  // 深度优先
  public void dfs(int index) {
    System.out.println(vertexList.get(index) + "->");
    isVisited[index] = true;
    int w = getNextNeighbor(index, 0);
    while (w > -1) {
      if (!isVisited[w]) {
        dfs(w);
      }
      w = getNextNeighbor(index, w + 1);
    }
  }

  //广度优先
  public void bfs(int index) {
    int u; // 出栈节点
    int w; // 邻接节点
    LinkedList queue = new LinkedList<Integer>();
    System.out.println(vertexList.get(index) + "->");
    isVisited[index] = true;
    queue.addLast(index);
    while (!queue.isEmpty()) {
      u = (int) queue.removeFirst();
      w = getNextNeighbor(u, 0);
      while (w > -1) {
        if (!isVisited[w]) {
          System.out.println(vertexList.get(w) + "->");
          isVisited[w] = true;
          queue.addLast(w);
        }
        w = getNextNeighbor(u, w + 1);
      }
    }
  }

  public void insertVertex(String vertex) {
    vertexList.add(vertex);
  }

  /**
   * @param v1     点在vertexList中的下标
   * @param v2
   * @param weight
   */
  public void insertEdge(int v1, int v2, int weight) {
    edges[v1][v2] = weight;
    // 因为是无向图，所以还要重复一边
    edges[v2][v1] = weight;
    numberOfEdge++;
  }

  public void showGraph() {
    for (int[] row : edges) {
      System.out.println(Arrays.toString(row));
    }
  }
}