Compare adjacency matrix and adjacency list for graph representation. How you choose which presentation to use depending on task and graph?

Both adjacency matrix and adjacency list are used to represent graphs in computer science.

Adjacency Matrix:
- An adjacency matrix is a 2D array where the rows and columns represent vertices in a graph.
- If there is an edge between two vertices, then the corresponding cell in the matrix is marked with a 1, otherwise it is marked with a 0.
- For undirected graphs, the matrix is symmetric along the diagonal.

Adjacency List:
- An adjacency list is a collection of linked lists or arrays where each vertex has a list of its neighboring vertices.
- Each list contains all the vertices adjacent to a particular vertex.
- For directed graphs, the list is not necessarily symmetric.

Choosing between the two representations depends on the task and the graph. Here are some guidelines:

Adjacency Matrix:
- Good for dense graphs with many edges.
- Provides constant time access to edges.
- Takes up more space than adjacency lists, especially for sparse graphs.
- Slower for adding or removing nodes or edges.

Adjacency List:
- Good for sparse graphs with fewer edges.
- Takes less space than an adjacency matrix, especially for sparse graphs.
- Faster for adding or removing nodes or edges.
- Slower for accessing edges, as it requires traversing through the list.

In summary, if the graph is dense, use an adjacency matrix. If the graph is sparse, use an adjacency list. If the task involves frequently adding or removing nodes or edges, use an adjacency list. If the task involves frequently accessing edges, use an adjacency matrix.