Unit 5 GRAPH STRUCTURE Graph ADT Representations of graph Graph traversals DAG Topological ordering Greedy algorithm Dynamic programming shortest paths minimum spanning trees introduction to complexity classes and intractability 5 1 Graph ADT 5 1 1 Definition A graph can be defined as group of vertices and edges that are used to connect these vertices A graph can be seen as a cyclic tree where the vertices Nodes maintain any complex relationship among them instead of having parent child relationship A graph G can be defined as an ordered set G V E where V G represents the set of vertices and E G represents the set of edges which are used to connect these vertices A Graph G V E with 5 vertices A B C D E and six edges A B B C C E E D D B D A is shown in the following figure 5 1 2 Directed and Undirected Graph A graph can be directed or undirected However in an undirected graph edges are not associated with the directions with them An undirected graph is shown in the above figure since its edges are not attached with any of the directions If an edge exists between vertex A and B then the vertices can be traversed from B to A as well as A to B In a directed graph edges form an ordered pair Edges represent a specific path from some vertex A to another vertex B Node A is called initial node while node B is called terminal node A directed graph is shown in the following figure Path 5 1 3 Graph Terminology node V from the initial node U A path can be defined as the sequence of nodes that are followed in order to reach some terminal A path will be called as closed path if the initial node is same as terminal node A path will be If all the nodes of the graph are distinct with an exception V0 VN then such path P is called as A cycle can be defined as the path which has no repeated edges or vertices except the first Closed Path closed path if V0 VN Simple Path closed simple path Cycle and last vertices Connected Graph A connected graph is the one in which some path exists between every two vertices u v in V There are no isolated nodes in connected graph Complete Graph A complete graph is the one in which every node is connected with all other nodes A complete graph contain n n 1 2 edges where n is the number of nodes in the graph Weighted Graph In a weighted graph each edge is assigned with some data such as length or weight The weight of an edge e can be given as w e which must be a positive value indicating the cost of traversing the edge A digraph is a directed graph in which each edge of the graph is associated with some direction and the traversing can be done only in the specified direction An edge that is associated with the similar end points can be called as Loop If two nodes u and v are connected via an edge e then the nodes u and v are called as Digraph Loop Adjacent Nodes neighbours or adjacent nodes Degree of the Node degree 0 is called as isolated node Length of the graph A degree of a node is the number of edges that are connected with that node A node with Length of the path is the number of edges of the path n 1 Where n is the number of vertices in the path Indegree and outdegree of a graph The number of edges entering into the vertex is called Indegree vertex of graph The number of edges leaving from the vertex is called Outdegree vertex of graph Sequential representation In sequential representation there is a use of an adjacency matrix to represent the mapping between vertices and edges of the graph We can use an adjacency matrix to represent the undirected graph directed graph weighted directed graph and weighted undirected graph If adj i j w it means that there is an edge exists from vertex i to vertex j with weight w An entry Aij in the adjacency matrix representation of an undirected graph G will be 1 if an edge exists between Vi and Vj If an Undirected Graph G consists of n vertices then the adjacency matrix for that graph is n x n and the matrix A aij can be defined as aij 1 if there is a path exists from Vi to Vj aij 0 Otherwise It means that in an adjacency matrix 0 represents that there is no association exists between the nodes whereas 1 represents the existence of a path between two edges If there is no self loop present in the graph it means that the diagonal entries of the adjacency matrix will be 0 Now let s see the adjacency matrix representation of an undirected graph In the above figure an image shows the mapping among the vertices A B C D E and this mapping is represented by using the adjacency matrix There exist different adjacency matrices for the directed and undirected graph In a directed graph an entry Aij will be 1 only when there is an edge directed from Vi to Vj 5 1 4 Adjacency matrix for a directed graph In a directed graph edges represent a specific path from one vertex to another vertex Suppose a path exists from vertex A to another vertex B it means that node A is the initial node while node B is the terminal node Consider the below directed graph and try to construct the adjacency matrix of it In the above graph we can see there is no self loop so the diagonal entries of the adjacent matrix are 0 5 1 5 Adjacency matrix for a weighted directed graph It is similar to an adjacency matrix representation of a directed graph except that instead of using the 1 for the existence of a path here we have to use the weight associated with the edge The weights on the graph edges will be represented as the entries of the adjacency matrix We can understand it with the help of an example Consider the below graph and its adjacency matrix representation In the representation we can see that the weight associated with the edges is represented as the entries in the adjacency matrix In the above image we can see that the adjacency matrix representation of the weighted directed graph is different from other representations It is because in this representation the non zero values are replaced by the actual weight assigned to the edges Adjacency matrix is easier to implement and follow An adjacency matrix can be used when the graph is dense and a number of edges are large Though it is advantageous to use an adjacency matrix but it consumes more space Even if the graph is sparse the matrix still consumes the same space Adjacency list In this representation every vertex of the …