It's important to analyze the running time of this algorithm
so we have some idea of how efficient it is.
And again, that's going to involve counting up the number of primitive steps,
primitive statements, time that the algorithm takes when solving a problem.
We'll assume, as before, that n represents the number of nodes in the graph
and m represents the number of edges.
And it turns out that the basic strategy that we use for this algorithm
is a kind of graph search.
There's 2 principal flavors of graft search, depth first search and breadth first search.
This one that we've been talking about is a form of depth first search.
Later we're going to see a version of breadth first search
when we start looking at shortest paths.
But this particular algorithm is not concerned about the length of the paths,
it's just trying to figure out which nodes can be reached by any kind of path.
So taking a look at this algorithm here,
one of the things that we can note right off the bat
is statements like this one, marked(node) = True,
can only be executed once for each node in the graph.
So even though it's a little bit hard to tell exactly when this is going to execute,
we know at the end of the day every node is going to get marked
and no node is going to get marked twice.
So that means once for each node in the graph we're going to execute this statement
and this statement and this loop.
And what does this loop do?
It goes through and basically visits all the edges that come out of this particular node (node).
And for each of those edges, well, it does some work.
It checks whether or not it's marked, which we're going to assume is a unit time operation,
some kind of nice hash table and it behaves nicely,
and a recursive call, and we're going to somehow have to account for
all the stuff that happens in this recursive call, but let's not worry about that for the moment.
It's going to do this one main computation, this adding whatever value it gets back
to this quantity here, then it returns.
So these statements here are going to get executed once per node.
This statement is going to get executed once per node.
This statement is going to get executed once per edge in the graph
because for each node it's going to visit all the edges emanating from that node.
So even though it's very difficult to keep track of what's going to be executed when,
we know that the total running time here is going to be big theta
of the number of nodes plus the total number of edges in the graph.
So that's what's happening in this marked component.
And then what's happening outside here, this marked gets executed once at all,
then for every node in the graph it may or may not execute this statement,
which does the call to mark component.
So we're going to iterate over all the nodes,
and again, we're going to do some work but not more than constant work per node.
And if we look at our running time here, adding another n in here doesn't change the big theta.
Again, even though it's very complex to figure out which statements are executing when,
the actual running time is big theta of n + m.
It's worth pointing out that this is linear in the size of the graph.
The graph consists of some number of nodes and some number of edges,
and that's the whole story.
So this is actually linear in the size of the graph.
यह इस एल्गोरिथ्म के चल रहे समय का विश्लेषण करने के लिए महत्वपूर्ण है
हम कुछ पता नहीं कैसे कुशल से है यह है।
और फिर से, कि आदिम चरणों की संख्या के ऊपर की गिनती शामिल करने के लिए जा रहा है,
आदिम बयान, समय है कि एल्गोरिथ्म लेता है जब एक समस्या को हल करने।
हम मान लेंगे, जैसा कि पहले, कि एन ग्राफ में नोड्स की संख्या का प्रतिनिधित्व करता है
और एम किनारों की संख्या का प्रतिनिधित्व करता है।
और यह जाता है कि बाहर बुनियादी रणनीति है कि हम के लिए इस एल्गोरिथ्म का उपयोग करें
एक ग्राफ खोज की तरह है।
वहाँ 2 मुख्य जायके भ्रष्टाचार खोज, पहली खोज गहराई और चौड़ाई पहली खोज की है।
इस एक कि हम के बारे में बात कर रहा है गहराई पहले खोज का एक रूप है।
बाद में हम चौड़ाई पहले खोज का एक संस्करण को देखने के लिए जा रहे हैं
जब हम शुरू में कम से कम रास्तों की तलाश।
लेकिन इस विशेष एल्गोरिथ्म पथ की लंबाई के बारे में चिंतित नहीं है,
यह सिर्फ आंकड़ा जो नोड पथ का किसी भी तरह से पहुँचा जा सकता करने के लिए कोशिश कर रहा है।
तो यह एल्गोरिथ्म पर एक नज़र यहाँ ले जा,
चीज़ें है कि हम सही बल्ले से नोट कर सकते हैं में से एक
इस एक, marked(node) की प्रवक्ता है = True,
केवल एक बार ग्राफ में प्रत्येक नोड के लिए निष्पादित किया जा सकता।
तो भले ही यह थोड़ा सा ठीक जब इस पर अमल करने के लिए है बता जा करने के लिए मुश्किल है,
हम हर नोड के रूप में चिह्नित हो जाओ करने के लिए जा रहा है दिन के अंत में पता
और कोई नोड दो बार के रूप में चिह्नित हो जाओ करने के लिए जा रहा है।
तो इसका मतलब कि एक बार ग्राफ में प्रत्येक नोड के लिए हम इस कथन निष्पादित करने के लिए जा रहे हैं
और इस बयान और इस लूप।
और इस लूप क्या होता है?
यह माध्यम से चला जाता है और मूल रूप से सभी किनारों कि इस विशेष नोड (नोड) से बाहर आने का दौरा किया।
और प्रत्येक उन किनारों के लिए, अच्छी तरह से, यह कुछ काम करता है।
यह जाँच करता है या नहीं यह चिह्नित किया है, जो हमें लगता है के लिए जा रहे हैं एक इकाई समय ऑपरेशन, है
किसी तरह का अच्छा हैश तालिका और यह अच्छी तरह से व्यवहार करती है,
और एक आवर्ती कॉल, और हम किसी भी तरह के लिए खाते में है के लिए जा रहे हैं
सब सामान है कि इस रीकर्सिव कॉल में होता है, लेकिन चलो क्षण के लिए उस के बारे में चिंता नहीं।
यह यह एक मुख्य गणना कर रहा है, यह जो कुछ भी यह मूल्य जोड़ने वापस हो जाता है
इस मात्रा करने के लिए यहाँ, तो यह देता है।
तो ये बयान यहाँ एक बार प्रति नोड निष्पादित हो करने के लिए जा रहे हैं।
यह बयान एक बार प्रति नोड निष्पादित हो करने के लिए जा रहा है।
यह बयान एक बार ग्राफ में बढ़त प्रति निष्पादित हो करने के लिए जा रहा है
क्योंकि प्रत्येक नोड के लिए यह उस नोड से उत्पन्न सभी किनारों पर जाएँ करने के लिए जा रहा है।
तो भी यह बहुत क्या का ट्रैक रखने के लिए मुश्किल है, हालांकि जब मार डाला जा रहा है,
हम जानते हैं कि कुल समय चल रहा है यहाँ बड़ी थीटा होने जा रहा है
नोड्स प्लस ग्राफ में किनारों की कुल संख्या की संख्या का।
तो है कि क्या इस रूप में चिह्नित घटक में क्या हो रहा है।
और फिर हो क्या रहा है यहाँ के बाहर, यह के रूप में चिह्नित एक बार सब पर निष्पादित हो जाता है,
ग्राफ में प्रत्येक नोड के लिए तो यह कर सकते हैं या इस कथन का निष्पादन नहीं हो सकता,
जो घटक को चिह्नित करने के लिए कॉल करता है।
तो हम पर सभी नोड्स पुनरावृति करने जा रहे हैं,
और फिर से, हम कुछ काम लेकिन नोड प्रति नहीं से अधिक लगातार काम करने के लिए जा रहे हैं।
और अगर हम हमारे चल रहे समय में यहाँ देखो, यहाँ में एक और एन जोड़ने बड़ा थीटा नहीं बदलता है।
फिर से, यहां तक कि हालांकि यह आंकड़ा जो बाहर जब क्रियान्वित कर रहे हैं के लिए बहुत जटिल है,
n + m का बड़ा थीटा वास्तविक समय चल रहा है।
यह उनका कहना है कि इस ग्राफ के आकार में रैखिक है लायक है।
ग्राफ नोड्स की कुछ संख्या और किनारों की कुछ संख्या होती है,
और कि पूरी कहानी है।
तो यह वास्तव में रेखीय ग्राफ के आकार में है।
実行時間の解析は重要です
それによって効率が分かるからです
ここでもまた問題解決にかかる
アルゴリズムの最短経路や実行時間をカウントします
前と同様にnはグラフ内のノード数と仮定し
mはエッジ数と仮定します
このアルゴリズムで使用する基本戦略は
一種のグラフ検索です
グラフ検索には深さ優先探索と幅優先探索の 2つの基本的な探索法があります
ここでは深さ優先探索の形式についてお話しします
幅優先探索については
最短経路と合わせてあとでお話しします
このアルゴリズムではパス長は関係なく
パスを使って到達するすべてのノードを探索します
このアルゴリズムを見てください
すぐに気づくのは
このmarked[node]=Trueのような文です
これはグラフの各ノードに一度だけ実行されます
いつ実行されるかは見極めづらいですが
すべてのノードが一度だけ マークされるということは分かっています
つまり各ノードにつき一度だけ 実行されるということです
ではこの2つの文とループを実行します
ループは簡単に言うと
この特定のノード[node]につながっている すべてのエッジを訪れて
マークされているかどうかをチェックします
これを表すif文がループの単位時間を 操作する文となります
これは一種のハッシュテーブルです
ここが再帰呼び出しで 内容を明らかにする必要がありますが
とりあえず今は置いておきましょう
ここで主要な計算が行われ ここに合計の値が加えられて
また返します
これらの文は各ノードに1度ずつ実行され
これも各ノードに1度実行され
これはグラフ内の各エッジに実行されます
なぜならエッジは訪れる各ノードから出ているからです
何がいつ実行されるかを把握するのは困難ですが
実行時間の合計は把握できます
ノード数+グラフ内のエッジ数のビッグ･シータです
それがここで行われていることです
次のコードではmarkedは一度だけ実行されます
mark_componentを呼び出す for node in Gは実行されるかは分かりません
これをすべてに繰り返しますが
各ノードに対する処理にすぎないので
別のnを加えても実行時間は大してかかりません
いつどのコンポーネントが実行されるかは 分かりづらいですが
実行時間はΘ(n+m)です
ちなみにこのグラフのサイズは線形です
グラフはノード数とエッジ数で 構成されているということです
そのためグラフのサイズは線形になります