Connected Components Code - Intro to Algorithms Udacity Japanese English

Connected Components Code - Intro to AlgorithmsYouTube↗ IA↗(long shot)
Education 2.3K views 0 likes 0 dislikes 23 Feb 2015

Udacity 651K subscribers United States YouTube↗

Click to Play Video

この例題を解くのにPythonコードを使いましょう

So let's write some Python code to solve this particular example.

問題と解答をコードに置き換えたものです

So here's a translation of that problem and the solution into Python.

まず最初にこれはグラフの連結リストで

So first I have a list of the connections in that graph

ここにノードaからhがあります

we were just looking at--nodes A through H.

次にグラフGにすべてのペアの連結を作っていきます

And for each of these pairs, I go through and make a link in a Graph G.

そしてlist_component_sizesにコードを書き込みます

Then I write a piece of code to list the component sizes

これが出力となります

for that Graph G, and here's what the output looks like.

次にアルゴリズムに戻り

Then we'll go back and look at what the algorithm is.

2つのコンポーネントが見つかりました

It goes through and identifies that there's two components.

1つをaとします

One we'll just name little A

4個のノードを含みその中にノードaがあるからです

because it contains node little A; it has four nodes in it.

aとつながっていないコンポーネントは

Then there's a separate component that's not connected to the first one

4個のノードを含みその中にノードbがあります

that contains B, and that also has four nodes.

先ほどのグラフを見ればリストのとおりです

In fact, looking back at the graph here, that's exactly what we see.

紫のグループAにノードaが含まれ

There's the purple nodes, which include node A,

もう一方の青のグループには

and then there's these blue-green nodes

4個のノードがありノードbが含まれています

four of which are visible here that include B.

それではPythonに戻りましょう

So it finds the right stuff. How does it go about doing this?

こちらのコードにも先ほどと同じ[br]アルゴリズムが利用できます

Well, it essentially uses the same algorithm that I did when I was doing it by hand, but of course it does it in code.

メインルーチンはmark_componentです

The main routine that we call is called mark component.

私がノードを紫にしたのと似たものです

So that's kind of like what I was doing when I was turning nodes purple,

グラフがこのようになります

and it works like this: we give it the graph that we're working on,

マークしている現在のノードと

the current node that we're marking,

これまでに何がマークされたかを[br]たどるデータ構造です

and data structure that keeps track of which things have been marked so far.

このルーチンを呼び出します

Call this routine on this node,

これは新しいノードなのでマークします

That's a new node; we haven't seen it before, and so we mark it.

このノードを訪れたという意味で

So that means we've visited that node, and we say

ルーチンに呼び出しました

that in this particular call to the routine

これまでマークしたノードは1個です

so far we've marked exactly one node.

次にすべての隣接ノードを見ていきます

Then we look at all the neighbors of that node. For each of them, we say

これまでマークされていない隣接ノードがあれば

if that neighbor of the node that we're looking at hasn't been marked so far,

mark_componentに再帰呼び出しをかけます

then what we're going to do is recursively call mark a component on that neighbor.

そうするとマークされていなかったすべてのノードを

It's going to go and get everywhere that it can get to that it hasn't already gotten to,

マークして返します

mark them all, and return.

このプロセスの一部として[br]マークしたノード数を返すのです

What it returns is the number of nodes that it marked as part of this process.

その数をtotal_markedに加えます

However many nodes it marked, we're going to add that to the total number marked.

これで現在のノードと[br]すべての隣接ノードをマークしました

So we marked our current node, then we visited a neighbor and marked all the nodes connected to that neighbor,

次は最初に戻り隣接する[br]他のすべてのノードでループを繰り返します

then we come back and repeat this loop for all the different neighbors of the node where we started.

それが完了すれば

When that's exhausted, it means we've now reached out

接触できるすべてのノードに接触したことになります

and touched all the nodes that are touchable from node node.

すると合計数を返しマークされた数が加えられて

And so we return the total that were actually marked as part of this process

プロセスは完了です

and then it's done.

これがメインルーチンです

So that's the main routine that does all the hard work..

外にもルーチンがあります

There's also a routine on the outside

このルーチンのグラフにはまだ何もマークされておらず

that takes a graph and starts off saying nothing's been marked so far.

空のデータ構造があるだけです

We just have an empty data structure.

まずはグラフ内のすべてのノードをループします

Then what we're going to do is loop through all the nodes in the graph

どれが新たな初期コンポーネントか分からないためです

because we don't know which ones are going to be the beginnings of a new component or not.

ループして以前にマークされていないノードがあれば[br]それが新たなコンポーネントです

For each one that we visit, we say if that node hasn't been marked in some previous iteration, then we've got a new component.

今訪れているノードはその一部で

This node that we're just visiting is a part of that component.

nodeを含むコンポーネントだということが分かりました

So we say, "Hey, we've got a component containing node node."

次に再帰呼び出しを使って

Then what we do is we recursively go

すべての隣接ノードをマークし[br]その数を数えて返します

and mark all the things connected to that node, count up how many things got marked in that way, and then we return.

これでnodeを含むコンポーネントと[br]隣接ノード数が分かったので

So what we know is there was a component, it contained node node, and it has a certain count to it.

次のノードに移ります

When it's done that, it moves on to the next node.

多くはすでにマークされているので[br]次々に進んでいきます

A bunch of these have probably already been marked, so they just get skipped really quickly,

新しいデータなのでいずれ[br]マークされていないノードにたどり着くはずです

but eventually it maybe reaches a node that hasn't been marked because it wasn't connected to anything so far.

出力して次に進みます

Prints that one out and continues.

