CS计算机代考程序代写 algorithm Introduction

Introduction

Ch.22.Elementary Graph Algorithms
Read all sections
Omit theorems, corollaries, lemmas and their proofs (but learn the results described in the slides)

2
Conventions
V – set of vertices or nodes
E – set of edges
|V| = # of vertices or nodes = n
|E| = # of edges = m

3
22.1 Representations of graphs
types: undirected, directed & weighted graphs
what is the max # of edges in a n-node undirected graph?
adjacency matrix representation (for dense graphs)
adjacency-list representation (for sparse graphs)

4

Understand these examples!

5
22.2 Breadth-first search
An algorithm for searching a graph
Starting from a vertex s, visits every vertex that is reachable from s
Called breadth-first because it visits all vertices reachable from s in 1 step (by 1 edge) first, then those reachable in 2 steps, and so on.
Produces a breadth-first tree

6
22.2 Breadth-first search

Complexity: Θ(|V|+|E|)

7

The operation of BFS
Thinking Assignment: Work out and understand this example yourself

8

The operation of BFS

9

The operation of BFS
Thinking Assignment: Draw the breadth-first tree created by BFS
Thinking Assignment: What are the distances & shortest paths from s to every other node?

10
Thinking Assignment
PRINT_PATH(G, source, destination )
1 if source = destination
2 then print source
3 else if π[destination ]=NIL
4 then print “no path from” source “to” destination
5 else PRINT-PATH(G, source, π[destination])
6 print destination
Understand and simulate this recursive algorithm on the previous graph with source=s and destination=y

11
22.3 Depth-First Search
Another graph search algorithm
Depth-first: Go as deep as possible from s, then backtrack to find unvisited nodes
Builds a depth-first forest (several depth-first trees) in the process
Places two time stamps on each vertex: d[v] the time at which a vertex is “discovered” and f[v] when it’s processing is finished; Each timestamp is an integer between 1 and 2n

12
22.3 Depth-First Search

Complexity: Θ(|V|+|E|)

13

The operation of DFS
Thinking Assignment: Work out and understand this example yourself

14

The progress of DFS

15

The progress of DFS

16

The progress of DFS

17
Depth-first forest
Depth-first forest consists of trees that represent the edges of the original graph that the DFS algorithm traversed
These edges are called tree edges
The remaining edges in the original graph can be classified as back, forward, or cross edges
DFS of an undirected graph will produce only tree and back edges
DFS of a directed graph may produce tree, back, forward, or cross edges

18

Example: Graph, its depth-first forest and other edges
Thinking Assignment: Work out and understand this example yourself

19
To check if a graph has a cycle or not: a graph is acyclic if and only if the depth-first forest trees have no back edges
To check if the graph has one or more nodes whose removal will split the graph into separate pieces: if there are no such nodes (called articulation points) the graph is said to be biconnected.
To sort the nodes of the graph so that constraints modeled by the graph edges are satisfied: topological sort.
Depth-first search applications

20
22.4 Topological sort

21

Complexity: Θ(|V|+|E| )

Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level

22

Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level

Thinking Assignment
Come up with a different Topological Algorithm using this strategy:
In-degree of a node is the # of edges coming into it; if a node has in-degree zero, then it means that it is not dependent on any other nodes;
therefore, determine the in-degree of all nodes in the graph and store those;
if there is at least one such node (what does it mean if there are no such nodes?), output that as the first node in TO;
then remove all outgoing edges from it by decrementing the in-degrees of all nodes connected by those outgoing edges;
if that makes the in-degree of any node to be zero, output that as the first node in TO (what does it mean if there are no such nodes?);
repeat steps 2-4 until all nodes have been output to the TO
23

1534
24
253
412
25
1
2
3
4
5
1
54
2
3
01001
10111
01010
01101
11010
















1
2
3
4
5
12345

5
65
2
4
24
1
2
3
4
5
6
6
1
45
23
6
010100
000010
000011
010000
000100
000001


















1
2
3
4
5
12345
6
6

BFS(G, s)
1 for each vertex
uVG s (){}

2
whiteucolor ][

3
][ud

4
NILu][

5
grayscolor ][

6
0][sd

7
NILs][

8
}{sQ

9 while
Q

10
][Qheadu

11 for each
][uadjv

12 if
color v white[]

13 then
grayvcolor ][

14
1][][ udvd

15
uv][

16 ENQUEUE(Q, v)
17 DEQUEUE(Q)
18
BLACKucolor ][

white
u
color
=
]
[

¥
=
]
[
u
d

NIL
u
=
]
[
p

gray
s
color
=
]
[

0
]
[
=
s
d

NIL
s
=
]
[
p

}
{
s
Q
=

BFS(G, s)

1
for each vertex

2

3

4

5

6

7

8

9
while

_1413089611.unknown

_1413089662.unknown

_1413089733.unknown

_1413089759.unknown

_1413089698.unknown

_1413089638.unknown

_931259556.unknown

_1413089586.unknown

_931259297.unknown

]
[
Q
head
u
=

]
[
u
adj
v
=

gray
v
color
=
]
[

1
]
[
]
[
+
=
u
d
v
d

u
v
=
]
[
p

BLACK
u
color
=
]
[

10

11
for each

12
if

13
then

14

15

16
ENQUEUE(Q, v)

17
DEQUEUE(Q)

18

_1413089819.unknown

_1413089885.unknown

_1413090045.unknown

_1413090046.unknown

_1413090044.unknown

_1413089853.unknown

_931259654.unknown

DFS(G)
1 for each vertex
uVG[]

2
whiteucolor ][

3
NILu][

4
0time

5 for each vertex
uVG[]

6 if
color u white[]

7 then DFS-VISIT(u)

DFS-VISIT(u)
1
color u gray[]

2
1][  timetimeud

3 for each
vadj u []

4 if
whitevcolor ][

5 then
uv][

6 DFS-VISIT(v)
7
color u black[]

8
1][  timetimeuf

white
u
color
=
]
[

NIL
u
=
]
[
p

0
=
time

DFS(G)

1
for each vertex

2

3

4

5
for each vertex

6
if

7
then DFS-VISIT(u)

_931281985.unknown

_1413090085.unknown

_1413090103.unknown

_1413090121.unknown

_931282000.unknown

_931281853.unknown

1
]
[
+
=
=
time
time
u
d

white
v
color
=
]
[

u
v
=
]
[
p

1
]
[
+
=
=
time
time
u
f

DFS-VISIT(u)

1

2

3
for each

4
if

5
then

6
DFS-VISIT(v)

7

8

_931282104.unknown

_1270379603.unknown

_1413090340.unknown

_1413090341.unknown

_1413090205.unknown

_931282252.unknown

_931282068.unknown

A topological sort of a directed acyclic graph G = (V, E) is a linear
ordering of all its vertices such that if G contains an edge ( u, v), then
u appears before v in the ordering.

A topological sort of a directed acyclic graph G = (V, E) is a linear ordering of all its vertices such that if G contains an edge (u, v), then u appears before v in the ordering.

TOPOLOGICAL_SORT( G)
1 call DFS(G) to compute finishing time f( v) for each
vertex v.
2 as each vertex is finished, insert it onto the front of a
link list.
3 return the link list of vertices

TOPOLOGICAL_SORT(G)

1
call DFS(G) to compute finishing time f(v) for each vertex v.

2
as each vertex is finished, insert it onto the front
of a link list.

3
return the link list of vertices

/docProps/thumbnail.jpeg