package hartech.kids.grapher;

import hartech.*;
import hartech.ds.Queue;
import java.awt.Dimension;

/**
 * <p>Title: 圖的遍歷、最小生成樹、最短路徑</p>
 *
 *
 * <p>Description:
 *
 * 采用鄰接矩陣做為圖存儲結(jié)構(gòu)，有權(quán)無向圖，不相連的值為 -1
 *
 * 圖的遍歷中深度遍歷采用遞歸方法，廣度遍歷使用輔助隊列
 *
 * 最小生成樹采用克魯斯卡爾算法，使用一數(shù)組記錄節(jié)點的連通情況
 *
 * 圖的最短路徑采用迪杰斯特拉算法，使用隊列記錄依次途經(jīng)的路徑
 *
 * 修改：
 * 深度、廣度遍歷中 在列出第n節(jié)點相鄰的節(jié)點并一一入棧/隊時，相鄰最近的優(yōu)先入棧/隊
 *
 * </p>
 *
 * <p>Website: www.hartech.cn </p>
 * <p>Page: http://www.hartech.cn/blog/blogview.asp?logID=88 </p>
 *
 * <p>Date: 2006-09-08 </p>
 */
public class Graph {

  // 圖鄰接矩陣
  private static int[][] arcs;
  // 節(jié)點數(shù)
  private static int num;
  // 記錄是否訪問過
  private static boolean[] hasVisit;

  // 記錄訪問過的前一個節(jié)點，用于統(tǒng)計線路總長度
  static int pre;

  // 深度優(yōu)先遍歷，給出圖鄰接矩陣和開始遍歷的節(jié)點
  public static void traverse_DFS(int[][] arcs_in, int begin) {
    pre = begin;
    if (arcs_in == null || arcs_in.length == 0 ||
        arcs_in.length != arcs_in[0].length || begin < 0) {
      System.err.println("wrong arcs[][] or begin!");
      return;
    }
    arcs = arcs_in;
    num = arcs.length;
    hasVisit = new boolean[num];

    DFS(begin);
  }

  private static void DFS(int begin) {
    hasVisit[begin] = true;
    Main.Q_DFS.enQueue(begin);
    Main.length_DFS += Main.arcs[pre][begin];
    pre = begin;

    int min, n = 0;
    for (int i = 1; i < num; i++) {
      // 距離最短的優(yōu)先入棧
      min = Integer.MAX_VALUE;
      for (int j = 0; j < num; j++) {
        if (!hasVisit[j] && arcs[begin][j] != -1 && arcs[begin][j] < min) {
          min = arcs[begin][j];
          n = j;
        }
      }
      if (min == Integer.MAX_VALUE) {
        break;
      }
      else {
        DFS(n);
      }
    }
  }

  // 廣度優(yōu)先遍歷，給出圖鄰接矩陣和開始遍歷的節(jié)點
  public static void traverse_BFS(int[][] arcs_in, int begin) {
    pre = begin;
    if (arcs_in == null || arcs_in.length == 0 ||
        arcs_in.length != arcs_in[0].length || begin < 0) {
      System.err.println("wrong arcs[][] or begin!");
      return;
    }
    arcs = arcs_in;
    num = arcs.length;
    hasVisit = new boolean[num];
    Queue queue = new Queue();

    hasVisit[begin] = true;
    queue.enQueue(begin);
    int temp, min, n = 0;
    while (!queue.isEmpty()) {
      temp = ( (Integer) queue.deQueue()).intValue();
      for (int i = 1; i < num; i++) {
        // 距離最短的優(yōu)先入隊
        min = Integer.MAX_VALUE;
        for (int j = 0; j < num; j++) {
          if (!hasVisit[j] && arcs[temp][j] != -1 && arcs[temp][j] < min) {
            min = arcs[temp][j];
            n = j;
          }
        }
        if (min == Integer.MAX_VALUE) {
          break;
        }
        else {
          hasVisit[n] = true;
          queue.enQueue(n);
          Main.Q_BFS.enQueue(n);
          Main.length_BFS += Main.arcs[pre][n];
          pre = n;
        }
      }
    }
  }

