그래프의 모든 정점 수를 계산하십시오.

Question

저는 자바를 처음 접했고 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 
} 

Answer 1

는 분명히, 그래프가 첫 번째 정점에 대한 참조를 가지고 있으며, 정점 자체가 단일 연결리스트에 함께 연결되어 있습니다 : 여기

우리가 작업 할 필요가 주어진 코드입니다. 이 코드는 자바 목록에 정점을 수집하는 데 필요한 모든해야한다 :

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를에서에서 선도, 당신은 또한 그래프가 유향 그래프로 나타납니다 고려해야 할 점에 유의하시기 바랍니다.

편집 : 실수로 방문한 꼭지점을 표시해야하거나 두 번 방문하게됩니다 (나는 무향 그래프를 생각하고있었습니다).