0

我对 java 还很陌生，我已经为这个练习苦苦挣扎了两个星期（这是我学校的家庭作业）。我需要创建一个拓扑排序并打印出所有可能的连接。我现在已经阅读了很多关于拓扑排序的内容，但是我们必须使用这行特定的代码。当我有顶点列表时，我很确定我可以进行拓扑排序。我的问题是，我不知道如何列出这个给定代码中的所有顶点。谁能给我一些提示或线索或者一个例子，我真的很感激。

这是我们需要使用的给定代码：

import java.util.*;

public class Answer {

   public static void main (String[] args) {
      Answer a = new Answer();
      a.run();
   }

   public void run() {

      // TODO!!! YOUR TESTS HERE!

      Graph g = new Graph ("G");
      Vertex a = new Vertex ("A");
      Vertex b = new Vertex ("B");
      Vertex c = new Vertex ("C");
      g.first = a;
      a.next = b;
      b.next = c;
      Edge ab = new Edge ("AB");
      Edge ac = new Edge ("AC");
      Edge ba = new Edge ("BA");
      Edge ca = new Edge ("CA");
      a.first = ab;
      b.first = ba;
      c.first = ca;
      ab.next = ac;
      ab.target = b;
      ac.target = c;
      ba.target = a;
      ca.target = a;
      System.out.println (g);
   }


   class Vertex {

      String id;
      Vertex next;
      Edge first;

      Vertex (String s, Vertex v, Edge e) {
         id = s;
         next = v;
         first = e;
      } 

      Vertex (String s) {
         this (s, null, null);
      }

      @Override
      public String toString() {
         return id;
      }

      // TODO!!! Your Vertex methods here!

   } // Vertex


   class Edge {

      String id;
      Vertex target;
      Edge next;

      Edge (String s, Vertex v, Edge e) {
         id = s;
         target = v;
         next = e;
      }

      Edge (String s) {
         this (s, null, null);
      }

      @Override
      public String toString() {
         return id;
      }

      // TODO!!! Your Edge methods here!

   } // Edge


   class Graph {

      String id;
      Vertex first;

      Graph (String s, Vertex v) {
         id = s;
         first = v;
      }

      Graph (String s) {
         this (s, null);
      }

      @Override
      public String toString() {
         String nl = System.getProperty ("line.separator");
         StringBuffer sb = new StringBuffer (nl);
         sb.append (id + nl);
         Vertex v = first;
         while (v != null) {
            sb.append (v.toString() + " --> ");
            Edge e = v.first;
            while (e != null) {
               sb.append (e.toString());
               sb.append ("(" + v.toString() + "->" 
                  + e.target.toString() + ") ");
               e = e.next;
            }
            sb.append (nl);
            v = v.next;
         }
         return sb.toString();
      }

      // TODO!!! Your Graph methods here!

   } // Graph
}
4

2 回答 2

2

显然，该图具有对第一个顶点的引用，并且这些顶点本身链接在一起形成一个单链表。这段代码应该是您将顶点收集到 Java 列表中所需的全部内容：

public List<Vertex> allVertices(Graph g) {    
  final List<Vertex> vertices = new ArrayList<>();
  for (Vertex v = g.first; v != null; v = v.next)
     vertices.add(v);
  return vertices;
}
于 2012-11-29T13:55:01.873 回答
1

我建议您将“lastvisited”整数字段添加到设置为零的边缘，或使用布尔值“visited”（真/假）。然后从一个顶点开始。假设图是连接的，您将通过遍历一个顶点的未访问边来到达所有顶点，然后沿着边到达它通向的顶点，将边标记为跟随，并递归地调用该顶点的计数函数。

I.E.: count(node) = sum(my unvisited edges) mark_edge_as_visited(edge), count(edge.target)

请注意，您还必须考虑该图似乎是有向图，因此从 a 到 b 和从 b 到 a 的边被计为两条边。

编辑：我犯了一个错误，您还需要将顶点标记为已访问，否则它将被访问两次（我在考虑无向图）。

于 2012-11-29T13:55:47.690 回答