  // 構(gòu)造最小生成樹，采用克魯斯卡爾算法
  // 使用一數(shù)組記錄節(jié)點的連通情況
  public static void miniSpanTree(int[][] arcs_in) {
    if (arcs_in == null || arcs_in.length == 0 ||
        arcs_in.length != arcs_in[0].length) {
      System.err.println("wrong arcs[][]!");
      return;
    }
    arcs = arcs_in;
    num = arcs.length;

    // 使用一數(shù)組記錄節(jié)點的連通情況
    // 如 group[0]＝0 表示節(jié)點未和任何節(jié)點連通
    // group[0]=group[3]=group[5]=2 表示節(jié)點0、3、5為同一連通圖內(nèi)，該連通圖的標識為 2
    int[] group = new int[num];
    boolean finish = false;

    int temp = 0, min, n1 = 0, n2 = 0, groupNum = 0;
    // 到全部group[n]等于同一數(shù)值，也就是處于同一連通圖才結(jié)束
    while (!finish) {

      // 遍歷所有路徑，無向圖，僅遍歷矩陣上三角
      // 找出最短的且不在同一連通圖的（group[n1]!=group[n2]），或兩節(jié)點都未加入連通圖的
      min = Integer.MAX_VALUE;
      for (int i = 0; i < num; i++) {
        for (int j = i + 1; j < num; j++) {
          if (arcs[i][j] < min && arcs[i][j] != -1) {
            if (group[i] != group[j] || (group[i] == 0 && group[j] == 0)) {
              min = arcs[i][j];
              n1 = i;
              n2 = j;
            }
          }
        }
      }
      // 無路了
      if (min == Integer.MAX_VALUE) {
        break;
      }

      Main.Q_tree.enQueue(new Dimension(n1, n2));
      Main.length_tree += Main.arcs[n1][n2];

      // 加入連通圖組
      if (group[n1] == 0 && group[n2] == 0) {
        groupNum++;
        group[n1] = groupNum;
        group[n2] = groupNum;
      }
      else if (group[n1] != 0 && group[n2] != 0) {
        temp = group[n2];
        for (int i = 0; i < num; i++) {
          if (group[i] == temp) {
            group[i] = group[n1];
          }
        }
      }
      else {
        if (group[n1] == 0) {
          group[n1] = group[n2];
        }
        else {
          group[n2] = group[n1];
        }
      }

      // 到全部group[n]等于同一數(shù)值且不為0，也就是處于同一連通圖才結(jié)束
      temp = 1;
      while (temp < num && group[temp] == group[0]) {
        temp++;
      }
      if (group[0] != 0 && temp == num) {
        finish = true;
      }
    }
    if (!finish) {
      System.out.println("圖為非強連通圖");
    }
  }

  // 圖的最短路徑，給出圖鄰接矩陣，起點，終點，打印出途經(jīng)的節(jié)點
  // 采用迪杰斯特拉算法
  public static void shortestPath_DIJ(int[][] arcs_in, int begin, int end) {
    if (arcs_in == null || arcs_in.length == 0 ||
        arcs_in.length != arcs_in[0].length) {
      System.err.println("wrong arcs[][]!");
      return;
    }
    arcs = arcs_in;
    num = arcs.length;
    // 標識節(jié)點是否已找到最短路徑，從begin到n 為finish[n]=true;
    boolean[] finish = new boolean[num];
    // 記錄從 begin 到 n 的最短路徑為 min[n]
    int[] D = new int[num];
    // 使用隊列記錄路徑途經(jīng)節(jié)點
    Queue[] queue = new Queue[num];

    // 初始化
    for (int i = 0; i < num; i++) {
      D[i] = arcs[begin][i];
      finish[i] = false;
      queue[i] = new Queue();
    }
    finish[begin] = true;
    D[begin] = -1;

    int v = 0, min = 0;
    // 一個一個循環(huán)找出最短距離（共num－1個）
    for (int i = 1; i < num; i++) {
      min = Integer.MAX_VALUE;
      // 掃描找出非final集中最小的D[]
      for (int w = 0; w < num; w++) {
        if (!finish[w] && D[w] < min && D[w] != -1) {
          v = w;
          min = D[w];
        }
      }

      finish[v] = true;
      // 已找到目標，退出循環(huán)
      if (v == end) {
        queue[v].enQueue(v);
        Main.Q_shortest = queue[v].clone();
        Main.length_short = D[v];
        break;
      }

      // 更新各D[]數(shù)據(jù)
      for (int w = 0; w < num; w++) {
        if (!finish[w] && arcs[v][w] != -1) {
          if ( (arcs[v][w] + min) < D[w] || D[w] == -1) {
            D[w] = arcs[v][w] + min;
            queue[w] = queue[v].clone();
            queue[w].enQueue(v);
          }
        }
      }
      queue[v].enQueue(v);
    }
  }

  public static void main(String[] args) {
    /**
     * test:
     * 深度遍歷結(jié)果：
     *  -> 0 -> 1 -> 3 -> 2 -> 4 -> 5 -> 6 -> 7
     * 廣度遍歷結(jié)果：
     * -> 0 -> 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7
     * 最小生成樹：
     * -> [0,1] -> [0,2] -> [0,5] -> [1,3] -> [0,4] -> [5,6] -> [6,7]
     * 從7到4的最短路徑：
     * [7] -> [4]:	 -> 7 -> 6 -> 5 -> 0 -> 4
     */
    int arcs[][] = {
        {
        -1, 1, 2, -1, 3, 2, -1, -1}, {
        1, -1, -1, 2, -1, -1, -1, -1}, {
        2, -1, -1, 3, -1, -1, -1, -1}, {
        -1, 2, 3, -1, -1, -1, -1, -1}, {
        3, -1, -1, -1, -1, 6, -1, -1}, {
        2, -1, -1, -1, 6, -1, 4, -1}, {
        -1, -1, -1, -1, -1, 4, -1, 4}, {
        -1, -1, -1, -1, -1, -1, 4, -1}
    };
    // 書上P174，圖7.16 的圖結(jié)構(gòu)
    int arcs2[][] = {
        {
        -1, 6, 1, 5, -1, -1}, {
        6, -1, 5, -1, 3, -1}, {
        1, 5, -1, 5, 6, 4}, {
        5, -1, 5, -1, -1, 2}, {
        -1, 3, 6, -1, -1, 5}, {
        -1, -1, 4, 2, 6, -1}
    };
    traverse_DFS(arcs, 0);

    traverse_BFS(arcs, 0);

    miniSpanTree(arcs);

    shortestPath_DIJ(arcs, 7, 4);
  }
}