Bridge Edges - Intro to Algorithms Udacity English Japanese

Bridge Edges - Intro to AlgorithmsYouTube↗ IA↗(long shot)
Education 4.2K views 20 likes 5 dislikes 23 Feb 2015

Udacity 651K subscribers United States YouTube↗

Click to Play Video

Here's one last topic, I'd like to cover in this unit.

これがレッスン3最後の項目です

And again, it's related to the analysis of graphs and paths,

今回もグラフやパスの分析に関連しており

and using variance of depth-first and breadth-first search to answer questions about the graph.

様々な深さ優先探索と幅優先探索を使って[br]問題を解いていきます

Here's a little graph that I drew and one thing that we might notice is that,

まず用意したこのグラフを見てみましょう

everybody is connected to everybody else, but there is this sort of weak edge.

グラフ上のすべてのノードがつながっていますが

This is the weakest link, hello.

ここにつながりの弱いリンクがあります

If this edge were to be removed from the graph, like so,

このエッジをグラフから取り除くと

the number of components in the graph has just gone up by one.

グラフ上のコンポーネントは2つになります

Now, that was the only edge in this graph that has that property.

このエッジだけがこの特性を持っており

There's other edges that if we take them out, things are still connected.

他のエッジを取ってもノードはつながっています

So, in some social networks, it's useful to know, are there any edges in this graph?

ソーシャルネットワークで

Are there any pairs of people in the graph that are connected

知っておくと有効なのは友達をやめたら

that if they were to say, stop being friends, there would be disconnection in the network as a whole.

ネットワークが分裂してしまうペアが[br]存在するかどうかです

Let's put this edge back in and label the edges, sorry, label the

このエッジを元に戻して

nodes of the graph so we can talk about them.

ノードにラベルをつけましょう

And we're going to carry an algorithm back to 1974 by Robert Tarjan.

アルゴリズムは1974年に[br]ロバート･タージャンが発表しました

Tarjan is responsible for some of the most amazing graph algorithms.

彼は多くのすばらしい[br]グラフアルゴリズムを設計しています

A lot of which are based on the ideas of building trees,

その多くはツリー構造のアイデアが基になっており

spanning trees using depth-first and breadth-first search.

深さや幅優先探索でツリーを測るというものです

Back in college, my friend ??? and I used to refer to him as Tarjan, Lord of the trees.

学生時代クリス･Mと私はタージャンを[br]木々の主と言っていました

So the basic idea of this algorithm is we pick any node in the graph.

このアルゴリズムは[br]ノードを選択することから始まります

Let's say B, and we start to build a tree starting from B, and here's how we do it.

ここではbを選んでbからツリーを作っていきます

Starting from B, we look at all the neighbors of B which in this case are A and C,

まずbの隣接ノードを確認しますこの場合はaとcです

and we haven't build any of them into the graph yet, so we can add them into the graph.

ここで2つを加えてツリーを描きます

And now, we do essentially a search just as we're doing before, consisted of A and C.

そして前と同じ要領でaとcを調べていきます

So from A, we look at the neighbors of A. The neighbors of A are B and C.

次にaの隣接ノードを確認しますノードはbとcです

Now, the BA edge is already in there, but the BC edge is not.

ba間のエッジはグラフにありますがbc間はありません

So, we're going to add a special kind of edge because this is an edge between two nodes that are already existing.

しかしエッジはすでに存在しているので[br]特殊なエッジを加えます

We'll call this a non-tree edge.

これを非ツリーエッジと呼びます

So, what we're going to do is we're going to take this entire graph and express it essentially as a tree,

ではこのグラフをツリーに置き換えていきましょう

but some of the edges aren't going to be part of the tree. We're going to have to add them in separate, all right.

しかしツリーに加えないエッジもあります

So, that takes care of all the neighbors of B and the neighbors of C.

では次にcの隣接ノードを加えていきます

We have B which the edges are already in there

bはすでにツリーに加えてありますね

and we also have an edge to E which we haven't seen yet.

eはツリーにないので

We add that edges and then we proceed from E.

エッジを加えてeに進みます

Now, E has three edges back to C which we already have and also to D and G.

eのエッジは3つあります[br]cはすでにあるので残りはdとgです

Those are new nodes, so we build them in with three edges

新たなノードなのでツリーに加えます

and we continue our search now, let's say from D and D has two neighbors, E and F.

次はdです dの隣接ノードはeとfです

E is already in there but we can add in F at the tree edge.

eはすでにありますがfはないのでツリーに加えます

We look back at G, G has neighbors F and E.

次はgです gの隣接ノードはfとeです

The E one is in there and the F one is not, so we add that non-tree edge in there,

eとのエッジはありますがfはないので[br]非ツリーエッジを加えます

Because F is already in the diagram but that edge was no not.

