3

2 つの要素間の推移的な関係を特定しようとしています。c でコーディングしています。

例: a->b は、1 行 2 列の隣接行列の "1" で表されます。

したがって、a->b および b-> c および c->d の場合

a->d かどうかを特定したい。隣接行列を更新する必要はありません。

私が採用したアプローチ：aに対応する行のすべての1をチェックしてください。2列目、つまりbに1があるとしましょう。[(a->b)] 、b->d かどうかをチェックし、そうでない場合は B の行のすべての 1 をチェックし、26 行目まで続けます。

複雑さにはあまり関心がありません。私はこれを実装することを望んでいます。

4

1 に答える 1

3

幅優先探索または深さ優先探索を実装する必要があります。で開始しa、に到達dしたとき、またはすべてのオプションを使い果たしたときに停止します。

あなたの場合、「プレーン」Cには幅優先探索に必要な組み込みの動的キューがないため、深さ優先探索の実装はやや簡単です。

効率を気にせず、行列の更新を気にしない場合は、Floyd-Warshallアルゴリズムを実装します。これは隣接行列用に特別に定式化されており、実装に5行しかかかりません。

for (int k = 0 ; k != N ; k++)
    for (int i = 0 ; i != N ; i++)
        for (int j = 0 ; j != N ; j++)
            if (matrix[i][k] && matrix[k][j])
                matrix[i][j] = 1;

このアルゴリズムを実行した後、結果matrixには元のアルゴリズムの推移閉包が含まれます。

于 2012-12-05T04:57:43.063 に答える