Source code online books for professionals by professionals



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

Listing 5-8.  Topological Sorting Based on Depth-First Search
def dfs_topsort(G):
    S, res = set(), []                          # History and result
    def recurse(u):                             # Traversal subroutine
        if u in S: return                       # Ignore visited nodes
        S.add(u)                                # Otherwise: Add to history
        for v in G[u]:
            recurse(v)                          # Recurse through neighbors
        res.append(u)                           # Finished with u: Append it
13
The dfs_topsort function can also be used to sort the nodes of a general graph by decreasing finish times, as needed when 
looking for strongly connected components, discussed later in this chapter.


Chapter 5 

 traversal: the skeleton key of algorithmiCs
105
    for u in G:
        recurse(u)                              # Cover entire graph
    res.reverse()                               # It's all backward so far
    return res
 
There are a few things that are worth noting in this new topological sorting algorithm. For one thing, I’m explicitly 
including a for loop over all the nodes to make sure the entire graph is traversed. (Exercise 5-8 asks you to show 
that this will work.) The check for whether a node is already in the history set (S) is now placed right inside recurse
so we don’t need to put it in both of the for loops. Also, because recurse is an internal function, with access to the 
surrounding scope (in particular, S and res), the only parameter needed is the node we’re traversing from. Finally, 
remember that we want the nodes to be sorted in reverse, based on their finish times. That’s why the res list is 
reversed before it’s returned.
This topsort performs some processing on each node as it backtracks over them (it appends them to the result 
list). The order in which DFS backtracks over nodes (that is, the order of their finish times) is called postorder, while 
the order in which it visits them in the first place is called preorder. Processing at these times is called preorder or 
postorder processing. (Exercise 5-9 asks you to add general hooks for this sort of processing in DFS.)

Download 4,67 Mb.

Do'stlaringiz bilan baham:
1   ...   79   80   81   82   83   84   85   86   ...   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