【数据结构】图

[miracles1919]

参考：图论基础及遍历算法

图是由节点和边构成的

常用邻接表和领接矩阵来实现

度 (degree)

• 无向图中，度就是每个节点相连的边的条数
• 有向图中，度分为出度和入度
  • 对于节点 3，indegree = 3，outdegree = 1

[miracles1919]

797. 所有可能的路径

时间复杂度：O(n x 2^n) 空间复杂度：O(n)

var allPathsSourceTarget = function (graph) {
    const res = [];
    const path = [0];
    const n = graph.length;

    function traverse (graph, node) {
        // 到达终点
        if (node === n - 1) {
            res.push(path.slice())
            return
        }

        // 递归相邻节点
        for(const v of graph[node]) {
            path.push(v)
            traverse(graph, v)
            path.pop()
        }
    }

    traverse(graph, 0);
    return res;
};

[miracles1919]

785. 判断二分图

• DFS 时间复杂度：O(n + m)，n 图的点数，m 的变数 空间复杂度：O(n)

  var isBipartite = function (graph) {
  const n = graph.length
  const visited = Array(n)
  const color = Array(n).fill(false)
  let valid = true
  
  function dfs (graph, v) {
  visited[v] = true
  for (const neighbor of graph[v]) {
    if (!visited[neighbor]) {
      color[neighbor] = !color[v]
      dfs(graph, neighbor)
      if (!valid) return 
    } else {
      if (color[neighbor] === color[v]) {
        valid = false
        return      
      }
    }
  } 
  }
  
  for (let i = 0; i < n; i++) {
  if (!visited[i]) {
    dfs(graph, i)
  }
  }
  return valid
  } 

• BFS 时间复杂度：O(n + m)，n 图的点数，m 的变数 空间复杂度：O(n)

  var isBipartite = function (graph) { 
  const n = graph.length
  const visited = Array(n)
  const color = Array(n).fill(false)
  let valid = true
  
  function bfs (graph, v) {
  visited[v] = true
  const queue = [v]
  
  while (queue.length) {
    const curr = queue.pop()
    for (const neighbor of graph[curr]) {
      if (!visited[neighbor]) {
        color[neighbor] = !color[curr]
        visited[neighbor] = true
        queue.push(neighbor)
      } else {
         if (color[neighbor] === color[curr]) {
           valid = false
           return
         }
      }
    }
  } 
  }
  
  for (let i = 0; i < n; i++) {
  if (!visited[i]) {
    bfs(graph, i)
  }
  }
  
  return valid
  }

[miracles1919]

886. 可能的二分法

var possibleBipartition = function (n, dislikes) {
  function buildGraph (n, dislikes) {
    const graph = new Array(n + 1).fill(0).map(() => []);
    dislikes.forEach((item) => {
      const [x, y] = item;
      graph[x].push(y);
      graph[y].push(x);
    });
    return graph;
  }

  const graph = buildGraph(n, dislikes) 
  return isBipartite(graph)
}