fはグラフにはありますがエッジがないからです

And then from F, there is connection to D and G and those were already in the graph.

次はfの隣接ノードdとgですが[br]すでにツリーにあります

So basically, what we've done now is we rewrote the original graph as a rooted tree.

これで基のグラフをツリーに置き換えられました

So starting with some node and then proceeding downward

ツリーはbから始まって下に続いています

and then any edges that don't really fit that pattern we put in is, we put that dotted lines.

そしてこの形式にはまらないエッジは点線で描きました

So, we rewritten the graph as a tree and the next thing we need to know is post order the nodes.

ツリーができたので次に学ぶのは[br]ノードを後行順にたどることです

Now, post ordering is something you can do to any tree structure,

後行順にたどるのはどのツリーでも可能です

and it basically involves assigning a number, a sequential number to each of the nodes in the--in the tree and post order means is,

後行順ではツリー内のノードに[br]一連の番号を振っていきます

what we do, is to assign a number to a node,

後行順ではノードに番号を振っていきますが

we first make sure that all the children on its left are numbered.

まず左側の子ノードに番号を振ります

All the children on its right are numbered, children and descendant.

次に右側の子と子孫に番号を振ります

Direct children also and their children's children and then the node itself gets a number after that.

すべての子孫に番号を振ったあとに親に番号をつけます

So, these number is going to come from first numbering A,

bはあとなのでまずaから番号を振り

well A has--and then-and then everything below C and then we can number B itself.

aの次にcとその子孫そしてbに番号を振ります

A's number comes from neighboring--numbering it's children, which it doesn't have any,

aの番号は子に続きますがaは子がいないので

so it can get whatever the next number is, which in this case is 1, all right.

この場合aの番号は1になります

So back to B, we have to label all the--all the children on it's left and all the children on it's right.

bの前に左右すべての子に[br]番号を振らなければいけませんが

We haven't done that yet, so let's do a numbering starting from C.

まだできていないのでcへ行きます

Well C, before it gets a number, has to have all it's children numbered

ここでもcより先に子に番号を振りますが

and we can see that they don't have numbers yet, so we have to proceed down the tree.

まだ子に番号がついていないので下へ行きます

E needs a number. Well, E can't get it's number until it's children have been numbered

eに番号をつけるには先にeの子に番号が必要です

but those haven't been numbered yet, so let's number those.

また下へ行きます

D--D should get a number but first it's children have to get a number.

次はdですがdにも子がいます

This is a, you know, children first sort of scheme. These children has one child and that's F.

この番号制度は子が先ですのでfに行きます

For F to get a number, it's children, oh it doesn't have any children yet.

fにはまだ子がいないので

All right, so F can get the next available number and in this case, it's 2.

fに次に空いている番号2が振れます

So now that, that's finish, D can get a number because all it's children are numbered.

子に番号がついたのでdにも番号が振れます

So, D gets the next available number and that's 3.

dには次に空いてる番号3をつけます

E, no E still can't be numbered because it's children haven't been all numbered yet.

次のeにはまだ子がいるので

We have to go to G first. G has no children, so it can get the next available number.

先に子のいないgに番号を振ります

Now, E can get a number. Post order in this case is, post meaning after.

これでeに番号が振れますこのように後行順では

After all the kids, the node itself can get numbered.

子のあとに親の番号を振ります

There's also pre-order and in-order, but we're just looking at post order for this algorithm.

他にも先行順や中間順があります

All right, now C, all it's children have been numbered, so now C can get it's number.

次に子に番号がついたcに番号を振ります

B, all its children have been numbered, so now B can get it's number.

すべての子に番号がついたのでbに番号を振ります

So we've now post ordered all the nodes in the graph.

これで完了です

So, just to make sure that you're understanding that process, here's a different tree.

確認のために別のツリーを用意しました

This time, the branching factors are a little different in some places. And I want you to post order this tree

これに後行順で番号を振ってみましょう

and then type in this box the number assigned to node P once you've done that.

終わったらpの番号を解答欄に書き込んでください

Similar videos:

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

RECICLAR UN VIEJO CUBO DE PINTURA. Recycle an old paint bucket
LOS TRUCOS DE JULIETA.
689.3K views 11K likes 381 dislikes 15 Aug 201464% match

Batir 2 ingredientes, cocinar a la sartén y listo! Tenemos postre!
Recipes that work
451.1K views 23.7K likes 481 dislikes 11 May 202064% match

STIHL FS 450 Cómo Manejar / Usar Correctamente Las Desbrozadoras Segadoras Huerto Urbano Luis Servia
Huerto Urbano Luis Servia
164.3K views 1.2K likes 123 dislikes 05 Jun 201764% match

Building a Home Hobby CNC Shop/Shed - Part 3 - September 2020 Update
Mark Lindsay CNC
1.3K views 130 likes 0 dislikes 20 Sep 202064% match

