コンピュータサイエンスにおけるグラフとは何ですか、またそれらは何を使用していますかために？素人の言葉で言えばできれば。
ウィキペディアの定義を読みました：
コンピュータサイエンスでは、グラフは数学からのグラフとハイパーグラフの概念を実装することを目的とした抽象データ型です。
グラフのデータ構造は有限（場合によっては可変）で構成されます。 ）ノードまたは頂点と呼ばれる特定のエンティティのエッジまたはアークと呼ばれる順序対のセット。数学と同様に、エッジ（x、y）はxからyを指す、または移動すると言われます。ノードはグラフ構造の一部である場合があります。 、または整数のインデックスまたは参照で表される外部エンティティである可能性があります。
しかし、私はより形式的で理解しやすい定義を探しています。
コメント
- データ構造をグラフ化するという意味ですか？
- はい、申し訳ありません。ここで説明されているグラフ en.wikipedia.org/wiki/Graph_(abstract_data_type）、私だけが'を探していますあまり形式的ではなく、理解しやすい定義です。
- @ Justin984ウィキペディアの括弧付きのリンク（およびそれらの多くがあります）は機能しません'動作しません、括弧は機能しません'リンクのマークダウン形式でうまく機能しません。さて、今後の参考のために、コメントではなく質問自体に説明を追加してください。'表示されておらず、'それらを見逃しがちです。 '質問の上記のコメントを編集します…
- @ Justin984 コンピュータサイエンスにも注意してくださいStack Exchange は、プログラマーよりもこのような質問に少し適しているかもしれません。 '誤解しないでください。質問はここで完全に話題になっており、すばらしい回答が得られましたが、'が問題にならない場合'私たちよりもコアコンピュータサイエンスの概念に少し焦点を当てているコミュニティをチェックアウトしました（'同じ質問を投稿しないでくださいただし、複数のサイトが間違ったサイトに投稿された場合は、自動的に正しいサイトに移動できます。
回答
完璧な素人」の例は Facebook です。あなた、あなたの友人、そして彼らの友達などは、まとめて ソーシャルグラフ 。
この「グラフ」では、人はノードと
エッジは友情リンク。
Facebookでは友達は双方向の関係（AはBの友達=> BはAの友達）なので、グラフは無向グラフ。 Google+やTwitterのようなネットワークは、関係の方向がここで意味を持つため、有向グラフと見なされます。
これらのグラフはすべて、ノード間の関係がサイクルを形成する可能性があるため、循環グラフと呼ばれます。 。一方、家系図は、特に非循環家系図の関係にサイクルはあり得ないため、 （技術的には、有向非巡回グラフ（DAG）と呼ばれます。これは、有向非巡回グラフの両方であるためです）
これは、グラフに関連するすべての基本的な専門用語をカバーするはずなので、これで、フィールド内の残りの資料を追跡できるようになります。
コメント
- '信じられない'
- 家系図は循環的ではありませんか？ 'であってはなりませんが、残念ながら…
- @MarjanVenema、家系図は循環？（'有向グラフであるため、サイクルを決定する上で方向が重要であり、おそらくステップ関係は本当に重要です。）
- @dbaupp：ここで詳細を説明したくないので、' 1つだけ言及します。単語：近親相姦。
- @MarjanVenema、あなたは'私の主張を見逃しています。有向グラフのサイクルは、
A -> B -> C -> A（つまり、矢印の円）のようなパターンであり、近親相姦はA -> B -> CとA -> D -> C（つまりダイヤモンド）。家系図のサイクルにはタイムトラベルが必要です。
回答
グラフは最も重要な数学的概念の1つです。コンピュータサイエンスで使用されます。
グラフを何度も見てきました。ある都市から別の都市へ飛行機で移動していると想像してみてください。必然的に、座席に航空会社の素敵な光沢のある雑誌が見つかります。あなたの前にポケット。その雑誌の裏側の近くには、ほとんどの場合、その航空会社が運航する都市を円で表した地図があり、それらの都市を結ぶフライトは曲線で表されています。つまり、「グラフです。円で表された都市はこのグラフのノードであり、曲線で表されたフライトはエッジです。グラフは、ノードとノードを接続するエッジを持つものです。
これらの単純なグラフは、さまざまな方法で装飾できます。そのマップを見ているときに、円や線の束だけを見たくはありません。これらの都市には名前があります。これらの都市にラベルを付けると、ラベル付きのグラフになります（また、エッジにラベルを付けます（例：フライト1234）。コンピュータサイエンスは、データをノードに関連付けることが多く、場合によってはエッジに関連付けることもありますが、これはラベルの単なる拡張です。それはまだラベル付きのグラフです。都市Aから都市Bに直接飛ぶことができるが、都市Bから都市Aに飛ぶことができない場合、別の装飾が得られます。これを表現する明白な方法は、都市を結ぶ線に矢印を付けることです。この一方向の関係を表すために。これで有向グラフができました。
リンクされたリスト、ツリー、状態遷移図、およびその他の多くのコンピュータサイエンスデータ構造はすべてグラフの例です。これは非常に強力です。コンセプト。
コメント
- I ' dは実際にその例を拡張して、すべて例で説明されているエンティティは、グラフ内の頂点（都市、平面、雑誌、地図など）として表すことができ、地図自体は単一の頂点にすぎません。
回答
より良い質問は、「グラフは何に使用されないのか」です。コンピュータサイエンスは、多くの点でグラフの研究です。
グラフは、素人の言葉で言えば、接続点を表す「ノード」または「頂点」と呼ばれる任意の抽象的なオブジェクトのコレクションです。次に、それらは「パス」または「エッジ」を介して接続されます。抽象データタイプ「グラフ」は、数学的な「グラフ」の実装です。したがって、基本的に、フィールドとしてノードとエッジがあり、それらに対して実行できるさまざまな操作があります。たとえば、グラフのコレクションに新しいノードを追加できます（これは、言語に応じて、リスト、配列、またはその他の構造になります）。次に、そのノードを既存のノードにリンクできます。操作には、グラフのトラバース、2つのノードがエッジを共有しているかどうかの確認（接続されている）、ノードまたはエッジからの値の取得、グラフからのノードまたはエッジの削除も含まれます。
使用率に関する限りグラフはいたるところに使用されています。ネットワーキングはそれらを特に多用しますが、それらは人工知能、データマイニング、ゲーム開発、地球情報学、および他の多くの分野で見られます。正式なコンピュータサイエンスでは、状態を表す方法として、さらに多くの用途が見られます。
事実上、接続のセットとして表すことができるものはすべてグラフとして表すことができ、一部のADTを介して実装できます。フォーム。
これが私が作成したグラフィックの例です：
回答
グラフは、頂点と呼ばれる線で接続されたオブジェクトのコレクションです。
「グラフ」という用語は、多くのオブジェクトを抽象化および一般化したものです。ソフトウェア開発で使用されるデータ構造。リンクリスト、バイナリツリー、 AST はすべてグラフです。
基本的に、次のようなオブジェクトのコレクションオブジェクトを相互に関連付けるポインタがあります。これはグラフです。グラフを作成したら、グラフ理論の原則をグラフに適用して、特定の問題を解決できます。