Chapter 11 - Graph • A Graph G consists of a set V, whose members are called the vertices of G, together with a set E of pairs of distinct vertices from V. • The pairs in E are called the edges of G. • If the pairs are unordered, G is called an undirected graph or a graph. Otherwise, G is called a directed graph or a digraph.
• Two vertices in an undirected graph are called adjacent if there is an edge from the first to the second. Chapter 11 - Graph • A path is a sequence of distinct vertices, each adjacent to the next. • A cycle is a path containing at least three vertices such that the last vertex on the path is adjacent to the first. • A graph is called connected if there is a path from any vertex to any other vertex.
• A free tree is defined as a connected undirected graph with no cycles. Examples of Graph Digraph as an adjacency table Directed graph Adjacency set Adjacency table Digraph count <integer> // Number of vertices edge <array of <array of <boolean> > > // Adjacency table End Digraph Weighted-graph as an adjacency table Weighted-graph vertex vector adjacency table WeightedGraph count <integer> // Number of vertices edge<array of<array of<WeightType>>> // Adjacency table End WeightedGraph Weighted-graph as an adjacency list Digraph as an adjacency list Directed graph contiguous structure linked structure mixed structure Digraph as an adjacency list (not using List ADT) V Directed graph first_vertex DiGraph first_vertex <pointer to VertexNode> End DiGraph linked structure Digraph as an adjacency list (using List ADT) head digraph GraphNode vertex <VertexType> // (key field) 0 head 1 2 adjVertex<LinkedList of< VertexType >> indegree <int> are hidden 1 head 2 3 outdegree <int> from the isMarked <boolean> image below 2 head End GraphNode 3 head 0 1 2 GraphNode ADT List is linked list: vertex adjVertex DiGraph 2 head digraph <LinkedList<of<GraphNode>> End DiGraph Digraph as an adjacency list (using List ADT) GraphNode vertex <VertexType> // (key field) adjVertex<LinkedList of< VertexType >> indegree <int> outdegree <int> isMarked <boolean> End GraphNode mixed list ADT List is contiguous list: DiGraph digraph <ContiguousList<of<GraphNode>> End DiGraph Digraph as an adjacency list (using List ADT) GraphNode vertex <VertexType> // (key field) adjVertex<ContiguousList of< VertexType >> indegree <int> outdegree <int> isMarked <boolean> End GraphNode contiguous list ADT List is contiguous list: DiGraph digraph <ContiguousList<of<GraphNode>> End DiGraph GraphNode <void> GraphNode() // constructor of GraphNode 1.clear() // By default, constructor of adjVertex made it empty. End GraphNode GraphNode vertex adjVertex head Operations for Digraph Insert Vertex Delete Vertex Insert edge Delete edge Traverse Digraph Digraph private: digraph <List of <GraphNode> > // using of List ADT. <void> Remove_EdgesToVertex(val VertexTo <VertexType>) public: <ErrorCode> InsertVertex (val newVertex <VertexType>) <ErrorCode> DeleteVertex (val Vertex <VertexType>) <ErrorCode> InsertEdge (val VertexFrom <VertexType>, val VertexTo <VertexType>) <ErrorCode> DeleteEdge (val VertexFrom <VertexType>, val VertexTo <VertexType>) // Other methods for Graph Traversal.
End Digraph Methods of List ADT Methods of Digraph will use these methods of List ADT: <ErrorCode> Insert (val DataIn <DataType>) // (success, overflow) <ErrorCode> Search (ref DataOut <DataType>) // (found, notFound) <ErrorCode> Remove (ref DataOut <DataType>) // (success , notFound) <ErrorCode> Retrieve (ref DataOut <DataType>) // (success , notFound) <ErrorCode> Retrieve (ref DataOut <DataType>, position <int>) // (success , range_error) <ErrorCode> Replace (val DataIn <DataType>, position <int>) // (success, range_error) <ErrorCode> Replace (val DataIn <DataType>, val DataOut <DataType>) // (success, notFound) <boolean> isFull() <boolean> isEmpty() <integer> Size() Insert New Vertex into Digraph <ErrorCode> InsertVertex (val newVertex <VertexType>) Inserts new vertex into digraph. Insert New Vertex into Digraph <ErrorCode> InsertVertex (val newVertex <VertexType>) 1. return duplicate_error 3.Insert(DataOut) // success or overflow End InsertVertex GraphNode vertex <VertexType> // (key field) adjVertex<List of< VertexType >> indegree <int> outdegree <int> isMarked <boolean> End GraphNode Delete Vertex from Digraph <ErrorCode> DeleteVertex (val Vertex <VertexType>) Deletes an existing vertex. Delete Vertex from Digraph <ErrorCode> DeleteVertex (val Vertex <VertexType>) 1.
return notFound GraphNode End DeleteVertex vertex <VertexType> // (key field) adjVertex<List of< VertexType >> indegree <int> outdegree <int> isMarked <boolean> End GraphNode Auxiliary function Remove all Edges to a Vertex <void> Remove_EdgesToVertex(val VertexTo <VertexType>) Removes all edges from any vertex to VertexTo if exist. position = position + 1 GraphNode End Remove_EdgesToVertex vertex <VertexType> // (key field) adjVertex<List of< VertexType >> indegree <int> outdegree <int> isMarked <boolean> End GraphNode Insert new Edge into Digraph <ErrorCode> InsertEdge (val VertexFrom<VertexType>, val VertexTo <VertexType>) Inserts new edge into digraph. return duplicate_error 3. return success GraphNode 4.
else vertex <VertexType> // (key field) 1. return overflow adjVertex<List of< VertexType >> 2. else indegree <int> 1. return notFound_VertexTo 4.
else outdegree <int> 1. return notFound_VertexFrom isMarked <boolean> End InsertEdge End GraphNode Delete Edge from Digraph <ErrorCode> DeleteEdge (val VertexFrom <VertexType>, val VertexTo <VertexType>) Deletes an existing edge in the digraph. return notFound_Edge GraphNode 2. else vertex <VertexType> // (key field) 1.
return notFound_VertexTo adjVertex<List of< VertexType >> 4. else indegree <int> 1. return notFound_VertexFrom outdegree <int> End DeleteEdge isMarked <boolean> End GraphNode Graph Traversal Depth-first traversal: analogous to preorder traversal of an oredered tree. Breadth-first traversal: analogous to level-by-level traversal of an ordered tree.
Depth-first traversal Breadth-first traversal Depth-first traversal <void> DepthFirst (ref <void> Operation ( ref Data <DataType>)) Traverses the digraph in depth-first order. Depth-first traversal <void> DepthFirst (ref <void> Operation ( ref Data <DataType>)) 1. recursiveTraverse (v, Operation) End DepthFirst Depth-first traversal <void> recursiveTraverse (ref v <VertexType>, ref <void> Operation ( ref Data <DataType>) ) Traverses the digraph in depth-first order. Depth-first traversal <void> recursiveTraverse(ref v <VertexType>, ref <void> Operation ( ref Data <DataType>) ) 1.
recursiveTraverse (w, Operation) End Traverse Breadth-first traversal <void> BreadthFirst (ref <void> Operation ( ref Data <DataType>) ) Traverses the digraph in breadth-first order. loop (NOT queueObj .EnQueue(x) End BreadthFirst Topological Order A topological order for G, a directed graph with no cycles, is a sequential listing of all the vertices in G such that, for all vertices v, w G, if there is an edge from v to w, then v precedes w in the sequential listing. Topological Order Topological Order Applications of Topological Order Topological order is used for: Courses available at a university, • Vertices: course. • Edges: (v,w), v is a prerequisite for w.
• A topological order is a listing of all the courses such that all perequisites for a course appear before it does. A glossary of technical terms: no term is used in a definition before it is itself defined. The topics in the textbook. Topological Order <void> DepthTopoSort (ref TopologicalOrder <List>) Traverses the digraph in depth-first order and made a list of topological order of digraph's vertices.
Idea: • Starts by finding a vertex that has no successors and place it last in the list. • Repeatedly add vertices to the beginning of the list. • By recursion, places all the successors of a vertex into the topological order. • Then, place the vertex itself in a position before any of its successors.
Topological Order Topological Order <void> DepthTopoSort (ref TopologicalOrder <List>) 1. recursiveDepthTopoSort(v, TopologicalOrder) End DepthTopoSort Topological Order <void> recursiveDepthTopoSort (val v <VertexType>, ref TopologicalOrder <List>) Idea: • Performs the recursion, based on the outline for the general function traverse. • First, places all the successors of v into their positions in the topological order. • Then, places v into the order.
Topological Order <void> recursiveDepthTopoSort (val v <VertexType>, ref TopologicalOrder <List>) 1.Insert(0, v) End recursiveDepthTopoSort Topological Order <void> BreadthTopoSort (ref TopologicalOrder <List>) Traverses the digraph in depth-first order and made a list of topological order of digraph's vertices. Idea: • Starts by finding the vertices that are not successors of any other vertex. • Places these vertices into a queue of vertices to be visited. • As each vertex is visited, it is removed from the queue and placed in the next available position in the topological order (starting at the beginning).
• Reduces the indegree of its successors by 1. • The vertex having the zero value indegree is ready to processed and is places into the queue. Topological Order <void> BreadthTopoSort (ref TopologicalOrder <List>) 1. loop (NOT queueObj.
decrease the indegree of w by 1 2.EnQueue(w) End BreadthTopoSort Shortest Paths • Given a directed graph in which each edge has a nonnegative weight. • Find a path of least total weight from a given vertex, called the source, to every other vertex in the graph. • A greedy algorithm of Shortest Paths: Dijkstra's algorithm (1959). Dijkstra's algorithm Let tree is the subgraph contains the shotest paths from the source vertex to all other vertices.
At first, add the source vertex to the tree. Loop until all vertices are in the tree: • Consider the adjacent vertices of the vertices already in the tree. • Examine all the paths from those adjacent vertices to the source vertex. • Select the shortest path and insert the corresponding adjacent vertex into the tree.
Dijkstra's algorithm in detail • S: Set of vertices whose closest distances to the source are known. • Add one vertex to S at each stage. • For each vertex v, maintain the distance from the source to v, along a path all of whose vertices are in S, except possibly the last one. • To determine what vertex to add to S at each step, apply the greedy criterion of choosing the vertex v with the smallest distance.
• Update distance from the source for all w not in S, if the path through v and then directly to w is shorter than the previously recorded distance to w. Dijkstra's algorithm Dijkstra's algorithm