[PDF] [PDF] Inf 2B: Graphs, BFS, DFS Directed and Undirected Graphs A

[PDF] Directed Graph Algorithms - Washington

CSE 373 Data Structures A directed graph with a cycle cannot be topologically If no such vertices, graph has only cycle(s) (cyclic graph) • Topological sort 

[PDF] Decremental Data Structures for Connectivity and - DROPS

We introduce a new dynamic data structure for maintaining the strongly connected components (SCCs) of a directed graph (digraph) under edge deletions, 

[PDF] Directed Graphs - Data Structures and Algorithms for CL III

A directed graph or digraph is a set " of vertices – together with a collection # of pairwise connections between vertices from ", called edges where all the edges 

[PDF] Directed Graphs

Every data structure is a digraph ・Vertex = object ・Edge = reference Roots Objects known to be directly accessible by program 

[PDF] Inf 2B: Graphs, BFS, DFS Directed and Undirected Graphs A

Which data structure has faster (asymptotic) worst-case running-time, for checking if w is adjacent to v, for a given pair of vertices? 1 Adjacency list is faster 2

ON THE APPLICATION OF GRAPH THEORY TO COMPUTER DATA

tures can be represented by directed graph structures and the purpose of this paper is or identified during the creation of the data structure, then it can be used

[PDF] A Technique for Drawing Directed Graphs - Graphviz

These algorithms are the basis of a practical implementation [GNV1] 1 1 Aesthetic criteria To make drawings, it helps to assume that a directed graph has an 

[PDF] directed graph java

[PDF] directed graph pdf

[PDF] directed graph reachability

[PDF] directed writing igcse paper 2

[PDF] directeur france bleu sud lorraine

[PDF] directional selection

[PDF] directions to port canaveral cruise ships

[PDF] director appointment letter doc

[PDF] director's cut

[PDF] directors chair home depot

[PDF] directors chair replacement covers

[PDF] directors chair with side table

[PDF] directors chairs for sale

[PDF] directors guild of america basic agreement

[PDF] directors guild of america los angeles

Inf2B:Gr aphs,BFS ,DFS

KyriakosKalorkoti

SchoolofInf ormatics

UniversityofEdinburgh

1/26

DirectedandUndirected Graphs

I Agraphisamathematical structureconsisting ofaset of verticesandaset ofedgesconnectingthev ertices . I

Formally:G=(V,E),whereVisaset andE✓V⇥V.

I

Foredgee=(u,v)wesaythateisdirectedfromu tov .

I

G=(V,E)undirectediffor allv,w2V:

(v,w)2E()(w,v)2E.

Otherwisedirected.

Directed⇠arrows(one-way)

Undirected⇠lines(two-way)

I

WeassumeVisfinite, henceEisalsofinite .

2/26

Adirectedg raph

G=(V,E),

V=

0,1,2,3,4,5,6

E= (0,2),(0,4),(0,5),(1,0),(2,1),(2,5), (3,1),(3,6),(4,0),(4,5),(6,3),(6,5)

0236541

3/26

Anundirectedg raph

badefgc 4/26

Examples

I

RoadMaps.

Edgesrepresentstreets andv erticesrepresent crossings (junctions). I

ComputerNetwor ks.

networkconnections(cables)betweenthem. I

TheWor ldWideWeb.

Verticesrepresentwebpages,andedges represent

hyperlinks. I 5/26

Adjacencymatrices

LetG=(V,E)beag raphwith nvertices.VerticesofGare

numbered0,...,n1.

Theadjacencymatrix ofGisthen⇥nmatrix

