c - 重み付きグラフの隣接行列におけるエッジの欠如の表現

Question

サポートデータ構造として隣接行列を使用して、Cでいくつかのグラフアルゴリズムを実装しようとしています。重みを実数で表した重み付きグラフを実装する必要があります。

0と負の数がエッジの正しい重みであるとすると、2つのノード間にエッジがないことをどのように表すことができますか？

score 2 · Accepted Answer

数字（）の代わりに次のdoubleような構造を使用できます。

struct weight
{
   double weight;
   bool edge_exists;
};

の隣接行列を作成しますweight。したがって、edge_existsがfalseの場合、をチェックする理由はありません。weightそうでない場合weightは意味があります。

every（？）doubleが可能な重み値である可能性がある場合は、上記を使用します。

score 0 · Accepted Answer

-1などの無意味な（すべての重みが正であると仮定していると思います）数値はどうですか？

これにより、コードが軽量になり（データ構造を追加する必要がなくなります）、覚えやすくなります。

score 0 · Accepted Answer

C99以降を使用している場合は、INFINITYで定義されたマクロを使用して、math.h存在しないすべてのエッジに重みを割り当てることができますINFINITY。

Cで無限大を使用する方法の詳細については、こちらをご覧ください：Cでnanとinfを使用する方法は？

（技術的にはNaNを使用することもできますが、定義が保証されているわけではなく、とにかく多くのアルゴリズムで無限大を使用した方がうまくいくと思います）

3 に答える 3