对图形进行 BFS 适当着色

Question

从顶点 0 开始，我将颜色 1 分配给顶点 0，然后将颜色分配给与顶点 0 相邻的所有顶点，然后将颜色分配给与顶点的距离最短的所有顶点0 是 2，依此类推，直到所有顶点都被着色。我运行遇到了一个问题，当运行我的代码时，我的图表的 "colors" 总是 returning 0。程序的输出应该是

但我在 return 中得到的只是

我在下面发布了我是运行的代码，在尝试解决此问题时将不胜感激任何帮助，请记住我有一个单独的 class 调用它并在.

public class P7BFSColorGraph {
int[] colorArray;
ArrayList<Integer> colorList;


public P7BFSColorGraph(Graph G) {
    colorList = new ArrayList<Integer>();
    colorArray = new int[G.V()];


    SimplerBreadthFirstPaths graph = new SimplerBreadthFirstPaths(G,0);
    for(int dis=0;dis<G.V();dis++) {
        for(int ver=0;ver<G.V();ver++) {
            if(graph.distTo(ver) == dis) {
                if (colorArray[ver] != 0)
                    colorList.add(colorArray[ver]);
                findUnusedColor(colorList);
                colorArray[ver] = findUnusedColor(colorList);
            }
        }

    }

}

public int vertexColor(int v ) {
    if(colorArray[v] != 0) {
        return colorArray[v];
    }
    return 0;
}

private int findUnusedColor(ArrayList<Integer> list) {
    list.sort(null);
    list.add(0, 0);
    for (int i = 0; i < list.size()-1; i++) {
        if (list.get(i+1)-list.get(i)>1) {
            return list.get(i)+1;
        }
    }
    return list.get(list.size()-1)+1;
}

}

Answer 1

编辑：@Diasiare 提出了一个很好的观点（着色与遍历有何不同）。您的方法应该保证没有两个相邻的顶点具有相同的颜色，但我不确定它会产生所需的结果。如果没有，您能否编辑您的问题以包含输入图，显示节点和边。

可能的解决方案：

您的代码存在的问题与距离和颜色之间没有参考有关。 Map 在这里是一个不错的选择，但坚持您的代码风格，将使用一个名为 distArray 的数组。该数组保存给定距离的颜色。根据需要分配新颜色（当检测到新距离时）。跟随将产生您期望的结果。

List<Integer> colorList = new ArrayList<Integer>();
int[] colorArray = new int[G.V()];
int[] distArray = new int[G.V()];
SimplerBreadthFirstPaths graph = new SimplerBreadthFirstPaths(G,0);

for (int dis = 0; dis < G.V(); dis++) {
    for (int ver = 0; ver < G.V(); ver++) {
        if (G.distTo(ver) == dis) {
            if (distArray[dis] == 0) {
                // Only assign a new color when a new distance occurs
                distArray[dis] = findUnusedColor(colorList);
                colorList.add(distArray[dis]);
            } 
            // Assign the color based on it's distance
            colorArray[ver] = distArray[dis];
        }
    }
}

这是运行算法的更有效方法（不需要双循环，即 O(n^2) - 你可以运行这在 O(n)

for (int ver = 0; ver < G.V(); ver++) {
    int dis = G.distTo(ver);
    if (distArray[dis] == 0) {
        distArray[dis] = findUnusedColor(colorList);
        colorList.add(distArray[dis]);
    }
    colorArray[ver] = distArray[dis];
}

对图形进行 BFS 适当着色

Doing a BFS proper coloring on a graph

java

breadth-first-search

graph-coloring