1 / 63

# Progressed DFS, BFS, Graph Modeling .

33 views
Description
2. Presentation. Profundity first hunt (DFS)Breadth-first pursuit (BFS)Graph ModelingModel a diagram from an issue, ie. change an issue into a diagram issue. 3. What is a chart?. An arrangement of vertices and edges. 4. Trees and related terms. 5. What is a tree?. A tree is an undirected straightforward chart G that fulfills any of the accompanying identical conditions:G is joined and has no basic cycles. G has n
Transcripts
Slide 1

﻿Progressed DFS, BFS, Graph Modeling 25/2/2006

Slide 2

Introduction Depth-first inquiry (DFS) Breadth-first pursuit (BFS) Graph Modeling Model a chart from an issue, ie. change an issue into a chart issue

Slide 3

vertex edge What is a diagram? An arrangement of vertices and edges

Slide 4

predecessors root parent kin descendents youngsters Trees and related terms

Slide 5

What is a tree? A tree is an undirected straightforward chart G that fulfills any of the accompanying proportional conditions: G is associated and has no basic cycles. G has no basic cycles and, if any edge is added to G, then a straightforward cycle is framed. G is associated and, if any edge is expelled from G, then it is not associated any longer. Any two vertices in G can be associated by a one of a kind straightforward way. G is associated and has n − 1 edges. G has no straightforward cycles and has n − 1 edges.

Slide 6

Graph Traversal Given: a diagram Goal: visit all (or a few) vertices and edges of the chart utilizing some methodology (the request of visit is efficient ) DFS, BFS are cases of chart traversal calculations Some most limited way calculations and spreading over tree calculations have particular visit arrange

Slide 7

Idea of DFS and BFS This is a concise thought of DFS and BFS DFS: keep going by next vertex at whatever point there is a street, backpedal if no street (ie. visit to the profundity of current way) Example: a human need to visit a place, however don\'t have the foggiest idea about the way BFS: experience all the contiguous vertices before going further (ie. spread among next vertices) Example: set a house ablaze, the fire will spread through the house

Slide 8

DFS (pseudo code) DFS (vertex u ) { mark u as went by for every vertex v specifically reachable from u if v is unvisited DFS ( v ) } Initially all vertices are set apart as unvisited

Slide 9

F E unvisited went to A D B C DFS (Demonstration)

Slide 10

"Progressed" DFS Apart from simply going to the vertices, DFS can likewise furnish us with profitable data DFS can be improved by presenting: birth time and demise time of a vertex birth time: when the vertex is initially gone by death time: when we withdraw from the vertex DFS tree parent of a vertex

Slide 11

DFS crossing tree/timberland An established tree The root is the begin vertex If v is initially gone to from u , then u is the parent of v in the DFS tree Edges are those in forward bearing of DFS, ie. when going to vertices that are not gone by before If some vertices are not reachable from the begin vertex, those vertices will shape other traversing trees (at least 1) The gathering of the trees are called woodland

Slide 12

DFS (pseudo code) DFS (vertex u ) { mark u as went to time  time+1; birth[u]=time; for every vertex v straightforwardly reachable from u if v is unvisited parent[v]=u DFS ( v ) time  time+1; death[u]=time; }

Slide 13

A D B E G E F C A D H F unvisited B went to went to (dead) C G H DFS backwoods (Demonstration) 1 2 3 13 10 4 14 6 12 9 8 16 11 5 15 7 - A B - A C D C

Slide 14

A D B E G C F H Classification of edges Tree edge Forward edge Back edge Cross edge Question: which sort of edges is constantly missing in an undirected diagram?

Slide 15

Determination of edge sorts How to decide the kind of a subjective edge ( u , v ) after DFS? Tree edge parent [ v ] = u Forward edge not a tree edge; and birth [ v ] > birth [ u ]; and passing [ v ] < demise [ u ] How about back edge and cross edge?

Slide 16

Determination of edge sorts

Slide 17

Applications of DFS Forests Topological sorting (Tsort) Strongly-associated parts (SCC) Some more "propelled" calculations

Slide 18

Example: Tsort Topological request: A numbering of the vertices of a coordinated non-cyclic diagram with the end goal that each edge from a vertex numbered i to a vertex numbered j fulfills i<j Tsort: Number the vertices in topological request 3 6 1 7 2 5 4

Slide 19

Tsort Algorithm If the chart has all the more then one vertex that has indegree 0, add a vertice to interface with all indegree-0 vertices Let the indegree 0 vertice be s Use s as begin vertice, and process the DFS woodland The passing time of the vertices speak to the turn around of topological request

Slide 20

Tsort (Demonstration) 1 2 3 4 12 13 8 5 16 11 10 7 15 14 9 6 A B C G S D F E G C F B An E D  D E A B F C G

Slide 21

Example: SCC A chart is emphatically associated if for any combine of vertices u and v , one can go from u to v and from v to u . Casually, a SCC of a chart is a subset of vertices that structures a firmly associated subgraph does not frame an emphatically associated subgraph with the expansion of any new vertex

Slide 22

SCC (Illustration)

Slide 23

SCC (Algorithm) Compute the DFS backwoods of the diagram G to get the demise time of the vertices Reverse all edges in G to shape G\' Compute a DFS woodland of G\', yet dependably pick the vertex with the most recent passing time while picking the root for another tree The SCCs of G are the DFS trees in the DFS timberland of G\'

Slide 24

F A D B C G H SCC (Demonstration) 1 2 3 13 10 4 14 6 12 9 8 16 11 5 15 7 - A B - A C D C E F An E B H D A D G F B C G H

Slide 25

An E B H E D F G F C A D B C G H SCC (Demonstration)

Slide 26

DFS Summary DFS spreading over tree/woodland We can utilize birth time and demise time in DFS traversing tree to do shifts things, for example, Tsort, SCC Notice that in the past slides, we related birth time and passing time. In any case, in the talked about applications, birth time and demise time can be free , ie. birth time and demise time can utilize distinctive time counter

Slide 27

Breadth-first inquiry (BFS) Revised: DFS: keep going to next vertex at whatever point there is a street, backpedal if no street (ie. visit to the profundity of current way) BFS: experience all the adjoining vertices before going further (ie. spread among next vertices) so as to "spread", we have to makes utilization of an information structure, line ,to recollect just went to vertices

Slide 28

BFS (Pseudo code) while line not void dequeue the principal vertex u from line for every vertex v specifically reachable from u if v is unvisited enqueue v to line mark v as gone by Initially all vertices with the exception of the begin vertex are set apart as unvisited and the line contains the begin vertex just

Slide 29

I G D C H unvisited went by An E J went to (dequeued) F B BFS (Demonstration) Queue: A B C F D E H G J I

Slide 30

Applications of BFS Shortest ways discovering Flood-fill (can likewise be taken care of by DFS)

Slide 31

Comparisons of DFS and BFS

Slide 32

What is diagram displaying? Change of an issue into a diagram issue Sometimes an issue can be effectively settled once its basic chart model is perceived Graph demonstrating shows up practically consistently in NOI or IOI

Slide 33

Basics of diagram displaying A couple steps: recognize the vertices and the edges distinguish the target of the issue express the goal in chart terms usage: develop the chart from the info occasion run the appropriate chart calculations on the chart change over the yield to the required arrangement

Slide 34

begin objective Simple illustrations (1) Given a framework labyrinth with impediments, locate a briefest way between two given focuses

Slide 35

Simple cases (2) An understudy has the telephone quantities of some different understudies Suppose you know all matches (A, B) to such an extent that A has B\'s number Now you need to know Alan\'s number, what is the base number of calls you have to make?

Slide 36

Simple cases (2) Vertex: understudy Edge: regardless of whether A has B\'s number Add an edge from A to B if A has B\'s number Problem: locate a briefest way from your vertex to Alan\'s vertex

Slide 37

Complex illustrations (1) Same settings as straightforward case 1 You know a trap – strolling through a deterrent! Be that as it may, it can be utilized for just once What ought to a vertex speak to? your position as it were? your position + whether you have utilized the trap

Slide 38

Complex cases (1) A vertex is in the shape ( position , utilized ) The vertices are separated into two gatherings trap utilized trap not utilized

Slide 39

begin objective Complex cases (1) unused begin objective utilized objective

Slide 40

Complex illustrations (1) How about you can stroll through obstructions for k times?

Slide 41

Complex cases (1) k begin objective k-1 k-2

Slide 42

Complex illustrations (1) k begin objective k-1 k-4 k-3 k-2

Slide 43

1 2 3 4 5 6 7 8 Complex cases (2) The renowned 8-bewilder Given a state, discover the moves that convey it to the objective state

Slide 44

Complex cases (2) What does a vertex speak to? the position of the vacant square? the quantity of tiles that are in wrong positions? the express (the places of the eight tiles) What are the edges? What is the comparable chart issue?

Slide 45

1 2 3 4 5 6 1 2 3 7 8 4 5 6 7 8 1 2 3 4 6 7 5 8 1 2 3 4 5 3 5 7 8 6 1 2 3 4 5 6 7 8 Complex cases (2)

Slide 46

Complex cases (3) Theseus and Minotaur http://www.logicmazes.com/theseus.html Extract: Theseus must escape from a labyrinth. There is additionally a mechanical Minotaur in the labyrinth. For each turn that Theseus takes, the Minotaur takes two turns. The Minotaur takes after this program for each of his two turns: First he tests in the event that he can draw on a level plane and get nearer to Theseus. On the off chance that he would, he be able to will move one square on a level plane. On the off chance that he can\'t, he will test on the off chance that he could draw vertically and get nearer to Theseus. On the off chance that he would, he be able to will move one square vertically. In the event that he can\'t move either on a level plane or vertically, then he just skirts that turn.

Slide 47

Complex illustrations (3) What does a vertex speak to? Theseus\' position Minotaur\'s position Both

Slide 48

Some more cases How can the followings be displayed? Tilt labyrinth (Single-objective labyrinths just) http://www.clickmazes.com/newtilt/ixtilt2d.htm Double title labyrinth http://www.clickmazes.com/newtilt/ixtilt.htm No-left-turn labyrinth http://www.clickmazes.com/noleft/ixnoleft.htm Same as intricate case 1, yet you can utilize the trap for k

Recommended
View more...