Advertisement
Guest User

Untitled

a guest
Oct 18th, 2019
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.84 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement