Now in matrix representation, we use an array of size nxn. We have n(n-1)/2 edges in a complete graph where n is the number of vertices. Sparse means we have very few edges and dense means many edges or an almost complete graph. Let me introduce you to two terms, sparse and dense. When we use the adjacency matrix and when the adjacency list Since the linked list has a time complexity O(n) for searching, the complexity for checking the existence of an edge is O(n). To save memory we have to sacrifice O(1) checking time here. Also iterating in an adjacency list is much faster than adjacency matrix. Memory usage of an adjacency list depends more on the number of edges than the number of nodes. int max_node=5 Īrr.push_back(make_pair(4,weight_from_0_to_4)) Advantages and disadvantages of adjacency list To make the adjacency list weighted, we will make a linked list of a pair and put node number and weight as pair in it. So, this way, the matrix represents an undirected graph. That means if we can go to 4, 3, 2, 5 from node 0 we can also come back from 4, 3, 2, 5 to 0. See, as 0 has 4, 3, 2, 5 in its list, indexes 4, 3, 2, and 5 also have 0 in their list. Following is an undirected version of this graph. If we insert v at index u, then we also have to insert u at index v. 2 has an edge with 1 (nodes 4,3,2,5 are adjacent to node 0).įor the undirected graph, we just need to do a bit of change in the logic. Index 1 has 3 in its list so 1 has an edge with 3. See, index 0 has 4, 3, 2, and 5 in its list which means 0 has an edge over all of them. The adjacency list for the graph is on the right side. The above operations will create a directed graph like the below, int max_node=5 Īn index of an adjacency list holds all the adjacent nodes of this node in its linked list/ vector. Below is an example in c++ that shows how we do it. Then we will insert/ push node 4 inside the 0th index of the array. Then say we need to represent an edge between node 0 and node 4. Then we will take an array of the linked lists/vectors of size 5+1=6. Suppose we have a graph where the maximum node is 5. Adjacency list uses an array of linked lists/vectors (in c++). Adjacency listĪnother way of storing a graph is to use an adjacency list. Also, lots of space remain unused in the adjacency matrix. In this case, we have to take a matrix of size 6圆 as our maximum is 6. Iterating for every node in the adjacency matrix is slow because in the array we can’t say which node exists and which is not. Another disadvantage is it will take O(n^2) time to add and delete a new node in the graph. So this approach will take more than 4 Megabytes of space for storing a graph with 1000 nodes. But a 2D matrix has O(n^2) space complexity. We have to use a 2D matrix to represent a matrix in programming. The major drawback of the adjacency matrix is the use of space. Also if we want to add an edge between two existing nodes it will take only O(1) time. We can easily check if there is an edge between node u and v and we can also get the weight of the edge. There are several advantages of the adjacency matrix. Advantages and disadvantages of the adjacency matrix If we have the undirected graph, our matrix will be symmetrical like below.įrom the above image if arr=1 then we can say arr is also 1.įor the weighted graph, we will put the weights instead of 1’s in the cell. Hence in the matrix, arr=1 where u=0 and v=1. Now we can see that we have a directed edge from 0 to 2. Look at the image above, we have a directed unweighted graph with 4 vertices and 4 edges. The below image is representing an adjacency matrix of the graph on the left. We can also make an undirected graph by making arr and arr non zero. We can make an adjacency matrix weighted by storing the weight in arr. Node: The shape of the adjacency matrix is n*n where n is the maximum number of nodes in the graph. Let’s consider an array arr then this array represents a matrix of size 10x10 where arr means an edge between u and v. Adjacency matrixĪ matrix is just a two-dimensional array in programming. We can easily represent a graph using the two following ways, Today, we will learn about graph representation in memory so that we can input a graph and perform our operation in it. Previously we’ve known about graphs and their types. Graph representation - adjacency matrix and adjacency list
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |