問題タブ [graph-theory]

異なるノードを持つJavaでグラフを作成しようとしています。一部のノードは他のノードに接続され、一部は接続されません。それらが接続されている場合、そのノードのブール値が true になり、別の変数が接続先のノードの値を保持します。

...これにアプローチするための最良の方法は何だと思いますか?

グラフ内で相互接続されたN個のノードが与えられ、次に別のノードに接続されているノードをリストする行列が与えられた場合に問題が発生します（接続されている場合は1、そうでない場合は0）。この問題に最善の方法で取り組む方法を考えています。これらは隣接行列だと思いますか？しかし、どうすればそれを実装できますか...

基本的に私がこれらから抜け出そうとしているのは、特定のノードが特定のセット「S」内の他のすべてのノードに接続されているかどうかを見つけることです。そして、選択されたアイテムがクリークであるかどうか...

ヒントをいただければ幸いです。

これがNP-Completeの問題に取り組んでいる可能性があることを懸念しています。あるのかないのか、どなたか回答いただけると幸いです。そして、イエスかノーかだけでなく、もっと多くの答えを探しています。理由を知りたいです。「これは基本的にこの問題 'x' であり、NP-Complete である/そうではない (wikipedia リンク)」と言えます。

(いいえ、これは宿題ではありません)

任意の無向グラフで 2 つの点が接続されているかどうかを判断する方法はありますか。たとえば、次の

ポイント A から M (「I」なし) は、開いたり閉じたりできるコントロール ポイント (天然ガス パイプのバルブのようなもの) です。「+」はノード (パイプ T のようなもの) であり、ウェルとハウスもノードであると思います。

任意のコントロール ポイント (例: C) を閉じた場合、井戸と家がまだ接続されているかどうかを知りたいです (他のコントロール ポイントも閉じている可能性があります)。たとえば、B、K、D が閉じている場合でも、AEJFCGLM を通るパスがあり、C を閉じると井戸と家が切断されます。もちろん; D だけが閉じられた場合、C だけを閉じてもハウスは切断されません。

これを別の言い方をすれば、C は橋/切り口/地峡ですか?

各コントロール ポイントをグラフの重みとして扱うことができます (オープンの場合は 0、クローズの場合は 1)。次に、Well と House の間の最短経路を見つけます (結果 >= 1 は、それらが切断されたことを示します。最短経路を見つけるためのアルゴリズムを短絡する方法もいくつかあります (たとえば、1 に達したら経路を破棄し、停止します)。井戸と家などをつなぐパスがあれば検索します。) そしてもちろん、あきらめる前にチェックするホップ数に人為的な制限を設定することもできます。

誰かがこの種の問題を以前に分類したに違いありません。名前がわかりません。

有向グラフのノードのデータ型を簡単に定義できます。

show 関数を使用してグラフをファイルに保存し、read を使用して復元できます。ただし、show はサイクルに対応しません。グラフを保存して復元する簡単な方法はありますか?

1 つ以上のノードがソースとして区別される有向グラフ (必ずしも接続されている必要はありません) があります。いずれかのソースからアクセス可能なノードは、「点灯」していると見なされます。ここで、エッジの 1 つが削除されたとします。問題は、以前に点灯していて、もう点灯していないノードを特定することです。

都市の電力システムのようなアナロジーが考えられるのではないでしょうか。

私は、さまざまなタイプのアルゴリズムを最適化するためのヒューリスティックなアプローチとして「アリのコロニー」モデルを使用することについて、あちこちで読んでいます。ただし、アリのコロニーの最適化について入門的な方法で、または詳細に説明している記事や本をまだ見つけていません。このアイデアについて詳しく学べるリソースを誰か教えてもらえますか?

私はグラフを持っていますが、どういうわけか、グラフの他のエッジを含まないグラフ内のすべての閉じた等高線を見つける必要があります。

私はグーグルを検索していましたが、チャートしか提供しません:)

ライブラリはありますか、またはそのようなアルゴリズムの名前を知っているかどうか。

どうも

プロパティを使用してユーザーが作成したノード コレクションを生成するには、Mac と他のプラットフォームの両方で動作することを期待するノードグラフ エディタが必要です。グラフ データは、私が取り組んでいるデータ駆動型アプリケーションで使用されるため、アプリケーションがグラフを処理しやすい形式で保存できる場合は称賛に値します。今までツリーエディタでXMLを使っていましたが、グラフは必要に応じて巡回できるので、ツリーエディタではカットしなくなりました。

他のアプリのプラグインもOK！

オブジェクト指向デザインに関するHeadFirstシリーズの本が大好きでした。それは主題への非常に穏やかで面白い紹介でした。私は現在データ構造クラスを受講していますが、使用しているテキスト（Kruse /Rybaデータ構造とC++のプログラム設計）は非常に乾燥していて理解しにくいと感じています。これは主に、数学の分野での私自身の限界によるものだと思います。

ユーモアのセンスのある、より明るいスタイルで書かれ、バイナリツリー、Bツリー、グラフなどのすべての基本をカバーするデータ構造テキストを知っている人はいますか？