图之其他问题

二分图

Map<Integer, Set<Integer>> graph = new HashMap<>();;
int [] colors = new int[ ];

for (int i = 1; i <=n ; i++) {
    if(colors[i]==0 && !canColor(i,1)){
        return false;
    }
}

染色法

BFS

1. 将首个节点染色为1，放入队列
2. 从队列中取一个，并获取其邻接节点
   1. 已经染色：如果颜色相同，则不能完成染色
   2. 未染色：染色成另一种颜色，加入队列
3. 知道队列为空

private boolean canColorBFS(int nodeId, int color) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(nodeId);
    colors[nodeId] = color;
    while (!queue.isEmpty()){
        Integer current = queue.poll();
        Set<Integer> nodes = graph.get(current);
        for (Integer nextId : nodes) {
            if(colors[nextId] != 0){
                if(colors[nextId] == colors[current]){
                    return false;
                }
            }else {
                colors[nextId] = 3^colors[current];
                queue.offer(nextId);
            }
        }
    }
    return true;
}

DFS

1. 染色当前节点
2. 获取当前节点的相邻节点，枚举相邻节点
   1. 若相邻节点没有染色，试着染成相反颜色，失败则不能染色
   2. 若已经染色，若颜色相同则不能完成染色

private boolean canColorDFS(int nodeId, int color) {
    colors[nodeId] = color;
    Set<Integer> nodes = graph.get(nodeId);
    for (Integer node : nodes) {
        if(colors[node] == 0){
            if(!canColorDFS(node,3^color)){
                return false;
            }
        }else {
            if(colors[node] == colors[nodeId] ){
                return false;
            }
        }
    }
    return true;
}