2

適切なノードとリンクを使用してグラフを作成するために作成する必要がある隣接リストの種類を教えてもらえますか？ajdacencyリストを定義するためにツリー構造を作成する必要がありますか？または別の方法はありますか？
今はマトリックスに興味がない、ありがとう。

たとえば、エッジの他のノードのすべての位置にある他のアラーリストとの配列リストを作成して、次のようにすることはできますか？

nodes {a,b,c}, connection {{a-c},{b,c}}

だから私はarraylistまたは私の隣接リストを持っています[a[c],b[c],c[a,b]]

4

3 に答える 3

2

隣接リストは、どのノードが相互に接続されているかを表すだけです。

次のノード1〜4のグラフがある場合、隣接行列は次のようになります。「1」はノード間の接続を表します。

    1 2 3 4
 1  1 1 1 1
 2  1 0 0 0
 3  0 1 0 1
 4  0 1 1 0

リストは次のようになります。->リンクを表します

 1  -> 1 -> 2 -> 3 -> 4
 2  -> 1
 3  -> 2 -> 4
 4  -> 2 -> 3

上記のように配列でリンクリストを使用して、配列にノード1〜4が含まれるようにすることについて考えてみてください。次に、別のノードへの接続を表すメンバー変数を使用するか、配列の各要素内に個別の配列リストを作成できます。 。

于 2012-05-24T15:58:10.933 に答える
0

ArrayListsのArrayList（またはより一般的にはリストのリスト）は、そうするのに良い方法です。これは、隣接リストの非常に標準的な表現です。だからあなたのアイデアは良いです。

また、グラフのサイズ（ノードの数）が事前にわかっていて、作成後にノードを追加する必要がない場合は、ArrayListsの配列も必要であり、いくらか効率的です。

于 2012-05-24T16:02:45.783 に答える
0

を使用して隣接リストを実装できますDictionary。辞書の各キーは、エッジの開始ノードを表します。各値はListオブジェクトの値であり、それぞれがエッジの宛先ノードを定義します。

たとえば、各キーListにのを格納できます。Tuplesの最初の項目はTuple、宛先ノードを表します。他の項目は、エッジのプロパティを定義します。

class AdjacencyList
{

    Dictionary<int, List<Tuple<int, int>>> adjacencyList;

    // Constructor - creates an empty Adjacency List
    public AdjacencyList(int vertices)
    {
        adjacencyList = new Dictionary<int, List<Tuple<int, int>>>();
    }

    // Appends a new Edge to the linked list
    public void addEdge(int startVertex, int endVertex, int weight)
    {
        if (!adjacencyList.ContainsKey(startVertex)) {
            adjacencyList[startVertex] = new List<Tuple<int, int>>();
        }

        adjacencyList[startVertex].Add(new Tuple<int, int>(endVertex, weight));
    }

    // Removes the first occurence of an edge and returns true
    // if there was any change in the collection, else false
    public bool removeEdge(int startVertex, int endVertex, int weight)
    {
        Tuple<int, int> edge = new Tuple<int, int>(endVertex, weight);

        return adjacencyList[startVertex].Remove(edge);
    }
}
于 2016-03-18T00:17:42.843 に答える