統計圖中的所有頂點

Question

我對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 
} 

Answer 1

顯然，圖中有第一個頂點的引用和頂點本身連接在一起成一個單向鏈表。此代碼應該是所有你需要收集頂點到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; 
} 

Answer 2

我建議你添加一個「lastvisited」整場被設置爲零的邊緣，或者使用走訪了布爾」 「（真假）。然後從一個頂點開始。假設圖形已連接，您將遍歷一個頂點的未訪問邊，然後沿着邊到達它所引起的頂點，將邊標記爲後面，並遞歸調用此頂點的計數函數，從而到達所有頂點。

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

請注意，您還必須考慮該圖形似乎有向圖，所以邊緣從領先到B，從B到A計爲兩條邊。

編輯：我犯了一個錯誤，你還需要將頂點標記爲已訪問，或者它將被訪問兩次（我正在考慮一個無向圖）。