图

1. 图是网络结构的抽象模型，是一组由边连接的节点
2. 图可以表示任何二元关系，比如道路、航班
3. js中没有图，但可以用Object和Array构建图
4. 图的表示法：邻接矩阵、邻接表、关联矩阵

图的常用操作

图的深度优先遍历

1. 访问根节点
2. 对根节点的没有访问的相邻节点挨个进行深度优先遍历

const graph = {
    0: [1, 2],
    1: [2],
    2: [0, 3],
    3: [3]
}

const visited = new Set()
const dfs = (n) => {
    console.log(n)
    visited.add(n)
    graph[n].forEach(c => {
        if (!visited.has(c)) {
            dfs(c)
        }
    })
}

图的广度优先遍历

1. 新建一个队列，把根节点入队
2. 把队头出队并访问
3. 把队头的没访问过的相邻节点入队
4. 重复二、三步，直到队列为空

const visited2 = new Set()
visited2.add(2)
const q = [2]
while (q.length) {
    const node = q.shift()
    console.log(node)
    graph[node].forEach(c => {
        if (!visited2.has(c)) {
            q.push(c)
            visited2.add(c)
        }
    })
}

LeetCode 65 有效的数字

function isNumber(s) {
    const graph = {
        0: { 'black': 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 = 'black'
        } else if(c === '+' || c === '-') {
            c = 'sign'
        } 

        state = graph[state][c]
        if(state === undefined) {
            return false
        }
    }

    if(state === 3 || state === 6 || state === 5) {
        return true
    }

    return false
}

LeetCode 133 克隆图

function cloneGraph(node) { 
    if (!node) return null;
    const visited = new Map();
    const dfs = (n) => {
        console.log(n.val)
        const clone = new Node(n.val);
        visited.set(n, clone);
        (n.neighbors || []).forEach(c => {
            if(!visited.has(c)){
                dfs(c);
            } 
            clone.neighbors.push(visited.get(c));
        });
    }

    dfs(node);
    return visited.get(node);
};