Java图形着色程序

我被要求创建一个Java程序，其中我首先接受预定义数量的顶点，然后将图形中存在的所有边作为数字对。我的代码应该接受边缘，创建'图形'并为所有顶点着色。我的问题是与着色。 'setColor'方法应该在每次调用时接受图的度数。 getBiggestVertex方法应该返回要着色的顶点。它被着色。但是，由于某些原因，当我显示顶点的颜色时，我总是得到0或1或-1。Java图形着色程序

我无法弄清楚为什么我得到这个输出，有人可以帮忙吗？

由于

图类：

import java.util.ArrayList; 
import java.util.Scanner; 


public class Graph { 
    ArrayList <Vertex> vertices = new ArrayList<Vertex>(); 
    public Graph(){ 
     Scanner sc = new Scanner(System.in); 
     int noOfVertices = sc.nextInt(); 

     for(int i = 0; i <noOfVertices; i++){ 
      addVertex(); 
     } 

     String input = sc.next(); 

     while(!input.equals("-1")){ 
      String vertex [] = input.split(","); 
      addEdge(vertices.get(Integer.parseInt(vertex[0])), vertices.get(Integer.parseInt(vertex[1]))); 
      input = sc.next(); 
     } 
     for(int i = 0; i<vertices.size(); i++){ 
      getBiggestVertex().setColor(vertices.size()); 
     } 
    } 

    public Vertex getBiggestVertex(){ 
     Vertex bVertex = new Vertex(-1); 
      for(int i = 0; i < vertices.size(); i++){ 
       Vertex v = vertices.get(i); 
       if(v.colour ==-1){ 
        if(v.getDegree() > bVertex.getDegree()){ 
         bVertex = v; 
        } else if(v.getDegree() == bVertex.getDegree()){ 
         if(v.vertexNumber < bVertex.vertexNumber){ 
          bVertex = v; 
         } 
        } else if(v.getDegree() < bVertex.getDegree()){ 

        } 
       } 
      } 
     return bVertex; 
    } 
    public void addVertex(){ 
     vertices.add(new Vertex(vertices.size())); 
    } 

    public Vertex getVertex(int index){ 
     return vertices.get(index); 
    } 

    public void addEdge(Vertex v1, Vertex v2){ 
     v1.addAdjacency(v2); 
     v2.addAdjacency(v1); 
    } 

}

顶点类别：

import java.util.LinkedList; 


public class Vertex { 
    int vertexNumber, colour; 
    LinkedList <Vertex> adjacencies = new LinkedList<Vertex>(); 
    public Vertex(int vertexNum){ 
     vertexNumber = vertexNum; 
     colour = -1; 
    } 
    public void addAdjacency(Vertex v){ 
     adjacencies.add(v); 
    } 
    public boolean isAdjacent(Vertex v){ 
     boolean adj = false; 
     for(int i = 0; i < adjacencies.size(); i++){ 
      if(adjacencies.get(i) == v){ 
       adj = true; 
      } 
     } 
     return adj; 
    } 
    public int getDegree(){ 
     return adjacencies.size(); 
    } 
    public void setColor(int degree){ 
     int [] used = new int[degree]; 
     for(int i = 0; i < adjacencies.size(); i++){ 
      int c = adjacencies.get(i).colour; 
      System.out.println("Color of " + i + " = " + c); 
      used[c+1] = 1; 

     } 
     int unusedColor = 0; 
     while(used[unusedColor] == 1){ 
      unusedColor ++; 
     } 
     colour = unusedColor; 
    } 
}

来源

2015-11-10 Marko Vidalis

我假定-1表示尚未定义顶点颜色。

有与您的代码的几个问题，其中中心的大部分周围setColor方法：

当检查相邻顶点的颜色的色码的范围由1转移到作为索引到使用标记阵列used。但是，在拜访过所有邻居之后，您测试的第一种颜色是0。

该过程使仅具有无色邻居的顶点着色为1。如果所有邻居都已上色，则分配的颜色将为0。

此外在getBiggestVertex，条件(v.vertexNumber < bVertex.vertexNumber)将永远不会触发对顶点为0的出度时没有指定的颜色的所有剩余顶点具有出度0（bVertex被初始化为-1的最小顶点数和将永远不会被重新安排）。

这意味着您可能会生成相同颜色的顶点路径。值得注意的是，下面的曲线图将给出一个无效的着色：

4,5 
4,6 
4,7 
4,3 
3,8 
3,9 
3,2 
2,10 
2,1 
9,2

导致着色

c(1) = -1 
c(2) = 1 
c(3) = 1 
c(4) = 1 
c(5) = -1 
c(6) = -1 
c(7) = -1 
c(8) = -1 
c(9) = 0 
c(10) = -1 
c(11) = -1

其中节点3将需要一个新的颜色2和-1是一个无效颜色（其可以被解释前当然有效）。

通过

维持双向邻接整顿代码（以便a,b意味着a邻近b反之亦然）
写入used[c]代替used[c+1]。

或检查先前顶点的颜色。

除了有缺陷的颜色分配，请考虑以下建议，以提高你的代码：

最大程度的图形的属性，因此应该是图形类的属性。因此，您不需要分配当前顶点数的最差情况度数 - setColor中的used数组的值为1。
与图中的最高等级的节点（多个）不需要从头开始重新计算在每次使用，也可以是图形类的属性以及
以先前的建议一步，您可以在存储此列表的着色过程之前通过降低度数来对图的顶点排序。您应该可以免除对getBiggestVertex的重复呼叫，您可以按照它们在列表中显示的顺序访问节点。

来源

2015-11-11 01:12:43 collapsar

Java图形着色程序

回答

相关问题