隣接リストを使用した重み付けされていないグラフ

Question

私はプログラミングに慣れていないので、自分でデータ構造を学習しようとしています。私は隣接リストを使用して重み付けされていないグラフクラスを実装しようとしていますが、getAdjacentVerticesメソッドの実装に問題があります。私は本当にこのトピックを説明していない使用しています。*

enter code here 
public class Graph { 
    private ArrayList<Integer> vertices; 
    private ListNode[] edges; 
    private int vertexCount = 0; 
    public Graph(int vertexCount){ 
     this.vertexCount = vertexCount; 
     vertices = new ArrayList<Integer>(); 
     edges = new ListNode[vertexCount]; 
     for(int i = 0; i < vertexCount; i++){ 
      vertices.add(i); 
      edges[i] = new ListNode(); 
     } 
    } 
    public void addEdge(int source, int destination){ 
     int i = vertices.indexOf(source); 
     int j = vertices.indexOf(destination); 
     if(i != -1 || j != -1){ 
      edges[i].insertAtBeginning(destination); 
      edges[j].insertAtBeginning(source); 
     } 
    } 
    public int getNumberVertices() { 
     return vertexCount; 
    } 
    public Object getAdjacentVertices(int currentVertex) { 

    } 
} 

Answer 1

を

• getAdjacentVertices(i)は、単にedgesのi番目の要素を返すことができ、あなたの質問に答えるために。
• addEdge()最初に追加する必要はありません。ネイバーリストに注文を課す特定の理由がない限り、ほとんどのグラフアルゴリズムはネイバーリストを必要としません。

他のいくつかのポイント：

• グラフの頂点は、伝統的に0からnに番号が付けられている - 1だからあなたの頂点がペイロード（名前、コストなど）を持っていない限り、あなたが離れて行うことができますverticesアレイ。
• はそれを明確にグラフが（vがuのリストに表示されたときにそれは、ある無向であることを確認するために、あなたのクラスUndirectedGraphを命名考えてみましょう隣人の隣人、uもvのリストに表示されます "。
• が使用することを検討してくださいお使いの隣接リストのためのList<Integer>とLinkedListとしてそれを実装しています。ほとんどのグラフアルゴリズムは隣接リストを反復する機能、ない（ArrayListが提供する）ランダムアクセスを必要とする。
• addEdge()行わず検証。入力された場所に応じてあなたは0≤をチェックしたいかもしれません210 < vertexCountであり、エッジ(u, v)はまだ存在していません。

簡潔にするために同じクラスにmain()メソッドを含めました。

import java.util.LinkedList; 
import java.util.List; 
import java.util.Vector; 

public class UndirectedGraph { 
    private Vector<List<Integer>> edges; 
    private int vertexCount = 0; 

    public UndirectedGraph(int vertexCount) { 
    this.vertexCount = vertexCount; 
    edges = new Vector<List<Integer>>(vertexCount); 
    for (int i = 0; i < vertexCount; i++){ 
     edges.addElement(new LinkedList<Integer>()); 
    } 
    } 

    public void addEdge(int u, int v) { 
    edges.get(u).add(v); 
    edges.get(v).add(u); 
    } 

    public int getNumberVertices() { 
    return vertexCount; 
    } 

    public Object getAdjacentVertices(int u) { 
    return edges.get(u); 
    } 

    public static void main(String [] args) { 
    UndirectedGraph g = new UndirectedGraph(4); 
    g.addEdge(0, 1); 
    g.addEdge(0, 2); 
    g.addEdge(1, 2); 
    g.addEdge(1, 3); 
    g.addEdge(2, 3); 

    for (int i = 0; i < g.getNumberVertices(); i++) { 
     System.out.println("Neighbors of node " + i + ": " + g.getAdjacentVertices(i)); 
    } 
    } 
}