java 图着色算法：典型的调度问题
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2394098/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Graph colouring algorithm: typical scheduling problem
提问by neverMind
I'm training code problems like UvA and I have this one in which I have to, given a set of nexams and kstudents enrolled in the exams, find whether it is possible to schedule all exams in twotime slots.
我正在训练像 UvA 这样的代码问题，我有这个问题，给定一组n 次考试和k名参加考试的学生，找出是否可以在两个时间段内安排所有考试。
InputSeveral test cases. Each one starts with a line containing 1 < n < 200of different examinations to be scheduled. The 2nd line has the number of cases kin which there exist at least 1 student enrolled in 2 examinations. Then, klines will follow, each containing 2 numbers that specify the pair of examinations for each case above. (An input with n = 0 will means end of the input and is not to be processed).
输入几个测试用例。每一项都以一行包含1 < n < 200 个要安排的不同检查开始。第 2 行包含至少 1 名学生参加 2 次考试的案例数 k。然后，将跟随k行，每行包含 2 个数字，用于指定上述每个案例的检查对。（n = 0 的输入将意味着输入结束，不会被处理）。
Output:You have to decide whether the examination plan is possible or notfor 2 time slots.
输出：你必须决定检查计划是否可以或不可以为2个时隙。
Example:
例子：
Input:
输入：
3
3
0 1
1 2
2 0
9
8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0
Ouput:
输出：
NOT POSSIBLE.
POSSIBLE.
I think the general approach is graph colouring, but I'm really a newb and I may confess that I had some trouble understanding the problem. Anyway, I'm trying to do it and then submit it. Could someone please help me doing some code for this problem? I will have to handle and understand this algo now in order to use it later, over and over.
我认为一般的方法是图形着色，但我真的是一个新手，我可能承认我在理解这个问题时遇到了一些麻烦。无论如何，我正在尝试这样做然后提交。有人可以帮我为这个问题做一些代码吗？我现在必须处理和理解这个算法，以便以后一遍又一遍地使用它。
I prefer C or C++, but if you want, Java is fine to me ;)
我更喜欢 C 或 C++，但如果你愿意，Java 对我来说很好；)
Thanks in advance
提前致谢
采纳答案by neverMind
I've translated the polygenelubricant's pseudocode to JAVA code, in order to provide a solution for my problem. We have a submission platform (like uva/ACM contests), so I know it passed even in the problem with more and hardest cases.
我已将 polygenelubricant 的伪代码翻译成 JAVA 代码，以便为我的问题提供解决方案。我们有一个提交平台（比如 uva/ACM 比赛），所以我知道即使在更多和最困难的问题中它也通过了。
Here it is:
这里是：
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Scanner;
/**
*
* @author newba
*/
public class GraphProblem {
class Edge {
int v1;
int v2;
public Edge(int v1, int v2) {
this.v1 = v1;
this.v2 = v2;
}
}
public GraphProblem () {
Scanner cin = new Scanner(System.in);
while (cin.hasNext()) {
int num_exams = cin.nextInt();
if (num_exams == 0)
break;
int k = cin.nextInt();
Hashtable<Integer,String> exams = new Hashtable<Integer, String>();
ArrayList<Edge> edges = new ArrayList<Edge>();
for (int i = 0; i < k; i++) {
int v1 = cin.nextInt();
int v2 = cin.nextInt();
exams.put(v1,"UNKNOWN");
exams.put(v2,"UNKNOWN");
//add the edge from A->B and B->A
edges.add(new Edge(v1, v2));
edges.add(new Edge(v2, v1));
}
boolean possible = true;
for (Integer key: exams.keySet()){
if (exams.get(key).equals("UNKNOWN")){
if (!colorify(edges, exams,key, "BLACK", "WHITE")){
possible = false;
break;
}
}
}
if (possible)
System.out.println("POSSIBLE.");
else
System.out.println("NOT POSSIBLE.");
}
}
public boolean colorify (ArrayList<Edge> edges,Hashtable<Integer,String> verticesHash,Integer node, String color1, String color2){
verticesHash.put(node,color1);
for (Edge edge : edges){
if (edge.v1 == (int) node) {
if (verticesHash.get(edge.v2).equals(color1)){
return false;
}
if (verticesHash.get(edge.v2).equals("UNKNOWN")){
colorify(edges, verticesHash, edge.v2, color2, color1);
}
}
}
return true;
}
public static void main(String[] args) {
new GraphProblem();
}
}
I didn't optimized yet, I don't have the time right new, but if you want, you/we can discuss it here.
我还没有优化，我没有时间做新的，但如果你愿意，你/我们可以在这里讨论。
Hope you enjoy it! ;)
希望你喜欢它！;)
回答by polygenelubricants
You are correct that this is a graph coloring problem. Specifically, you need to determine if the graph is 2-colorable. This is trivial: do a DFS on the graph, coloring alternating black and white nodes. If you find a conflict, then the graph is not 2-colorable, and the scheduling is impossible.
您是正确的，这是一个图形着色问题。具体来说，您需要确定图形是否为 2 色。这是微不足道的：在图上做一个 DFS，为交替的黑白节点着色。如果发现冲突，则该图不是 2-colorable 的，并且调度是不可能的。
possible = true
for all vertex V
color[V] = UNKNOWN
for all vertex V
if color[V] == UNKNOWN
colorify(V, BLACK, WHITE)
procedure colorify(V, C1, C2)
color[V] = C1
for all edge (V, V2)
if color[V2] == C1
possible = false
if color[V2] == UNKNOWN
colorify(V2, C2, C1)
This runs in O(|V| + |E|)with adjacency list.
这O(|V| + |E|)与邻接表一起运行。
回答by Antti Huima
in practice the question is if you can partition the n examinations into two subsets A and B (two timeslots) such that for every pair in the list of k examination pairs, either a belongs to A and b belongs to B, or a belongs to B and b belongs to A.
在实践中的问题是，是否可以将 n 个考试划分为两个子集 A 和 B（两个时隙），使得对于 k 个考试对列表中的每一对，要么 a 属于 A，b 属于 B，要么 a 属于B 和 b 属于 A。
You are right that it is a 2-coloring problem; it's a graph with n vertices and there's an undirected arc between vertices a and b iff the pair or appears in the list. Then the question is about the graph's 2-colorability, the two colors denoting the partition to timeslots A and B.
你是对的，这是一个 2 着色问题；它是一个具有 n 个顶点的图，并且顶点 a 和 b 之间有一个无向弧，如果该对或出现在列表中。然后问题是关于图的 2-colorability，这两种颜色表示时隙 A 和 B 的分区。
A 2-colorable graph is a "bipartite graph". You can test for bipartiteness easily, see http://en.wikipedia.org/wiki/Bipartite_graph.
2-colorable 图是“二部图”。您可以轻松测试二分性，请参阅http://en.wikipedia.org/wiki/Bipartite_graph。
