SHARE
TWEET

Untitled

a guest Oct 18th, 2019 87 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // 图
  2. class Graph {
  3.     constructor(count, adj_list) {
  4.         this.count = count          // 记录顶点的个数
  5.         this.adj = new Array(count)    // 邻接表
  6.         // 初始化邻接表
  7.         for (let i = 0; i < count; i++) {
  8.             this.adj[i] = new Array()
  9.         }
  10.         for (let j = 0, len = adj_list.length; j < len; j++) {
  11.             let vw = adj_list[j]
  12.             this.adj[vw[0]].push(vw[1])
  13.         }
  14.     }
  15.     showGraph() {
  16.         let str = ''
  17.         for (let i = 0; i < this.count; i++) {
  18.             str += (i + " -> ")
  19.             for (let j = 0, len = this.adj[i].length; j < len; j++) {
  20.                 if (this.adj[i][j] != undefined) {
  21.                     str += (this.adj[i][j] + ' ')
  22.                 }
  23.             }
  24.             str += "\n"
  25.         }
  26.         console.log(str)
  27.     }
  28.     build_path(edgeTo, end, start) {
  29.         const path = []
  30.         for (let i = end; i != start; i = edgeTo[i]) {
  31.             path.push(i)
  32.         }
  33.         path.push(start)
  34.         return path.reverse()
  35.     }
  36.     find_path(start, end) {
  37.         const que = [], edgeTo = [], visited = []
  38.         visited[start] = true
  39.         que.push(start)
  40.         while (que.length > 0) {
  41.             let v = que.shift()
  42.             for (let w of this.adj[v]) {
  43.                 if (!visited[w]) {
  44.                     visited[w] = true
  45.                     edgeTo[w] = v
  46.                     que.push(w)
  47.                     if (w == end) {
  48.                         return this.build_path(edgeTo, end, start)
  49.                     }
  50.                 }
  51.             }
  52.         }
  53.     }
  54. }
  55. const count = 4
  56. const g = new Graph(count, [[0,1], [0,2], [1,0], [1,2], [1,3], [2,0], [2,1], [3,0], [3,1]])
  57. g.showGraph()
  58. for (let i = 0; i < count; i++) {
  59.     for (let j = 0; j < count; j++) {
  60.         if (i != j) {
  61.             console.log(i + '->' + j, g.find_path(i, j))
  62.         }
  63.     }
  64. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top