問題タブ [graph-theory]

G をグラフとします。したがって、G はノードの集合とリンクの集合です。グラフをすばやく分割する方法を見つける必要があります。私が現在取り組んでいるグラフには 120*160 ノードしかありませんが、別のコンテキスト (医学ではなく Web サイト開発) で数百万のノードを持つ同等の問題にすぐに取り組んでいる可能性があります。

だから、私がしたことは、すべてのリンクをグラフマトリックスに格納することでした:

ここで、ノード s がノード t に接続されている場合、M は位置 s,t に 1 を保持します。M が対称 M[s,t]=M[t,s] であり、各ノードが M[s,s]=1 にリンクしていることを確認します。

よく覚えているのですが、M に M を掛けると、結果は 2 つのステップで到達した頂点を結ぶグラフを表す行列になります。

したがって、行列内のゼロの数が減少しなくなるまで、M をそれ自体で乗算し続けます。これで、接続されたコンポーネントのリストができました。次に、このマトリックスをクラスター化する必要があります。

今のところ、アルゴリズムにはかなり満足しています。簡単で、エレガントで、かなり速いと思います。この部分で悩んでいます。

基本的に、このグラフを接続されたコンポーネントに分割する必要があります。

すべてのノードを調べて、それらが何に接続されているかを確認できます。

しかし、行を並べ替えて行列をソートするのはどうでしょうか。しかし、それが可能かどうかはわかりません。

以下は、これまでのコードです。

編集：

SVD 分解を使用することが提案されています。これは、5x5 グラフの問題の簡単な例です。これを使用するのは、19200x19200 の正方行列ではクラスターが見にくいためです。

基本的にここには 4 つのクラスターがあります: (0),(1,3),(2),(4) しかし、このコンテキストで svn がどのように役立つかはまだわかりません。

学校のプロジェクトのフェーズ1（3つのうち）は24時間であるため、結論に達し、コードを適応させるためにこれについて適切に話し合う時間があるわけではありませんが、少なくとも正しい決定をしたかどうかを知る必要があります。

リンクリストを使用しています。構造は次のとおりです。

基本的に、私にはたくさんの都市があり、それらの都市はグラフのようにすべて一緒にリンクされています。たとえば、A、B、C、D、およびEは、この順序で構造Cityに挿入されます。次に、AをB、CとD、BをC、D、E、CをD、EとDをEに接続します。

ここで、E市に行く必要があるとしましょう。これはリンクリストの最後の都市であり、リンクリストを最後まで通過するには時間がかかります。たぶん、この例では5つの都市ではありませんが、実際のアプリでは、少なくとも10,000の都市のようにサポートすることになっています。ただし、最短ルートはA（開始点）からCからE（またはADEまたはABEの場合もあります）です。

私の構造では、リンクリスト全体を1つずつトラバースすることなく、AからEへの最短ルートを見つけることができますか？そうでない場合、私は何を間違っていますか？

はいの場合、どうすればそれを行うことができますか？どうすればそのような道を見つけることができるのか分かりません...

グラフをトラバースする関数は、ツリーをトラバースするのと同じように機能しますか?

私は学生のセットを持っています (一般性のためにタイトルでアイテムと呼ばれます)。これらの学生の中には、やんちゃであるという評判がある学生もいます。「私はjが嫌い」という形の一連の憎悪関係について話されます。「私は j が嫌い」は、 「j は私が嫌い」という意味ではありません。「iがjを嫌う」場合、iがjの番号よりも厳密に小さい番号の列に配置されるように、生徒を列に並べます（最前列の番号は1） 。 j の行の前にある行) を使用して、j に何もスローしないようにします (後戻りは許可されません)。必要な行の最小数を見つけるための効率的なアルゴリズムは何でしょうか (各行の生徒数が同じである必要はありません)。

次の仮定を行います。

1) これを有向グラフとしてモデル化すると、グラフにサイクルはありません。最も基本的なサイクルは次のようになります。「i は j が嫌い」が true の場合、「j は i が嫌い」は false です。そうしないと発注できなくなると思うからです。

2) グループ内のすべての生徒が、少なくとも 1 人の他の生徒に嫌われている、または少なくとも 1 人の他の生徒を嫌っている。もちろん、一部の人に嫌われている生徒と、他の生徒を嫌っている生徒がいるでしょう。これは、グラフの一部を形成しない迷子の生徒がいないことを意味します。

更新: 'i が j を嫌う場合、i --> j を使用して有向グラフを作成し、トポロジカル ソートを行うことを既に考えています。ただし、すべての生徒を一列に並べる必要がある場合は、一般的なトポロジカルソートの方が適しているためです。ここには行のバリエーションがあるため、トポロジーソートへの変更を考慮して、必要なものを得る方法を見つけようとしています。

回答するときは、ソリューションの複雑さを述べてください。誰かがコードを提供していて、言語を気にしないのであれば、私は Java を好みますが、もちろん他の言語でも問題ありません。

JFYI これは宿題用ではありません (私は学生ではありません :))。

XAMLを介した長い学習ループの後、HTMLとjavascriptに戻り、宣言型コードの概念（変換のルールの観点から）が非常に強力な概念であることに気付きました。

構文が豊富であるにもかかわらず、XMLのXSLT処理は宣言型変換プログラミングの要です。ただし、XSLTが日常のタスク（XMLを使用）にどのように使用されるかを理解するのは常に困難です。

HTMLを生成する以外に、プログラミングの問題をエレガントに解決するXSLTの良い例は何ですか？

グラフ変換やデータ再処理が得意だと思います...

編集：私はいくつかの実際の例を望んでいます-完全なxsltを思いとどまらせるものの1つは、コードの視覚的な複雑さです。

グラフの推移閉包は、たとえばここで定義されます: http://mathworld.wolfram.com/TransitiveClosure.html

O（n ^ 3）で簡単に可能です。ここで、nは頂点の数です。時間O(n^2)でできるかどうか疑問に思っていました。

Stevey Yegge のGet That Job At Googleの記事を読んだ後、次の短い引用が興味深いものであることがわかりました。

誰かがあなたに問題を与えるときはいつでも、グラフを考えてください。それらは、あらゆる種類の関係を表現する最も基本的で柔軟な方法です。そのため、興味深いデザインの問題にグラフが関係しているのは、50 ～ 50 ショット程度です。他のソリューション タイプに移る前に、グラフを使用してそれを解決する方法を思いつかないことを絶対に確認してください。このヒントは重要です！

グラフのデータ構造/アルゴリズムによって最もよく表現および/または解決される問題の例は何ですか?

私が考えることができる 1 つの例: 現在の場所から別の場所への道順を提供するナビゲーション ユニット (ala Garmin、TomTom) は、グラフと高度なパス アルゴリズムを利用します。

他のいくつかは何ですか？