To get a handle on how to best find shortest paths in a graph,
it's going to help to compare a little bit between the kinds of depth first search algorithms
that we were looking at with the kinds of breadth first search algorithms
that we're going to need to look at.
So let's consider what the check_connection algorithm that we were just talking about does
if it's given this graph, G, and we ask it to check the connection between i and n.
The flow of control is when we do check_connection on i and n,
checking to see whether i and n are connected in the graph,
the way that it proceeds is it starts off at i
then visits the neighbors of i in some order.
Let's say it visits j first and then it asks, "Has j been visited so far? i has."
"Has j been visited so far?" No.
"Okay, well, let's go to j and do a mark_component from j."
It's going to consider the neighbors of j in some order.
Let's say it considers k first. "Has k been visited?" No.
"All right. Let's go mark_component on k." And so on.
So at some point, it may actually check one of the neighbors that it's already visited,
but at this point, once it's kind of heading in this direction,
it's going to continue to explore the graph this way,
and it will eventually hit n.
Essentially, the path that it followed to get to n is 1, 2, 3, 4, 5 links long,
which is not very representative of the shortest path, which in this case is just the 1 link.
So partly what's going on when you run this kind of algorithm
is it's diving deep into the graph.
It starts off at i and it just keeps digging itself deeper and deeper
and deeper and deeper and deeper.
And really what we'd like to do is kind of check in circles around i.
We start at i and check the things that are close to i before the things that are far from i.
And that's the essence of what breadth first search is going to do.
कैसे सबसे अच्छा एक ग्राफ में कम से कम पथ ढूँढने के लिए पर एक संभाल जाओ करने के लिए,
यह थोड़ा सा गहराई पहली खोज एल्गोरिदम के प्रकार के बीच तुलना करने के लिए मदद करने के लिए जा रहा है
हम चौड़ाई पहले खोज एल्गोरिदम के प्रकार के साथ देख रहे थे कि
पर देखने की जरूरत है कि हम जा रहे हैं।
तो हम क्या हम बस के बारे में बात कर रहे थे check_connection एल्गोरिथ्म करता है पर विचार करें
यदि यह इस ग्राफ, जी, दिया जाता है और हम इसे i और एन के बीच कनेक्शन की जाँच करने के लिए पूछना।
जब हम check_connection i और एन पर नियंत्रण का प्रवाह है,
देखना है कि क्या मैं और एन ग्राफ में से जुड़े रहे हैं की जाँच,
जिस तरह से कि यह आय है यह मैं पर बंद शुरू होता है
तब मैं के पड़ोसियों में कुछ आदेश का दौरा किया।
हम कहते हैं कि यह पहले जम्मू का दौरा और फिर यह पूछते हैं, "जे अभी तक दौरा किया गया है? मैं है."
"जे अभी तक दौरा किया गया है?" नहीं.
"ठीक है, ठीक है, चलो जाओ करने के लिए जम्मू और जम्मू से एक mark_component करते हैं."
यह कुछ क्रम में जम्मू के पड़ोसियों पर विचार करने के लिए जा रहा है।
हम कहते हैं कि यह कश्मीर समझता है पहले। "कश्मीर दौरा किया गया है?" नहीं.
"सब ठीक है। चलो mark_component कश्मीर पर चलते हैं." और इतने पर।
तो कुछ बिंदु पर, यह वास्तव में एक पड़ोसी कि यह पहले से ही का दौरा किया है की जाँच कर सकते हैं,
लेकिन इस बिंदु पर, एक बार इसे की तरह इस दिशा में बढ़ रहा है,
यह इस तरह ग्राफ का पता लगाने के लिए जारी रखने के लिए जा रहा है,
और यह अंततः एन मारा जाएगा।
अनिवार्य रूप से, रास्ता है कि यह n करने के लिए प्राप्त करने के लिए पीछा किया है 1, 2, 3, 4, 5 लिंक लंबे,
जो बहुत ही कम से कम पथ, जो इस मामले में सिर्फ 1 लिंक है का प्रतिनिधित्व नहीं है।
जब आप इस तरह एल्गोरिथ्म का तो आंशिक रूप से क्या हो रहा है
यह ग्राफ में गहरी गोताखोरी है है।
यह मैं पर बंद शुरू होता है और यह सिर्फ ही गहरी और गहरी खुदाई रहता है
और गहरे और गहरे और गहरे।
और वास्तव में क्या हम ऐसा करना चाहते तरह है मैं चारों ओर हलकों में जाँच की।
हम मैं पर शुरू और चीजें हैं जो मैं करीब चीज़ें है कि मैं से दूर रहे हैं पहले कर रहे हैं की जाँच करें।
और कि क्या चौड़ाई पहले खोज कर रहा है का सार है।
最適な最短経路の探索法を理解するには
前に使った深さ優先探索アルゴリズムと
これから使う幅優先探索を比較することが役立ちます
先ほどのcheck_connectionアルゴリズムに
グラフGを与えてiとnの連結を
求めたらどうなるでしょう
制御の流れはcheck_connectionにiとnを入力した時
iとnの連結をチェックします
その方法はまずiからスタートして
次にiと隣接するノードを訪れます
最初にjに行ったとして
前に訪ねられたかを聞きます iはありますね
jは"ない"と答えたので
mark_componentをjから始めることにしました
そしてjに隣接するkを調べて
前に訪ねられたかを聞くとkは"ない"と言ったので
kにmark_componentをします
これを繰り返していきます
もし前に訪れたノードがあっても
進行方向は変えずこのままグラフを進んで行って
最後にnに到達します
これでnに続くパスの長さは5リンクと分かりました
これは最短経路ではありません
この場合の最短経路は1リンクです
この種のアルゴリズムを動かすと
グラフを広く分析するのです
まずiからスタートして次から次へと
グラフを徹底的に分析していきます
iから一周するようにチェックしていき
iから近いノードから遠いノードへ進んでいくのです
これが幅優先探索の特徴です