まさに手書きの方法と同じで

So this really is very explicitly what we were doing by hand,

1個ずつ確認していくのです

just one piece at a time.

Similar videos:

Top K Code - Intro to Algorithms
Udacity
722 views 2 likes 0 dislikes 19 Jul 2012100% match

Eulerian Path - Intro to Algorithms
Udacity
55.8K views 144 likes 30 dislikes 27 Jun 2012100% match

QUICK FOLD THE CLOTHING AND EFFICIENT
LOS TRUCOS DE JULIETA.
109.9K views 1.9K likes 95 dislikes 05 Apr 201665% match

🧐 How to SEE CELL PHONE screen on PC 📱 Free with SCREEN MIRROR 💻
Tu ApoyoWeb
1.1K views 9 likes 1 dislikes 28 Jul 202063% match

JABON EN CREMA PARA LAVADORA. Soap in cream TO WASHING MACHINE
LOS TRUCOS DE JULIETA.
478.1K views 3.6K likes 341 dislikes 21 Apr 201462% match

DIY COCINA o estufa de ASERRIN !! #estufasdebajocosto
Leo Besson
4.2K views 281 likes 2 dislikes 01 Aug 202062% match

IT'S OUR END OF SCHOOL DANCE! | We Are The Davises
We Are The Davises
2M views 11K likes 446 dislikes 03 May 201762% match

How to do Picture in Picture for YouTube - Chrome/Android/iOS
AdamUPN0w
705 views 5 likes 0 dislikes 01 Nov 201862% match

Funcionamiento de las Cámaras
MovilOne Mobile repair
1.9K views 197 likes 0 dislikes 25 Nov 202062% match

#111 Lantern on the Wall, or Cityscape Without Perspective (Watercolor Cityscape Tutorial)
Watercolor Online with Michael Solovyev
6.7K views 397 likes 7 dislikes 26 Oct 202061% match

🔗 CADENA DE PLATA, JOYERÍA 💎
Guillermo Petrochelli Orfebre
8.6K views 503 likes 3 dislikes 03 Jan 202161% match

The 6 Must Know Signs of Depression!
Kati Morton
2.2M views 33K likes 960 dislikes 23 Feb 201461% match

LuLaRoe Leggings Face Mask DIY
Simply Epic Boutique
238.6K views 5.7K likes 141 dislikes 04 Apr 202061% match

🤔 ¿Por qué NO FUNCIONA DESCARGAR KINEMASTER 4.15? 😔 | 🔥 ¿PROBLEMA de EXPORTACIÓN SOLUCIONADO? 😳
Davizungo
10.8K views 311 likes 33 dislikes 04 Nov 202061% match

【超小厨】直播唱嗨肚子饿，泡面+牛腩，做真正的牛肉方便面，夫妻俩深夜吃到爽！
ChefChao
211.6K views 5K likes 238 dislikes 01 Dec 202061% match

Derecha liftada. Propuesta metodológica para la enseñanza. Curso de Entrenador de Tenis.
Arranztenis
112.7K views 402 likes 28 dislikes 30 Sep 201261% match

🔥 Spoiler of ONE PIECE 991 [FULL]
Anime Site
9.5K views 278 likes 36 dislikes 22 Sep 202061% match

#Yellowstone Ola de calor mundial Arboles mueren en yellowstone cierran plantar nucleares
America Hoy
270.6K views 7.2K likes 312 dislikes 04 Aug 201861% match

Chocolate cake with only 2 INGREDIENTS - RECIPE WITHOUT EGGS OR OIL OR FLOUR
RECETAS FÁCILES
2.1K views 264 likes 1 dislikes 25 Aug 202060% match

72.3K views 0 likes 0 dislikes 04 Jun 202660% match

苗大姐做野版毛血旺，又麻又辣一大锅，看着她吃口水都掉了一地【苗阿朵美食】
Miao Aduo cuisine
83.5K views 1.7K likes 71 dislikes 27 Nov 202060% match

湖北大哥靠10盆滷肉賣早酒，凌晨5點開喝！ 2元酒管夠，怎麼賺錢？【饞貓探店】
馋猫探店
6.4K views 72 likes 4 dislikes 06 Oct 202060% match

Ex101x - 5.3 - Filter
DelftX Data Analysis to the MAX
9.5K views 2 likes 0 dislikes 04 May 201560% match

POLAR BEAR PLUNGE CHALLENGE | We Are The Davises
We Are The Davises
4.4M views 17.3K likes 1.1K dislikes 11 Mar 201760% match

✅ Como Hacer ACEITE ANTICELULÍTICO de Limón 🍋 | * Prueba y Alucinarás*
SaludablementeSana
402.3K views 3K likes 77 dislikes 29 Sep 201260% match

胖哥车坏了心情很郁闷，小杜晚餐炒河粉，胖哥彤彤都吃嗨了~【小杜生活日】
Fat brother has Du
21.9K views 575 likes 12 dislikes 29 Oct 202060% match

Tutorial Disassemble Dell Latitude E6410 Disassembly Laptop

2.5K views 25 likes 0 dislikes 02 Dec 201960% match

[Subtitle] Stayed a thunderstorm night at 'Hottarakashi' hot spring in Yamanashi
Tatsuo and Umiko
187.3K views 753 likes 112 dislikes 22 Jun 201960% match

How To Remove Watermark In Kinemaster For Free
Devin Street
874.7K views 13.7K likes 1.7K dislikes 08 Aug 201860% match

Both Pigeon Loft Updates
Maney Pigeons
12K views 535 likes 17 dislikes 31 Dec 202060% match

Settings Privacy About Contact Donate