0

私はJavaにかなり慣れていないので、この演習に2週間苦労しています（これは私の学校での宿題です）。トポロジカルソートを作成し、考えられるすべての接続を印刷する必要があります。トポロジカルソートについてはたくさん読んだことがありますが、この特定のコード行を処理する必要があります。頂点のリストがあれば、トポロジカルソートができると確信しています。私の問題は、この与えられたコードからすべての頂点をリストする方法がわからないことです。誰かが私にいくつかのヒントやリード、あるいはおそらく例を教えてもらえますか、私は本当にそれを感謝します。

使用する必要のある特定のコードは次のとおりです。

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」(true/false) を使用することをお勧めします。次に、1 つの頂点から開始します。グラフが接続されていると仮定すると、1 つの頂点の未訪問のエッジを通過し、エッジをたどって頂点に到達し、エッジを追跡済みとしてマークし、この頂点の count 関数を再帰的に呼び出すことで、すべての頂点に到達します。

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

グラフが有向グラフのように見えることも考慮する必要があることに注意してください。したがって、a から b および b から a につながるエッジは 2 つのエッジとしてカウントされます。

編集：私は間違いを犯しました。頂点を訪問済みとしてマークする必要もあります。そうしないと、2回訪問されます（無向グラフを考えていました）。

于 2012-11-29T13:55:47.690 に答える