little Kingdom Frozen Sleigh Ride Toy
Tic Tac Toy
258.2K views 167 likes 55 dislikes 01 Apr 201664% match

CHRISTMAS CLEAN & DECORATE 2020 / EXTREME CLEANING MOTIVATION / CLEAN WITH ME / SPEED CLEAN / SAHM
Naimah Altidore
22.9K views 1.1K likes 20 dislikes 11 Dec 202063% match

🧢Como SOLDAR con ELECTRODO (1 VEZ )✅
That, Dad fix it
2.1K views 115 likes 12 dislikes 19 Apr 202063% match

Como Cambiar ó Adaptar Panel de Repuesto en TV LED de 32"
Jesus Lopez
128.4K views 2K likes 91 dislikes 02 Jul 201863% match

КАК БЫСТРО ВОССТАНОВИТЬ ПЛАСТИК??? Горелка или тепловой пистолет???
Bought-Sold
12.6K views 766 likes 27 dislikes 29 Oct 202063% match

Air Layer Series Part 1: Trident Maple 2017
Appalachian Bonsai
954.3K views 6.8K likes 464 dislikes 30 Jun 201863% match

NEW MASKED Warrior Super 17! Mira and OTHERS! Super Dragon Ball Heroes Episode 28+ Spoilers
YeLLa Playz
1.7K views 79 likes 4 dislikes 29 Aug 202063% match

Beginner's Guide to CoC - Maxing Town Hall 5 Faster - Upgrading Town hall to level 6
Learning with Rock
1.6K views 32 likes 11 dislikes 30 Apr 201863% match

7λεπτο Πρόγραμμα Γυμναστικής Για Λιποδιάλυση & Σύσφιξη (Multi Subtitles)
Leo Spartacus
1.3K views 102 likes 1 dislikes 05 Sep 202063% match

Christmas Origami Instructions: Snowflake (Dennis Walker)
happyfolding.com - enjoy origami online
3.9M views 7.3K likes 465 dislikes 13 Oct 200962% match

COLD WINTER CAMPING & 4WD IN THE SNOW - Off Grid & Overland with our Defender Camper
Back On Track
14.2K views 375 likes 8 dislikes 24 Jan 202162% match

The Reveal: Homemade Silicone PokeBall Molds
TKOR
6.1M views 68.4K likes 4.1K dislikes 13 Dec 201662% match

Road Trip Europe (Hamburg to Copenhagen) | From Germany To Denmark by Car | RoamerRealm
RoamerRealm
877 views 51 likes 3 dislikes 30 Sep 201962% match

나는 왜 아이폰에서 삼성 갤럭시A71를 선택했나!!, 언박싱-1부
CanadaJJang2020
1.4K views 19 likes 2 dislikes 18 Oct 202062% match

Come Fare il PANDORO a Casa 🎄
Le ricette di zia Franca
34.1K views 1.3K likes 37 dislikes 18 Nov 202062% match

Подрезают в наглую - Опасное вождение

9.2K views 401 likes 10 dislikes 19 Mar 202062% match

It's a Finding Dory Toy Haul
Tic Tac Toy
379.9K views 472 likes 88 dislikes 05 May 201662% match

Tiramisù alle fragole / Senza uova / Ricetta facile e veloce
Cucina Geek
173.6K views 0 likes 0 dislikes 18 Apr 202062% match

LIVING AT SEA ON A BOAT! | Couple Vlog Travel 2021
Living Hakuna
9.9K views 829 likes 8 dislikes 28 Mar 202162% match

Behind The Scenes - Avengers Endgame HISHE
How It Should Have Ended
2M views 82.2K likes -1 dislikes 27 Jun 201962% match

Sliding Miter Saw 10 Inch NRT Pro MS 1055 HD - Unboxing & Review
Meadow Interior
4.2K views 89 likes 1 dislikes 07 Aug 202062% match

How to make MUTTON BIRYANI MANDI | Mutton Mandi restaurant recipe | My kind of Productions
My Kind Of Productions
23.6K views 981 likes 22 dislikes 04 Aug 202062% match

Display Temperature on LCD1602 using LM35 Temperature Sensor with Arduino
Robojax
2.2K views 95 likes 3 dislikes 24 May 202062% match

✅✅✅ DREMEL MOTOSAW SIERRA MARQUETERIA, la mejor para MANUALIDADES, MAQUETAS Y AEROMODELISMO 2021 ✅✅✅
BatuHerramientas
1.7K views 68 likes 1 dislikes 16 Jul 202061% match

99 TL iPhone 6s Aldım Kaç para masraf Bit pazarı mı internet mi
Tamir Et
22.9K views 1.2K likes 35 dislikes 10 Dec 202061% match

Settings Privacy About Contact Donate