FilesExpand file tree

 master

/

topsort.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

58 lines (49 loc) · 1.19 KB

 master

/

topsort.py

Copy path

Top

File metadata and controls

• Code
• Blame

58 lines (49 loc) · 1.19 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

"""

Given a list of system packages,

some packages cannot be installed until the other packages are installed.

Provide a valid sequence to install all of the packages.

e.g.

a relies on b

b relies on c

then a valid sequence is [c, b, a]

"""

depGraph = {

"a" : [ "b" ],

"b" : [ "c" ],

"c" : [ 'e'],

'e' : [ ],

"d" : [ ],

"f" : ["e" , "d"]

}

given = [ "b", "c", "a", "d", "e", "f" ]

def retDeps(visited, start):

queue = []

out = []

queue.append(start)

while queue:

newNode = queue.pop(0)

if newNode not in visited:

visited.add(newNode)

for child in depGraph[newNode]:

queue.append(child)

out.append(child)

out.append(start)

return out

def retDepGraph():

visited = set()

out = []

# visited.add(given[0])

for pac in given:

if pac in visited:

continue

visited.add(pac)

#out.append(pac)

if pac in depGraph:

# find all children

for child in depGraph[pac]:

if child in visited:

continue

out.extend(retDeps(visited, child))

out.append(pac)

print(out)

retDepGraph()