0

これは非常に素朴に聞こえるかもしれませんが、C言語でグラフを実装する方法を誰かが説明してくれませんか. 理論は読みましたが、グラフプログラミングのブロックから抜け出せません。

隣接リストと隣接行列を使用してグラフを作成する方法と、Cコードで幅優先検索と深さ優先検索を実行する方法を説明していただければ幸いです。

そして何よりも、これは宿題ではないことをお伝えしたいと思います。グラフを本当に学びたいのですが、家庭教師を雇う余裕がありません。

4

2 に答える 2

2

ここで、グラフは頂点とエッジのコレクションであると仮定します。そのためには、構造体へのポインターの配列が必要になります。これはグラフの隣接リスト表現です。これらの構造体は、少なくともノード番号と別の構造体へのポインタである値を持ちます。グラフに新しいノードを挿入するときは、配列の適切なインデックスに移動し、最初にノードをプッシュします。これは、挿入に O(1) 回です。私の実装は、それが実際にどのように機能するかを理解するのに役立つかもしれません. C のスキルがあれば、コードを理解するのにそれほど時間はかかりません。

//  Graph implementation by adjacency list

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 1000

typedef struct node{
    int number;
    struct node * next;
} Node;


//  U is starting node, V is ending node
void addNode (Node *G[], int U, int V, int is_directed)
{
    Node * newnode = (Node *)malloc(sizeof(Node));
    newnode->number = V;
    newnode->next = G[U];
    G[U] = newnode;

//  0 for directed, 1 for undirected
    if (is_directed)
    {
        Node * newnode = (Node *)malloc(sizeof(Node));
        newnode->number = U;
        newnode->next = G[V];
        G[V] = newnode;
    }
}

void printgraph(Node *G[], int num_nodes)
{
    int I;
    for (I=0; I<=num_nodes; I++)
    {
        Node *dum = G[I];
        printf("%d : ",I);
        while (dum != NULL)
        {
            printf("%d, ",dum->number);
            dum =dum->next;
        }
        printf("\n");
    }

}



void dfs (Node *G[], int num_nodes, int start_node)
{
    int stack[MAX_SIZE];
    int color[num_nodes+1];
    memset (color, 0, sizeof(color));
    int top = -1;
    stack[top+1] = start_node;
    top++;
    while (top != -1)
    {
        int current = stack[top];
        printf("%d  ",current);
        top--;
        Node *tmp = G[current];
        while (tmp != NULL)
        {
            if (color[tmp->number] == 0)
            {
                stack[top+1] = tmp->number;
                top++;
                color[tmp->number] = 1;
            }
            tmp = tmp->next;
        }
    }

}

void bfs (Node *G[], int num_nodes, int start_node)
{
    int queue[MAX_SIZE];
    int color[num_nodes+1];
    memset (color, 0, sizeof (color));
    int front=-1, rear=-1;
    queue[rear+1] = start_node;
    rear++;printf("\n\n");
    while (front != rear)
    {
        front++;
        int current = queue[front];
        printf("%d  ",current);

        Node *tmp = G[current];
        while (tmp != NULL)
        {
            if (color[tmp->number] == 0)
            {
                queue[rear+1] = tmp->number;
                rear++;
                color[tmp->number] = 1;
            }
            tmp = tmp->next;
        }
    }

}  

int main(int argc, char **argv)
{
    int num_nodes;
    // For Demo take num_nodes = 4
    scanf("%d",&num_nodes);
    Node *G[num_nodes+1];
    int I;
    for (I=0; I<num_nodes+1 ;I++ )
        G[I] = NULL;

    addNode (G, 0, 2, 0);
    addNode (G, 0, 1, 0);
    addNode (G, 1, 3, 0);
    addNode (G, 2, 4, 0);
    addNode (G, 2, 1, 0);
    printgraph( G, num_nodes);
    printf("DFS on graph\n");
    dfs(G, num_nodes, 0);
    printf("\n\nBFS on graph\n");
    bfs(G, num_nodes, 0);

    return 0;
}
于 2012-07-18T16:36:32.657 に答える
0

まあ、本当の素朴で基本的な答えは、他のそのようなデータ構造へのポインターを含むデータ構造を使用して、C でグラフを表すことができるということです。グラフは、単一のノードから複数のリンクを持つことができる、二重にリンクされたリストです。リンクされたリストと二重にリンクされたリストを消化していない場合は、そこから始めるのが良いでしょう。

隣接リスト {a,b},{b,c},{d},{b,e} があるとします。まず、それを解析して、すべての一意のアイテムのリストを作成します。(通常のリンクされたリスト、配列、何でも、それはあなたを助けるための単なる一時的な構造です。それをバイパスして、その場でそれを行うことで、おそらくスピードアップを得ることができますが、これは簡単です。) そのリストをたどると、各アイテムのノード。ノードごとに、隣接リストを再度調べて、それ自体が認識されたときにエッジを作成します。これは、別のノードを指すノード内のポインターです。

最終的に、すべてのノードの定期的なリストが作成されるため、単独でぶら下がっている唯一の 'd' ノードを失うことはありません。また、すべてのノードのグラフがあるため、相互の関係がわかります。

検索
グラフ全体を検索することは、かなり基本的な考え方です。ノードで開始し、比較し、その隣接ノードの 1 つに移動して、もう一度実行します。とはいえ、落とし穴がたくさんあります。無限ループに入って、いつ停止するかを知るようなものです。

すでにオンラインで見つけられるものよりも良い説明が必要な場合は、より具体的な質問をする必要があります.

于 2012-07-18T16:49:40.923 に答える