// 顶点类，有两个数据成员，一个用于标识顶点，另一个是表明这个顶点是否被访问过。
function Vertex(label, wasVisited) {
  this.lable = label;
  this.wasVisited = wasVisited;
} 

function Graph(v) {
  this.vertices = v; // 顶点的数量
  this.edges = 0;  // 边的数量
  this.adj = []; // adjvex 邻接域，表示边，即上面说的邻接表 邻接矩阵
  for (var i = 0; i < this.vertices; i++) {
    this.adj[i] = []; // 初始化一个空数组来存储所有的相邻顶点
  }

  this.addEdge = addEdge;
  this.showGraph = showGraph;
}

// 增加v-w两个顶点之间的连接关系，即在v的邻接表中加入w 同时也在w的邻接表中加入v
// 然后将边的数量加1
function addEdge(v, w) {
  this.adj[v].push(w);
  this.adj[w].push(v);
  this.edges++;
}

// 打印所有顶点及其相邻顶点列表
function showGraph() {
  for (var i = 0; i < this.vertices; ++i) {
    var str = i + " -> ";
    for (var j = 0; j < this.vertices; ++j) {
      if (this.adj[i][j] != undefined) {
        str += this.adj[i][j] + " "
      }
    }
    console.log(str);
  }
}

var g = new Graph(4);
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 3)
g.showGraph()
// 0 -> 1 2 
// 1 -> 0 2 
// 2 -> 0 1 3 
// 3 -> 2 

function Graph(v) {
  // ...
  // 维护一个marked数组，用来标记该顶点是否被访问过
  this.marked = [];
  for (var i = 0; i < this.vertices; i++) {
    this.marked[i] = false; // 默认都是false
  }

  // 新增一个深度优先搜索的函数
  this.dfs = dfs;
}

function dfs(v) {
  this.marked[v] = true;
  if (this.adj[v] != undefined) {
    console.log("当前访问的顶点是: " + v);
  }
  
  // this.adj[v] 即初始访问顶点的邻接表
  // w 邻接表中的各个顶点
  this.adj[v].forEach(w => {
    if (!this.marked[w]) { // 没有访问过则递归
      this.dfs(w);
    }
  })
}

var g2 = new Graph(5)
g2.addEdge(0, 1)
g2.addEdge(0, 2)
g2.addEdge(1, 3)
g2.addEdge(2, 4)
g2.showGraph();
g2.dfs(0)
// 0 -> 1 2 
// 1 -> 0 3 
// 2 -> 0 4 
// 3 -> 1 
// 4 -> 2 
// 当前访问的顶点是: 0
// 当前访问的顶点是: 1
// 当前访问的顶点是: 3
// 当前访问的顶点是: 2
// 当前访问的顶点是: 4

function bfs(s) {
  var queue = [];
  this.marked[s] = true;
  queue.push(s); // 维护一个队列

  do {
    var v = queue.shift(); // 循环过程会不断push，通过shift依次从队首开始访问
    if (this.adj[v] != undefined) {
      console.log("当前访问的顶点是: " + v);
    }

    this.adj[v].forEach(w => {
      if (!this.marked[w]) {
        this.marked[w] = true;
        queue.push(w);
      }
    })

  } while (queue.length > 0);
}

var g3 = new Graph(5)
g3.addEdge(0, 1)
g3.addEdge(0, 2)
g3.addEdge(1, 3)
g3.addEdge(2, 4)
g3.showGraph();
g3.bfs(0)
// 0 -> 1 2 
// 1 -> 0 3 
// 2 -> 0 4 
// 3 -> 1 
// 4 -> 2 
// 当前访问的顶点是: 0
// 当前访问的顶点是: 1
// 当前访问的顶点是: 2
// 当前访问的顶点是: 3
// 当前访问的顶点是: 4

function Graph(v) {
  // ....

  this.edgeTo = [];
  this.pathTo = pathTo;
}

// 修改bfs方法，在广度搜索的时候，记录一下，到达某一顶点应该先经过哪个顶点。
function bfs(v) {
  var queue = [];
  this.marked[s] = true;
  queue.push(s);

  do {
    var v = queue.shift();
    if (this.adj[v] != undefined) {
      console.log("当前访问的顶点是: " + v);
    }

    this.adj[v].forEach(w => {
      if (!this.marked[w]) {
        // 记录了顶点w可以由顶点v到达 以下表述都以0为起点，因为bfs传入的s为0
        // 在此例中 edgeTo 为 [empty, 0, 0, 1, 2]
        // 即表示 顶点1、2由顶点0可以达到， 顶点3可以由顶点1到达，顶点4可以由顶点2到达。
        this.edgeTo[w] = v; 
        this.marked[w] = true;
        queue.push(w);
      }
    })

  } while (queue.length > 0);
}

// 查找路径
function pathTo(start, end) {
  var v = end;
  if (!this.marked[v]) {
    return undefined;
  }
  var path = [];
  // 从终点开始往回起点找，所以结束的条件为找到了起点
  // i是终点到起点回经过的各个点 start是起点
  // this.edgeTo[i] 得到的是 => 到达i顶点需要经过上一个顶点
  for (var i = v; i != start; i = this.edgeTo[i]) {
    path.push(i)
  }
  path.push(start)
  return path;
}

var g4 = new Graph(5)
g4.addEdge(0, 1)
g4.addEdge(0, 2)
g4.addEdge(1, 3)
g4.addEdge(2, 4)
g4.bfs(0) // 完成广度搜索
var paths = g4.pathTo(0, 4); // 查找0到4的路径
console.log(paths.reverse().join('-')) // 0-2-4

function Graph() {
  // ...
  
  this.vertexList = []; // 用来存储各个顶点的数据，使输出指向具体的数据

  this.topSortHelper = topSortHelper;
  this.topSort = topSort;
}

function topSort() {
  // 某个“最深”顶点的邻接表访问完成后，就将该顶点先入栈，输出的时候后出栈。
  // 即递归时，下面哪个顶点的forEach是最先执行完成的， this.adj[v] 中的 v。
  var stack = []; 
  var visited = new Array(5).fill(false); // 初始都标记为未访问
  
  for (var i = 0; i < this.vertices; i++) {
    if (visited[i] == false) {
      this.topSortHelper(i, visited, stack)
    }
  }

  // 栈结构，所以倒序输出
  for (var i = stack.length-1; i >= 0; i--) {
    if (stack[i] != undefined && stack[i] !== false) {
      console.log(this.vertexList[stack[i]]);
    }
  }
}

// 类似于深度优先搜索
function topSortHelper(v, visited, stack) {
  visited[v] = true;
  this.adj[v].forEach(w => {
    if (!visited[w]) {
      this.topSortHelper(w, visited, stack)
    }
  })
  stack.push(v)
}

var g = new Graph(6)
g.addEdge(0, 1)
g.addEdge(1, 2)
g.addEdge(1, 3)
g.addEdge(2, 4)
g.addEdge(2, 5)
g.vertexList = ['CS1', 'CS2', '数据结构', '汇编语言', '操作系统', '算法']
g.topSort();
// CS1
// CS2
// 汇编语言
// 数据结构
// 算法
// 操作系统