Source code online books for professionals by professionals


NODe COLOrS aND eDGe tYpeS



Download 4,67 Mb.
Pdf ko'rish
bet84/266
Sana31.12.2021
Hajmi4,67 Mb.
#213682
1   ...   80   81   82   83   84   85   86   87   ...   266
Bog'liq
2 5296731884800181221

NODe COLOrS aND eDGe tYpeS
in describing traversal, i have distinguished between three kinds of nodes: those we don’t know about, those 
in our queue, and those we’ve visited (and whose neighbors are now in the queue). some books (such as 
Introduction to Algorithms, by Cormen et al., mentioned in Chapter 1) introduce a form of node coloring, which 
is especially important in Dfs. each node is considered white to begin with; they’re gray in the interval between 
their discover time and their finish time, and they’re black thereafter. you don’t really need this classification in 
order to implement Dfs, but it can be useful in understanding it (or, at least, it might be useful to know about it if 
you’re going to read a text that uses the coloring).
in terms of trémaux’s algorithm, gray intersections would be ones we’ve seen but have since avoided; black 
intersections would be the ones we’ve been forced to enter a second time (while backtracking).
these colors can also be used to classify the edges in the Dfs tree. if an edge uv is explored and the node v is 
white, the edge is a tree edge—that is, it’s part of the traversal tree. if v is gray, it’s a so-called back edge, one 
that goes back to an ancestor in the Dfs tree. finally, if v is black, the edge is either what is called a forward edge 
or a cross edge. a forward edge is an edge to a descendant in the traversal tree, while a cross edge is any other 
edge (that is, not a tree, back or forward edge).
note that you can classify the edges without actually using any explicit color labeling. let the time span of a 
node be the interval from its discover time to its finish time. a descendant will then have a time span contained 
in its ancestor’s, while nodes unrelated by ancestry will have nonoverlapping intervals. thus, you can use the 
timestamps to figure out whether something is, say, a back or forward edge. even with color labeling, you’d need 
to consult the timestamps to differentiate between forward and cross edges.
you probably won’t need this classification much, although it does have one important use. if you find a back 
edge, the graph contains a cycle, but if you don’t, it doesn’t. (exercise 5-10 asks you to show this.) in other words
you can use Dfs to check whether a graph is a Dag (or, for undirected graphs, a tree). exercise 5-11 asks you to 
consider how other traversal algorithms would work for this purpose.


Chapter 5 

 traversal: the skeleton key of algorithmiCs
106
Infinite Mazes and Shortest (Unweighted) Paths
Until now, the overeager behavior of DFS hasn’t been a problem. We let it loose in a maze (graph), and it veers off in 
some direction, as far as it can, before it starts backtracking. This can be problematic, though, if the maze is extremely 
large. Maybe what we’re looking for, such as an exit, is close to where we started; if DFS sets off in a different direction, 
it may not return for ages. And if the maze is infinite, it will never get back, even though a different traversal might have 
found the exit in a matter of minutes. Infinite mazes may sound far-fetched, but they’re actually a close analogy to an 
important type of traversal problem—that of looking for a solution in a state-space.
But getting lost by being over-eager, like DFS, isn’t only a problem in huge graphs. If we’re looking for the shortest 
paths (disregarding edge weights, for now) from our start node to all the others, DFS will, most likely, give us the wrong 
answer. Take a look at the example in Figure 
5-6
. What happens is that DFS, in its eagerness, keeps going until it reaches 
c via a detour, as it were. If we want to find the shortest paths to all other nodes (as illustrated in the figure on the right), 
we need to be more conservative. To avoid taking a detour and reaching a node “from behind,” we need to advance our 
traversal “fringe” one step at a time. First visit all nodes one step away and then all those two steps away, and so forth.
14
In other words, let’s think inductively.
15
IDDFS isn’t completely equivalent to Ore’s method because it doesn’t mark edges as closed in the same way. Adding that kind of 
marking is certainly possible and would be a form of pruning, discussed later in this chapter.
c
d
a
b
c
d
a
b
DFS tree from a
SP tree from a

Download 4,67 Mb.

Do'stlaringiz bilan baham:
1   ...   80   81   82   83   84   85   86   87   ...   266




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish