Network OptimizationSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45The depth first search treeSlide 47Network OptimizationDepth First SearchJames Orlin 20102Initialize LISTUnmark all nodes in N;12453 697812453 697811Mark node 1 and add it to LIST13Select a node i in LIST LISTSelect last node in LIST12453 697811114If node i is incident to an admissible arc… LISTScan an arc out of node 1.12453 69781111222If endpoint is unmarked, then mark it and add it to LIST.5Select the last node on LIST LIST12453 6978111122212Select Node 2.63If node i is incident to an admissible arc… LIST12453 6978111122212Scan arc out of node 2.44Mark node 4 and add it to LIST.73Select LIST12453 6978111122212Select node 4442483If node i is incident to an admissible arc… LIST12453 69781111222124424Scan arc out of node 4.848Mark 8 and add it to LIST.93Select LIST12453 6978111122212424848Select node 848103If node i is not incident to an admissible arc… LIST12453 697811112221242484848If there are no unscanned arcs out of node 8, delete it from LIST.113Select LIST12453 697811112221242484848Select Node 4841253If node i is incident to an admissible arc… LIST12453 69781111222124248484884Scan arc out of node 4.55Mark 5 and add it to LIST.1353Select LIST12453 6978111122212424848488455Select node 5451453If node i is incident to an admissible arc… LIST12453 697811112221242484848845545Scan arc out of node 5.666Mark 6 and add it to LIST.1553Select the last node on LIST LIST12453 697811112221242484848845545Select node 66665616753If node i is incident to an admissible arc… LIST12453 69781111222124248484884554566656Scan arc out of node 6.99Mark 9 and add it to LIST.17753Select the last node on LIST LIST12453 69781111222124248484884554566656Select node 99969188753If node i is incident to an admissible arc… LIST12453 697811112221242484848845545666569969Scan arc out of node 9.77Mark 7 and add it to LIST.198753Select the last node on LIST LIST12453 697811112221242484848845545666569969Select node 77797208753Scan arc (7,4) LIST12453 697811112221242484848845545666569969Scan arc out of node 77797If endpoint is marked, then label arc as “scanned”.218753Scan arc (7,5) LIST12453 697811112221242484848845545666569969Scan arc out of node 77797If endpoint is marked, then label arc as “scanned”.228753Scan arc (7,8) LIST12453 697811112221242484848845545666569969Scan arc out of node 77797If endpoint is marked, then label arc as “scanned”.238753If node i is not incident to an admissible arc… LIST12453 697811112221242484848845545666569969There are no arcs out of 7. Delete 7 from LIST7797248753Select node 9 LIST12453 697811112221242484848845545666569969779779Select node 9.258753Scan (9,4) LIST12453 697811112221242484848845545666569969779779Scan arc out of node 9. If endpoint is marked, then label arc as “scanned”.268753Delete 9 from LIST LIST12453 69781111222124248484884554566656996977977Node 9 has no incident arcs. Delete it from list. 9278753Select node 6 LIST12453 697811112221242484848845545666569969Select node 6.77977996288753Scan arc (6.7) LIST12453 697811112221242484848845545666569969Select arc out of node 6. 77977996298753Select node 6 LIST12453 697811112221242484848845545666569969779779Delete node 6 from LIST96308753Select node 5 LIST12453 697811112221242484848845545666569969Select Node 57797799665318753Select node 5 LIST12453 697811112221242484848845545666569969779779Delete node 5 from LIST9665328753Select node 4 LIST12453 697811112221242484848845545666569969Select node 47797799665544338753Delete node 4 LIST12453 697811112221242484848845545666569969779779Delete node 4 from LIST966554348753Select node 2 LIST12453 697811112221242484848845545666569969Select Node 277977996655442358753Scan arc (2,5) LIST12453 697811112221242484848845545666569969Scan arc out of node 277977996655442368753Delete node 2 LIST12453 697811112221242484848845545666569969779779Delete node 2 from LIST966554422378753Select node 1 LIST12453 6978111122212424848488455456665699697797799665544221Select node 13898753Scan arc (1,3) LIST12453 6978111122212424848488455456665699697797799665544221Scan arc out of node 1333998753Select node 3 LIST12453 6978111122212424848488455456665699697797799665544221Select node 333134098753Scan arcs (3,5) and (3,6) LIST12453 6978111122212424848488455456665699697797799665544221Scan arcs out of node 333134198753Delete node 3 LIST12453 69781111222124248484884554566656996977977996655442213313Delete node 3 from LIST4298753Select node 1 LIST12453 6978111122212424848488455456665699697797799665544221Select node 13313314398753Scan arc (1, 5) LIST12453 6978111122212424848488455456665699697797799665544221Scan arc out of (1,5)3313314498753Delete node 1 LIST12453 6978111122212424848488455456665699697797799665544221Delete node 1 from LIST3313314598753LIST is empty LIST12453 6978111122212424848488455456665699697797799665544221The algorithm ends!331331146132 9875486796542 31The depth first search treeNote that each induced subtree has consecutively labeled nodesMITOpenCourseWarehttp://ocw.mit.edu15.082J / 6.855J / ESD.78J Network OptimizationFall 2010 For information about citing these materials or our Terms of Use, visit: