phpの画像は何ですか？どのように保管できますか?
- 醉折花枝作酒筹転載
- 2021-07-28 17:06:451482ブラウズ
学習が深まるにつれて、私たちの知識は常に拡大し、豊かになっていきます。ツリー構造にみんな混乱しましたか?信じてください、この図を学習すると、二分木が言葉では言い表せないほど単純であると感じるでしょう。実際、私たちが話しているツリーも特殊な形式のグラフです。
絵の概念
木の学習に関する最初の記事で見た木の絵をまだ覚えていますか?
そのとき、私たちは絵cは木ではなく絵だと言いました。なぜ？ツリーの定義から、ツリーはルート ノードを 1 つだけ持つことができ、レベル間に接続はなく、複数の子ノードを持つことができることがわかります。グラフはこれらのルールに従う必要はなく、ノード同士を接続できるのがグラフの特徴です。たとえば、以下の写真はすべて写真です。
上の図では、図bには矢印があり、図aの接続線には矢印がありませんが、このように方向が明確になっているグラフをいいます。有向グラフ。矢印のないグラフ、つまり方向のないグラフを無向グラフと呼びます。
まず、図 a-1 に注目してみましょう。実際には、図 a が回転しているだけです。みんなも見えるかな？ノード 4 と 1 の間の接続を無視すると、それはツリーになります。それは上記の樹状図の図 c の概念と一致していますか?
グラフのより正式な公式定義は次のとおりです:
グラフ (グラフ) G は 2 つのセット V と E で構成され、G=(V, E) として記録されます。V は頂点です。 E の有限の空でない集合は、V の頂点の有限集合です。これらの頂点のペアもエッジと呼ばれます。
有向グラフでは、開始ノードから指示ノードまでの 2 点を結ぶ線分を
上の図を見るとよくわかるのに、この定義を見ると混乱しませんか?あなたがテストを受ける必要がある学生であれば、この定義を覚えておく必要があります。私のように学習、応用、理解だけに集中したい場合は、丸暗記する必要はありません。 V はノード、E はこれらのノード間の関係、2 つの頂点間の関係、つまりグラフ上のノードを接続する線分がエッジです。
OK、これら 3 つの最も基本的な概念が理解できたので、引き続き画像に関連する他の用語を学習しましょう。
グラフに関する用語
まず、nはグラフの頂点の数を表し、eは辺の数を表すので、この2つのコードを覚えておいてください。
(1) サブグラフ: V と E' に V' が含まれる場合、G=(V, E) と G'=(V', E') の 2 つのグラフがあるとします。 E に含まれる場合、G' は G の部分グラフと呼ばれます
上の図の右側の部分グラフはすべて元の図の部分グラフです。サブグラフは多くの形状を生成でき、有向グラフも同じ概念を持っていることがわかります。ただし、無向グラフと比較すると、有向グラフはエッジに方向性があるため、生成できるサブグラフの数が少なくなります。
(2) 無向完全グラフと有向完全グラフ: 無向グラフの場合、n(n-1)/2 のエッジがある場合、それは無向完全グラフです。有向グラフの場合、n(n-1) 個の孤立子がある場合、それは有向完全グラフと呼ばれます。 (完全なバイナリ ツリーを参照してください)
実際、完全なグラフの概念は、グラフ内のすべての隣接するノードにエッジがあるということです。それらをつなぎ合わせます。
有向グラフの場合、エッジには方向性がありますが、もちろん、有向グラフで や などの前後方向を定義することもできます。 1 から 2、または 2 から 1 に進むことができることを示すために、反対方向に 2 つの矢印を描く必要があります。無向グラフでは、これら 2 つのエッジの概念を 1 つのエッジで置き換えます。矢印の方向のないエッジは双方向です。
(3) スパース グラフとデンス グラフ: エッジや孤立したグラフ (e
(4) Quanhe Net: 実際のアプリケーションでは、地図上の距離と同じように、各エッジまたは島に何らかの意味を持つ値をマークできます。これらの値はと呼ばれます。重み。権威のある写真をネットワークと呼ぶことができます
上の写真の図 a-2 と図 b-1 の横にある数字は重量を表します。この 2 つの画像はネットワーク画像と呼ばれます。重みの概念については、後で関連するアルゴリズムについて説明するときに学習します。これら 2 つの図から、ノード 1 からノード 4 に移動したい場合、直接 に移動しないことが実際にはっきりとわかります。側にありますが、 、 ルートを選択した方が早いです。
(5) 隣接点: エッジを持つ 2 つのノードは隣接点です。
(6) 次数、入次数および出次数:頂点 v の次数は、v に関連付けられたエッジの数を指します。有向グラフの場合、他のノードを指す矢印は出力次数であり、それ自体を指す矢印は次数です
引き続き図 b を見てみましょう。ノード 1 には 2 つの出力次数と 1 つの入力次数があります。これについてはあまり説明の必要はないようです。
(7) パスとパスの長さ: ある頂点から別の頂点に通過するすべての頂点はパスです。有向グラフの場合、そのパスは矢印の方向になります。パスの長さは、パス上を通過するエッジまたは孤立の数です。
(8) ループまたはループ: 最初の頂点と最後の頂点が同じパスは、ループまたはループと呼ばれます。ループ
(9) 接続性、接続されたグラフおよび接続されたコンポーネント: 2 つのノード間にパスがある場合、それらは接続されていると言われます。グラフ全体のすべてのノードが相互に接続できる場合、そのグラフは接続されたグラフです。連結成分は、無向グラフ内の最大連結部分グラフです。
- (10) 最大接続サブグラフ: 接続サブグラフに含めることができるノードの最大数。ノードを 1 つ追加すると、サブグラフは接続グラフではなくなります。
- # は、実際にはグラフ内のすべてのノードを接続するパスです。連結成分のグラフでは、2 つの連結成分に基づいて 2 つの最小スパニング ツリーを生成します。接続コンポーネント 1 のスパニング ツリーのノードは必ずしもこの構造である必要はなく、この最小スパニング ツリーを生成するためのトラバース方法に応じて、ノード 4 をノード 2 の下に置くことができます。
上の図 a の最小スパニング ツリーは、実際には赤い点線のない図 a-1 になります。もちろん、ノード 4 をノード 1 の下に配置することもできます。また、プログラムがグラフをどのように走査してどのような種類のツリーを生成するかによっても異なります。
(12) スパニング フォレスト: 非接続グラフでは、接続された各コンポーネントが接続されたスパニング ツリーを生成し、非接続グラフ全体のスパニング フォレストを形成できます。- これを読んだ後、めまいがしませんか?問題ではありません。これらの用語は今後の研究で頻繁に使用されますが、これは最も包括的なものではありません。参考文献やその他の学習教材を使用して、グラフ関連の用語をより深く学習し、理解することができます。
まとめ
グラフの概念はほぼ紹介されているので、それを理解して次の内容を学習し続けることができます。これはほんの始まりにすぎませんが、多くの学生は、ツリー構造に比べて大幅に改善されたと感じるでしょう。グラフに関する内容がまだ理解できていなくても、以下の知識を学べばツリー構造への理解が確実に深まるのでご安心ください。なぜ？ツリーは実際にはループのないグラフであり、深さまたは幅によってたどることができますが、グラフはより複雑です。さて、未来にはまだ希望があると思いますか？学習は段階的なプロセスであることが多く、現在の知識と過去の知識の間には常につながりがあります。最初はあまり考えすぎず、ステップバイステップで進めてください。
おすすめ:《2021年PHP面接質問まとめ（集）》《phpビデオチュートリアル》
以上がphpの画像は何ですか？どのように保管できますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。