December 02, 2019
Amitraj
Adjacency List
1. Adjacency list is another representation of graphs.
2. It is a collection of unordered list, used to represent a finite graphs.
3. Each list describes the set of neighbors of a vertex in the graph.
4. Adjacency list requires less amount of memory.
5. For every vertex, adjacency list stores a list of vertices, which are adjacent to the current one.
6. In adjacency list, an array of linked list is used. Size of the array is equal to the number of vertices.
7. In adjacency list, an entry array[i] represents the linked list of vertices adjacent to the ith vertex.
8. Adjacency list allows to store the graph in more compact form than adjacency matrix.
9. It allows to get the list of adjacent vertices in O(1) time.
Disadvantages of Adjacency List
-> It is not easy for adding or removing an edge to/from adjacent list.
-> It does not allow to make an efficient implementation, if dynamically change of vertices number is required.
NOTE:
Vertex: Each node of the graph is represented as a vertex.
Edge: It represents a path between two vertices or a line between two vertices.
Path: It represents a sequence of edges between the two vertices.
Adjacency: If two nodes or vertices are connected to each other through an edge, it is said to be an adjacency
1. Adjacency list is another representation of graphs.
2. It is a collection of unordered list, used to represent a finite graphs.
3. Each list describes the set of neighbors of a vertex in the graph.
4. Adjacency list requires less amount of memory.
5. For every vertex, adjacency list stores a list of vertices, which are adjacent to the current one.
6. In adjacency list, an array of linked list is used. Size of the array is equal to the number of vertices.
7. In adjacency list, an entry array[i] represents the linked list of vertices adjacent to the ith vertex.
8. Adjacency list allows to store the graph in more compact form than adjacency matrix.
9. It allows to get the list of adjacent vertices in O(1) time.
Disadvantages of Adjacency List
-> It is not easy for adding or removing an edge to/from adjacent list.
-> It does not allow to make an efficient implementation, if dynamically change of vertices number is required.
NOTE:
Vertex: Each node of the graph is represented as a vertex.
Edge: It represents a path between two vertices or a line between two vertices.
Path: It represents a sequence of edges between the two vertices.
Adjacency: If two nodes or vertices are connected to each other through an edge, it is said to be an adjacency
