概念
图是网络机构的抽象模型，是一组由边连接的节点。图可以表示任何二元关系，比如道路、航班...
在Javascript中，是没有图这种数据结构的，但是可以用Object和Array构建图。
图有多种表示法：邻接矩阵、邻接表、关联矩阵...，一般根据需求自由表示。
图的表示法：邻接矩阵
网络异常，图片无法展示
|
使用空间会比邻接表大，但是能清楚的查出边
图的表示法：邻接表
网络异常，图片无法展示
|
图的表示法太多，如何应对？
按自己喜欢的表示法实现所有的算法。
对于我们来说，只需要掌握最经典的表示法，遇到不同的需求，如果是其他表示法，我们就可以转换成最经典表示法，比如邻接矩阵表示法，再进行其他计算，这样就相当于掌握一种模版，然后遇到一些特殊的情况就先将它转换成模版，然后再进行操作，这样才能达到一通百通。
用Java代码表示图
publicn class Graph{ public HashMap<Integer, Node> nodes; // 点集，哈希表表示，Integer是表示点的编号 public HashSet<Edge> edges; // 边集 public Graph(){ nodes = new HashMap<>(); edges = new HashSet<>(); } } public class Edge{ public int weight; // 权值，常表示距离 public Node from; // 从哪个节点出来的 public Node to; // 到哪个节点去 public Edge(int weight, Node from, Node to){ this.weight = weight; this.from = from; this.to = to; } } public class Node{ public int value; // 点的值 public int in; // 点的入度 public int out; // 点的出度 public ArrayList<Node> nexts; // 从当前点出发，从它发散出去的边指向的邻居 public ArrayList<Edge> edges; // 从当前点出发，从它发散出去的边 public Node(int value){ this.value = value; in = 0; out = 0; nexts = new ArrayList<>(); edges = new ArrayList<>(); } } 复制代码
表示法如何转换成图
假设现在有个数据，是一个二维数组，数据结构为[weight, from节点上面的值，to节点上面的值][]：
[ [5,0,1], // 表示权重为5的这个边从0这个点到1这个点 [3,1,2], [4,3,2] ] 复制代码
其中，[5,0,1]表示[weight, from节点上面的值，to节点上面的值]，
// matrix是一个N*3阶矩阵 // [weight, from节点上面的值，to节点上面的值] public static Graph createGraph(Integer[][] matrix){ Graph graph = new Graph(); for(int i = 0; i<matrix.length; i++){ Integer from = matrix[i][1]; Integer to = matrix[i][2]; Integer weight = matrix[i][0]; if(!graph.nodes.containsKey(from)){ gragh.nodes.put(from, new Node(from)); } if(!graph.nodes.containsKey(to)){ gragh.nodes.put(to, new Node(to)); } Node fromNode = gragh.nodes.get(from); Node toNode = gragh.nodes.get(to); Edge newEdge = new Edge(weight, fromNode, toNode); fromNode.nexts.add(toNode); fromNode.out++; toNode.in++; fromNode.edges.add(newEdge); graph.edges.add(newEdge); } return graph; } 复制代码
图的操作：宽度优先遍历
步骤
- 利用队列实现
- 从源节点开始依次按照宽度进队列，然后弹出
- 每弹出一个点，把该节点所有没有进过队列的邻接点放入队列
- 直到队列变空
Java版
public static void bfs(Node node){ if(node == null){ return; } Queue<Node> queue = new LinkedList<>(); HashSet<Node> set = new HashSet<>(); queue.add(node); set.add(node); while(!queue.isEmpty()){ Node cur = queue.poll(); System.out.printIn(cur.value); for(Node next: cur.nexts)){ if(!set.contains(next)){ set.add(next); queue.add(next); } } } } 复制代码
图的操作：深度优先遍历
思路先访问根节点，在对根节点的没访问过的相邻节点挨个进行深度优先遍历。步骤
- 利用栈实现
- 从源节点开始把节点按照深度放入栈，然后弹出
- 每弹出一个点，把该节点下一个没有进过栈的邻接点放入栈
- 直到栈变空
Java版
public static void dfs(Node node){ if(node == null){ return; } Stack<Node> stack = new Stack<>(); hashSet<Node> set = new HashSet<>(); stack.add(node); set.add(node); System.out.printIn(node.value); while(!stack.isEmpty()){ Node cur = stack.pop(); for(Node next: cur.nexts){ if(!set.contains(next)){ stack.push(cur); stack.push(next); set.add(next); System.out.printIn(next.value); break; } } } } 复制代码
Leetcode-65. 有效数字
解题思路
网络异常，图片无法展示
|
解题步骤
- 构建一个表示状态的图
- 遍历字符串，并沿着图走，如果到了某个节点无路可走就返回false
- 遍历结束，如走到3/5/6，就返回true，否则返回false
代码实现
var isNumber = function(s) { const graph = { 0:{'blank': 0, 'sign':1,'.':2,'digit':6}, 1:{'digit':6,'.':2}, 2:{'digit':3}, 3:{'digit':3,'e':4}, 4:{'digit':5,'sign':7}, 5:{'digit':5}, 6:{'digit':6,'.':3,'e':4}, 7:{'digit':5}, } let state = 0; for(c of s.trim()){ if(c>='0'&&c<='9'){ c='digit' }else if(c === ' '){ c='blank' }else if(c === '+'||c==='-'){ c='sign' } state = graph[state][c] if(state === undefined){ return false; } } if(state === 3 || state === 5 || state === 6){ return true } return false }; 复制代码
Leetcode-417. 太平洋大西洋水流问题
解题思路
- 将矩阵想象成图
- 从海岸线逆流而上遍历图，所到之处就是可以留到某个大洋的坐标
网络异常，图片无法展示
|
解题步骤
- 新建两个矩阵，分别记录能留到两个大洋的坐标
- 从海岸线，多管齐下，同时深度优先遍历图，过程中填充上述矩阵
- 遍历两个矩阵，找出能留到两个大洋的坐标
代码实现
var pacificAtlantic = function(matrix) { if(!matrix || !matrix[0]){ return []} const m = matrix.length; // 行数 const n = matrix[0].length; // 新建两个矩阵，分别记录能流到两个大洋的坐标 const flow1 = Array.from({ length: m }, () => new Array(n).fill(false)); const flow2 = Array.from({ length: m }, () => new Array(n).fill(false)); // 深度优先遍历，过程中填充flow1，flow2 const dfs = (r, c, flow) => { flow[r][c] = true; //遍历相邻节点 [[r-1, c],[r+1,c],[r,c-1],[r,c+1]].forEach(([nr,nc]) => { if( // 保证在矩阵中 nr >= 0 && nr < m && nc >= 0 && nc < n && // 保证未访问过，防止死循环 !flow[nr][nc] && // 保证逆流而上 matrix[nr][nc] >= matrix[r][c] ){ dfs(nr, nc, flow); } }) } // 沿着海岸线逆流而上 for(let r = 0; r < m; r += 1){ // 遍历第一列 dfs(r, 0, flow1); // 遍历最后一列 dfs(r, n -1, flow2); } for(let c = 0; c<n;c+=1){ dfs(0, c, flow1); dfs(m-1, c, flow2); } // 能流到两个大洋的坐标 const res = []; for(let r = 0;r<m;r+=1){ for(let c=0;c<n;c+=1){ if(flow1[r][c]&&flow2[r][c]){ res.push([r,c]) } } } return res }; 复制代码
Leetcode-133. 克隆图
解题思路
- 拷贝所有节点
- 拷贝所有的边
解题步骤
- 深度或广度优先遍历所有节点
- 拷贝所有的节点，存储起来
- 将拷贝的节点，按照原图的连接方法进行连接
代码实现
// 深度优先遍历 var cloneGraph = function(node) { if(!node) return; const visited = new Map(); const dfs = (n) => { const nCopy = new Node(n.val); visited.set(n, nCopy); (n.neighbors || []).forEach(ne=>{ if(!visited.has(ne)){ dfs(ne) } nCopy.neighbors.push(visited.get(ne)) }) }; dfs(node) return visited.get(node) }; 复制代码
时间复杂度：O(n)，访问了所有节点，n为节点数
空间复杂度：O(n)，有map这个数据结构。递归的空间复杂度<map这个数据结构
