图的示意图

image.png
源码

  1. class node {
  2.     constructor(value) {
  3.         this.value = value;
  4.         this.neighbour = [];
  5.     }
  6. }
  8. const a = new node('a');
  9. const b = new node('b');
  10. const c = new node('c');
  11. const d = new node('d');
  12. const e = new node('e');
  14. a.neighbour.push(b);
  15. a.neighbour.push(c);
  16. b.neighbour.push(a);
  17. b.neighbour.push(c);
  18. b.neighbour.push(d);
  19. c.neighbour.push(a);
  20. c.neighbour.push(b);
  21. c.neighbour.push(d);
  22. d.neighbour.push(b);
  23. d.neighbour.push(c);
  24. d.neighbour.push(e);
  25. e.neighbour.push(d);
  27. /**
  28.  * 图的深度优先搜索
  29.  * @param {*} root 
  30.  * @param {*} target 
  31.  * @param {*} path 
  32.  * @returns 
  33.  */
  34. function deepSearch(root, target, path = []) {
  35.     if (root == null) return false;
  36.     if (path.includes(root) ) return false;
  37.     console.log(root.value, target, 'value')
  38.     if (root.value == target) return true;
  39.     path.push(root);
  40.     let result = false;
  41.     for (let i = 0; i < root.neighbour.length; i++) {
  42.         result = deepSearch(root.neighbour[i], target, path);
  43.         if(result) return true;
  44.     }
  45.     return result;
  46. }
  48. console.log(deepSearch(a, 'e', []))