Data Structures（数据结构）Course 12Graphs.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * Adjacency List Two-dimensional linked list to store the edges or arcs Graph Algorithms Graph data Structure Graph Algorithms Create Graph Insert Vertex Delete Vertex Insert Arc Delete Arc Retrieve Vertex First Arc Traverse Depth-first Traversal Algorithm Algorithm depthfirst (val graphmetadata Processing the keys of the graph is depth-first order. Pre graph is a pointer to a graph head structure Post vertices “processed” If (empty graph) Return Set processed flags to not processed 2 walkPtr=graph.first Loop (walkPtr) 1 walkPtr-processed = 0 2 walkPtr =walkPtr-nextVertex End loop Process each vertex in list createStack(stack) 6 walkPtr=graph.first 7 loop(walkPtr not null) 1 if (walkPtr-Processed 2) 1 if (walkPtr-processed 1) Push and set flag to stack 1 puchStack(stack,walker) 2 walkPtr-processed =1 2 end if Process vertex at stack top 3 loop (not emptyStack(stack)) 1 popStack(stack,vertexPtr) 2 process(vertex-dataPtr) 3 vertexPtr-processed =2 Push all Vertices from adjacency list 4 arcwalkPtr=vertexPr-arc 5 loop( arcwalkPtr not null) 1 vertToPtr=arcwalkPtr-destination 2 if (vertToPtr-processed is 0) 1 puchStack(sack,VertToPtr) 2 vertToPtr-Processed =1 3 end if 4 arcwalkPtr=arcwalkPtr-nextArc 6 end loop 4 end loop 2 end if 3 walkPtr-walkPtr-nextVertex 8 end loop 9 destroyStack(stack) Return End depthfirst Breadth-first Traversal Algorithm Algorithm Breadthfirst (val graphmetadata Processing the keys of the graph is Breadth-first order. Pre graph is a pointer to a graph head structure Post vertices “processed If (empty graph) 1 return 2 End if Fist se all processed flags to not processed Falg:0– not processed, 1– enqueued, 2