出度、入度

• 出度：节点指向多少个节点
• 入度：有多少个节点指向该节点

有向图、无向图

• 有向图：每个节点是有方向的
• 无向图：每个节点无方向，可以相互指向，互为出入度

邻接表

• 通过节点的指向表示

邻接矩阵

• 通过矩阵表示，A-A的权重为0，A-C的权重为7，…

宽度遍历

• 宽度遍历的结果为：A、C、B、E、D，其中CBE的顺序无所谓，相比于二叉树的宽度遍历，因为图有指向自身或已遍历节点的方向，所以需要处理这样的环结构的问题

function BFS(node) {
  let arr = [];
  //Set保证去重去环
  let unique = new Set();

  arr.push(node);
  unique.add(node);
  for (let i = 0; i < arr.length; i++) {
    let tempNode = arr[i];
    console.log(tempNode.value);
    //nexts是当前节点指向的节点集合
    let nexts = tempNode.nexts || [];
    for (let j = 0; j < nexts; j++) {
      let nextNode = nexts[j];
      if (unique.has(nextNode)) {
        return;
      }
      arr.push(nextNode);
      unique.add(nextNode);
    }
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

深度遍历

• 深度优先遍历：如果从B进入的话，ABCDE
  • 深度优先遍历准备一个栈结构，是当一个节点进去的时候处理，同样需要处理节点的指向自身或已遍历节点形成的环的问题（Set）
  • 如果当前节点指向的最近的节点未遍历，就将当前节点和指向的节点一起加入栈中，输出指向的节点，然后终止掉，从指向的节点开始遍历，即弹出栈顶元素
  • 重复上一步，当指向的节点不再有指向的节点时，因为每次存入的都是一对节点和节点指向的节点，所以会继续弹出栈顶元素，即指向之前弹出节点的那个节点，恢复路径，继续走上一步，因为会有去重判断，所以恢复的路径节点，不会再遍历已经遍历过的指向节点

function DFS(node) {
  let stack = [];
  let unique = new Set();

  stack.push(node);
  unique.add(node);

  console.log(node.value);

  while (stack.length) {
    //弹出上一次存的最新的节点，开始走新节点的深度
    let tempNpde = stack.pop();
    let nexts = tempNpde.nexts;
    for (let i = 0; i < nexts.length; i++) {
      let nextNode = nexts[i];
      if (!unique.has(nextNode)) {
        //1、如果当前节点指向的最近的节点未遍历，就将当前节点和执行的节点一起加入栈中然后break
        //2、下次将取当前节点指向的节点为起始点，重复上面步骤
        //3、当深度遍历结束，因为栈中存的是每一对当前节点和当前节点的指向节点，所以路径恢复到当前节点，继续重复第一步

        //再次放入是为了栈还原
        stack.push(tempNpde);
        //放入当前节点，将在break后使用
        stack.push(nextNode);
        //去重去环
        unique.add(nextNode);
        console.log(nextNode.value);
        break;
      }
    }
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33