BRIEF RELETIONSHIP BETWEEN ADJACENCY MATRIX AND LIST.pptx

BRIEF RELETIONSHIP BETWEEN ADJACENCY MATRIX AND LIST

1. TOPIC NAME- BRIEF RELETIONSHIP BETWEEN ADJACENCY MATRIX AND LIST

2. In graph theory, an adjacency matrix is nothing but a square matrix utilized to describe a finite graph. The components of the matrix express whether the pairs of a finite set of vertices (also called nodes) are adjacent in the graph or not. In graph representation, the networks are expressed with the help of nodes and edges, where nodes are the vertices and edges are the finite set of ordered pairs . ADJENCY MATRIX

3. In graph theory and computer science an adjacency list is a collection of unordered lists used to represent a finite graph. Each unordered list within an adjacency list describes the set of neighbors of a particular vertex in the graph. This is one of several commonly used representations of graphs for use in computer programs. ADJACENCY LIST

4. PROPERTIES OF ADJACENCY MATRIX The vertex matrix is an array of numbers which is used to represent the information about the graph. Some of the properties of the graph correspond to the properties of the adjacency matrix, and vice versa.

5. PROPERTIES OF ADJACENCY LIST It is a finite graph. a particular vertex in the graph .

6. DIFFERENCES BETWEEN ADJACENCY MATRIX AND ADJACENCY LIST Operations Adjacency Matrix Adjacency List Storage Space This representation makes use of VxV matrix, so space required in worst case is O(|V| 2 ). In this representation, for every vertex we store its neighbours . In the worst case, if a graph is connected O(V) is required for a vertex and O(E) is required for storing neighbours corresponding to every vertex .Thus, overall space complexity is O(|V|+|E|). Adding a vertex In order to add a new vertex to VxV matrix the storage must be increases to (|V|+1) 2 . To achieve this we need to copy the whole matrix. Therefore the complexity is O(|V| 2 ). There are two pointers in adjacency list first points to the front node and the other one points to the rear node.Thus insertion of a vertex can be done directly in O(1) time. Adding an edge To add an edge say from i to j, matrix[i][j] = 1 which requires O(1) time. Similar to insertion of vertex here also two pointers are used pointing to the rear and front of the list. Thus, an edge can be inserted in O(1)time. Removing a vertex In order to remove a vertex from V*V matrix the storage must be decreased to |V| 2   from (|V|+1) 2 . To achieve this we need to copy the whole matrix. Therefore the complexity is O(|V| 2 ). In order to remove a vertex, we need to search for the vertex which will require O(|V|) time in worst case, after this we need to traverse the edges and in worst case it will require O(|E|) time.Hence , total time complexity is O(|V|+|E|).

7. APPLICATION OF ADJACENCY MATRIX The adjacency matrix is a matrix used to represent finite graphs. The values in the matrix show whether pairs of nodes are adjacent to each other in the graph structure. If the graph is undirected, then the adjacency matrix will be a symmetric one.

8. APPLICATION OF ADJACENCY LIST In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each unordered list within an adjacency list describes the set of neighbors of a particular vertex in the graph.

9. THE RELATIONSHIP BETWEEN ADJACENCY LIST AND ADJACENCY MATRIX If a graph has n number of vertices, then the adjacency matrix of that graph is n x n, and each entry of the matrix represents the number of edges from one vertex to another. An adjacency matrix is also called as connection matrix. Sometimes it is also called a Vertex matrix.

10. CONCLUSION Adjacency matrix is good for dense graphs. Adjecency lists is good for sparse graphs and also for changing the no of nodes.