0

だから私は次のようなグラフを持っているとしましょう

6 7
1 2 -2
2 3 -1
3 1 -4
3 4 -2
3 5 -3
6 4 -1
6 5 -4

ここで、最初の行はそれぞれノードの数とエッジの数を示し、残りはエッジと重みを読み取ります。このグラフから入力を読み取る方法を知っています。

私の質問は、最初の行でノードの数 (または何か) を指定せずに、このグラフのエッジと重みをどのように読み取るかです。たとえば、同じことを行うには、このグラフをどのように読み取るか...

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

ありがとう！

Here is my current code

FILE *fin = fopen(argv[1], "r");
        fscanf(fin, "%d", &n);
        e = 0;

        for (i = 0; i < n; ++i)
            for (j = 0; j < n; ++j) {
                fscanf(fin, "%d", &w);
                if (w != 0) {
                    edges[e].u = i;
                    edges[e].v = j;
                    edges[e].w = w;
                    ++e;
                }
            }
4

2 に答える 2

0

グラフの実装と、ノードを動的に挿入できるかどうかに少し依存します。各行について、2 つのノードを読み取り、いずれかまたは両方が現在グラフに存在しない場合は、それらを挿入してからエッジを挿入する必要があります。マトリックス表現を使用している場合は、マトリックスのサイズを継続的に変更してコピーする必要があります (悪い)。リストまたはキュー表現を使用している場合は、各ノードをトラバースして、新しい行ごとに既に挿入されているかどうかを確認する必要があります (悪いですが、それほど悪いことではありません)。これは、より高い番号のノードに到達するたびに停止して挿入できるため、順序付きリストの場合はわずかに優れています。この実装では、ノードに連続した名前を付ける必要もありません (つまり、ノード名が 1、2、5、19、20202、20203 などのグラフ)。

于 2013-11-13T18:39:03.090 に答える
0

ノードが追加されるたびに動的に拡大するリンク リストを作成し、ファイルの最後まで継続します。への多くの呼び出しがmallocそれを行います。現在データをどのように読み取っているのか、およびデータ構造が何であるかを示さない限り、より詳細な回答を提供することは困難です。

于 2013-11-13T18:38:17.393 に答える