1

次のようなテキスト ファイルからデータのリストを格納するグラフを実装しようとしています。

0,1 (node 0 links to 1)
0,2 (node 0 links to 2)
1,2 (node 1 links to 2)
2,1 (node 2 links to 1)

とにかく、構造を定義することになると、私は問題に遭遇します。マトリックスを使用するか、隣接するリストを使用するかで迷っていますが、リストを使用すると思います。構造を定義する方法がわかりません。可変サイズの配列、リンクされたリスト、または何か他のものを使用する必要がありますか? どの方法が最も簡単でしょうか?

struct grph{

};

struct node{

    //ID of the node
    int id;

};

第二に、このグラフにデータを保存するにはどうすればよいですか。ここで最も問題が発生します。基本的には、連結リストのように最後にノードを追加していくだけで簡単だと思っていました。ここでの違いは、各ノードが多くの異なるノードを指している場合もあれば、まったくノードを指していない場合もあるということです。グラフ構造をすべてのリンクされたノード構造とリンクするにはどうすればよいですか?

たとえば、リンクされたリストを使用する場合、上記の例でノード 0 が接続するものをどのように保存しますか? マトリックスまたはリスト/配列を使用していることは理解していますが、C でそのような実装の例が不足しているため、真剣に混乱しています。

4

4 に答える 4

1

最初の質問への答え: 隣接行列と隣接リスト? グラフが密であると予想される場合、つまり、ほとんどのノードが他のほとんどのノードに隣接している場合は、マトリックスを使用します。ほとんどの操作はマトリックスの方がはるかに簡単です。推移閉包が本当に必要な場合は、行列が密になる傾向があるため、行列もおそらく優れています。それ以外の場合、隣接リストは高速で小さくなります。

グラフは次のようになります。

typedef struct node * node_p;
typedef struct edge * edge_p;

typedef struct edge
{       node_p  source, target;
        /* Add any data in the edges */
} edge;

typedef struct node
{       edge_p  * pred, * succ;
        node_p  next;
        /* Add any data in the nodes */
} node;

typedef struct graph
{       node_p  N;
} graph;

のNフィールドは、リストをリンクするために のフィールドをgraph使用して、グラフのノードのリンクされたリストを開始します。andは、andを使用して、グラフ内の後続エッジと先行エッジに割り当てられた配列にすることができます(エッジへのポインターの配列と終端)。後継者と先行者の両方を保持することは冗長に思えるかもしれませんが、ほとんどのグラフ アルゴリズムは、両方の方法を実行できることを好むことがわかります。エッジのandフィールドは、ノードに戻ります。エッジにデータを格納する予定がない場合は、および配列がノードを直接指すようにして、型を忘れることができます。nextnodepredsuccmallocreallocNULLsourcetargetpredsuccedge

ノードのすべてのアドレスが変更される可能性があり、これらはグラフの残りの部分で頻繁に使用されるため、でrealloconを使用しないでください。Ngraph

NULLPS: 個人的には、終了したリンクリストよりも循環リンク リストの方が好きです。その場合、ポインターの代わりにgraph(ダミー) が含まれます。node

于 2013-03-30T23:48:31.943 に答える
1

これはほんの一例です:

struct node{
        int id; 
        struct node **out;
        int num_out;
        /* optional: if you want doubly links */
        struct node **in;
        int num_in;
};

/* quick access to a node given an id */
struct node *node_list;

/* connect 'from' to 'to' */
void link(struct node *graph, int from, int to) {
        struct node *nfrom = &node_list[from], 
                    *nto   = &node_list[to];
        nfrom->num_out++;
        nfrom->out = realloc(nfrom->out, 
             sizeof(struct node*) * nfrom->num_out);
        nfrom->out[num_out-1] = nto;
        /* also do similar to nto->in if you want doubly links */
}
于 2013-03-30T23:35:51.640 に答える