A=(a ij

0i,jn1

with a ij

1,ifthereis anedge fromver texitover texj;

0,otherwise.

6/26

Adjacencymatrix (Example)

0236541

0 B B B B B B B B

0010110

1000000

0100010

0100001

1000010

0000000

0001010

1 C C C C C C C C A 7/26

Adjacencylists

Arraywithoneentryf oreachv ertex v,whichis alist ofall verticesadjacenttov.

Example

02365412455103550610125634

8/26

QuickQuestion

Given:graphG=(V,E),withn=|V|,m=|E|.

Forv2V,we writein(v)forin-degree,out(v)forout-degree. Whichdatastr ucturehasf aster(asymptotic)worst-case running-time,forcheckingifwis adjacenttov ,for agivenpair ofver tices?

1.Adjacencylistis faster .

2.Adjacencymatrix isfaster.

3.Bothhav ethesameasymptoticworst-caserunning-time .

4.Itdepends.

Answer:2.ForanAdjacencyMatrix we cancheck in⇥(1)time. Anadjacencylist structuretak es⇥(1+out(v))time. 9/26

QuickQuestion

Given:graphG=(V,E),withn=|V|,m=|E|.

Forv2V,we writein(v)forin-degree,out(v)forout-degree. Whichdatastr ucturehasf aster(asymptotic)worst-case running-time,forvisitingallv ertices wadjacenttov,for agiven vertexv?

1.Adjacencylistis faster .

2.Adjacencymatrix isfaster.

3.Bothhav ethesameasymptoticworst-caserunning-time .

4.Itdepends.

Answer:3.Adjacencymatrix requires⇥(n)timealwa ys.

Adjacencylistrequires ⇥(1+out(v))time.

Inworst-case out(v)=⇥(n).

10/26

AdjacencyMatrices vsAdjacencyLists

adjacencymatrix adjacencylist

Space⇥(n

2 )⇥(n+m)

Timetochec kifw⇥(1)⇥(1+out(v))

adjacenttov

Timetovisit allw⇥(n)⇥(1+out(v))

adjacenttov.

Timetovisit alledges⇥(n

2 )⇥(n+m) 11/26

Sparseanddense graphs

G=(V,E)graphwithnverticesandmedges

Observation:mn

2 I

Gdenseifmcloseton

2 I

Gsparseifmmuchsmallerthann

2 12/26

Graphtraversals

Atraversalisastr ategyfor visitingallverticesof agraphwhile respectingedges.

BFS=breadth-firstsearch

DFS=depth-firstsearch

Generalstrategy:

1.Letvbeanarbitr aryv ertex

2.Visitallv ertices reachablefromv

3.Ifthereare vertices thathav enotbeenvisited,letvbe

suchav ertex andgobackto(2) 13/26

GraphSearching(generalStr ategy)

AlgorithmsearchFromVertex(G,v)

1.markv

2.putvontoscheduleS

3.whilescheduleSisnotempty do

4.removeavertexvfromS

5.forallwadjacenttovdo

6.ifwisnotmar kedthen

7.markw

8.putwontoscheduleS

Algorithmsearch(G)

1.ensurethateach ver texof Gisnotmar ked

2.initialisescheduleS

3.forallv2Vdo

4.ifvisnotmar kedthen

5.searchFromVertex(G,v)

14/26

Threecolourvie wofv ertices

I

Previousalgorithmhasv erticesinoneoftw ostates:

unmarkedandmarked.Progression is unmarked!marked I

Canalsothink ofthemas beinginone ofthreestates

(representedby colours): I

White:noty etseen(not yetinvestigated).

I

Grey:puton schedule(underin vestigation).

I

Black:taken offschedule(completed).

Progressionis

white!grey!black

Wewillusethethree colourscheme whenstudyingan

algorithmfortopological sortingofgraphs . 15/26 BFS Visitallv erticesreachab lefromvinthef ollowingorder : I v I allneighboursof v I allneighboursof neighboursofvthathav enotbeen visitedyet I allneighboursof neighboursofneighbours ofvthathav e notbeenvisited yet I etc. 16/26

BFS(usinga Queue)

Algorithmbfs(G)

1.InitialiseBooleanarr ay visited,settingall entriesto FALSE.

2.InitialiseQueueQ

3.forallv2Vdo

4.ifvisited[v]=FALSEthen

5.bfsFromVertex(G,v)

17/26

BFS(usinga Queue)

AlgorithmbfsFromVertex(G,v)

1.visited[v]=TRUE

2.Q.enqueue(v)

3.whilenotQ.isEmpty()do

4.v Q.dequeue()

5.forallwadjacenttovdo

6.ifvisited[w]=FALSEthen

7.visited[w]=TRUE

8.Q.enqueue(w)

18/26

AlgorithmbfsFromVertex(G,v)

1.visited[v]=TRUE

2.Q.enqueue(v)

3.whilenotQ.isEmpty()do

4.v Q.dequeue()

5.forallwadjacenttovdo

6.ifvisited[w]=FALSEthen

7.visited[w]=TRUE

8.Q.enqueue(w)

0236541

19/26

QuickQuestion

Givenagraph G=(V,E)withn=|V|,m=|E|,whatis the

worst-caserunningtimeof BFS,interms ofm,n?

1.⇥(m+n)

2.⇥(n

2

3.⇥(mn)

4.Dependsonthe number ofcomponents.

Answer:1.Toseethisneedto becarefulabout bounding

runningtimeforthe loopat lines5-8.

MustusetheAdjacency Liststructure .

Answer:2.ifwe useadjacencymatrixrepresentation.

20/26 DFS Visitallv erticesreachab lefromvinthef ollowingorder : I v I someneighbourwofvthathasnot beenvisited yet I someneighbourxofwthathasnot beenvisited yet I etc.,untilthe currentv ertex hasnoneighbour thathasnot beenvisitedy et I

Backtracktothefirstvertexthat hasay etunvisited

neighbourv 0 I

Continuewithv

0 ,aneighbour ,aneighbour ofthe neighbour,etc.,backtrac k,etc. 21/26

DFS(usinga stack)

Algorithmdfs(G)

1.InitialiseBooleanarr ay visited,settingall toFALSE

2.InitialiseStackS

3.forallv2Vdo

4.ifvisited[v]=FALSEthen

5.dfsFromVertex(G,v)

22/26

DFS(usinga stack)

AlgorithmdfsFromVertex(G,v)

1.S.push(v)

2.whilenotS.isEmpty()do

3.v S.pop()

4.ifvisited[v]=FALSEthen

5.visited[v]=TRUE

6.forallwadjacenttovdo

7.S.push(w)

0236541

23/26

RecursiveDFS

Algorithmdfs(G)

1.InitialiseBooleanarr ay visited

bysettingallentries toFALSE

2.forallv2Vdo

3.ifvisited[v]=FALSEthen

4.dfsFromVertex(G,v)

AlgorithmdfsFromVertex(G,v)

1.visited[v] TRUE

2.forallwadjacenttovdo

3.ifvisited[w]=FALSEthen

4.dfsFromVertex(G,w)

24/26

AnalysisofDFS

G=(V,E)graphwithnverticesandmedges

Withoutrecursive calls:

I dfs(G):time⇥(n) I

Overalltime:

T(n,m)=⇥(n)+

P v2V ⇥(1+out-degree(v)) n+ P v2V (1+out-degree(v)) n+n+ P v2V out-degree(v) n+ P v2V out-degree(v) =⇥(n+m) 25/26
quotesdbs_dbs17.pdfusesText_23