Suppose that an undirected graph is represented with the array adjacency list representation. Write an algorithm to remove the an edge from G. What is the time complexity of the algorithm.
Adjacency List Representation: An adjacency list representation of a graph G= {V, E} consists of an array of adjacency list denoted by adj of V list. For each vertex U e V, adj[U] consists of all vertices adjacent to U in the graph G.
Consider the graph for undirected graph:-
The following is the adjacency list representation of graph is
Adj [1] = {2, 3, 5}
Adj [2] = {2, 4}
Adj [3] = {1, 4, 5}
Adj [4] = {2, 3, 5}
Adj [5] = {1, 3, 4}
adjacency matrix representation of a graph G= (V, E) is a matrix A(aij)
such that
aij = { 1 if edge (i,j) belongs to E O otherwise
The Adjacency matrix for the graph of above is given below:-
Adjacency matrix of an undirected graph is symmetric on main diagonal. When directions are not marked on the edges, then the graph is called an undirected graph.
Consider a graph G= (V,E). We wish to find out the shortest path from a single source vertex vEV, to every vertex vEV.
The single source shortest path algorithm is based on assumption that no edges have negative weights.
Now, we shall discuss about an algorithm in which we will remove an edge from the graph G.
And we can solve the path (shortest) algorithm which starts with a single source and finds shortest path to all vertices in the graph. This problem is helpful in finding distance between all pairs problem is mother of all shortest paths problems.
In this algorithm, we will represent the graph by adjacency matrix.
The weight of an edge (ij in an adjacency array representation as follow
___ ________ ____ ____ ______ ______ _________ _____ _______ _________.
____ ___ ________ ___ ____ ____ _________ ______ ___.
_______ ______ _________ _______ __________ ______ ________ _______ _______ ________ _______.
_________ __________ ______ ______ _______ _____ _________ ____.
____ ___ _________ ___ ___ ________.
____ ________ ___ _____ _____ ______ ________ ______ ________.
______ _____ ______ ______ ______.
___ _____ ___ ___ ___ ____.
_______ _______ _________ ____ _______ _____.
_________ _____ _____ ______ ___ ______.
______ ________ _______ _______ _____ ______.
_____ _________ ___ ____ ___ ______ _________ ___ __________.
___ ____ ___ ______ __________ ____ ________ ________ _________.
____ ___ _________ __________ ___ ______ ___ ______ ____.
_______ _______ ________ _____ ___ _______ ____ ____.
__________ ___ _____ ____ ___ _______ _______.
_____ ____ ____ _____ ___ ____ ____.
_________ __________ _______ ___ ________ ____ ___ _______ _____ ______ __________.
________ ____ ________ _______ _________ _______ _________ ______ ____ _______ ___ ________.
__________ _________ __________ _____ ______ __________ ______.
________ __________ _____ ________ _______ __________ ________ _____ ______ ____ ___ ___.
__________ _____ ___ _________ _______ _________ _________ _______ ____ ______ ________.
____ ___ _____ __________ ________ __________ ________ _____.
_________ ______ __________ __________ _____.
___ _____ ________ ______ ___ _________ ________ ______ __________.
______ ___ ______ ____ __________.
______ ___ ________ _____ ______ _______ __________ ________.
_________ _________ _____ _______ __________ ________ _________.
__________ _______ ___ _______ ________ _________ ____.
_________ ____ _________ ___ ________.
__________ _______ ________ _____ _____ __________.
__________ _________ _____ __________ ____ _________ _____ __________ _____ _______ ____.
____ _______ __________ _________ _________ ______ _____ _______ ________ _____ __________.
_____ ___ ______ ___ _____ ____ ________ __________ _____ _____.
_____ ___ ____ ____ __________ _________ _________ _________ _________ ______ ______ _____.
____ _________ __________ ____ _________ ___ __________.
_______ ______ ______ _________ ____ ______ ___ __________ ______ ____ _____ ___.
________ _________ _____ _________ ______ _____ ___ ____ _________.
_________ ______ ____ ______ _______.
__________ ______ ______ ______ _______ ___ ______ ___ __________ _________ _______.
___ ____ ____ _____ _____ __________ __________ __________ ______.
________ ________ _________ ________ ____ _______.
__________ ________ _____ ______ ____ _____ ____ ________ _______ ________ _________ ____.
_____ ______ _______ ____ _________ ___.
________ _________ ______ __________ ________ __________.
_______ ___ ___ ___ _______ ______ _______ _____ ____ __________ _____ ____.
___ ______ _______ ____ __________ ________.
________ _________ _____ __________ ______ ______.
________ ________ ______ ______ __________ ________ _______ ___.
____ __________ _____ _____ _____ _________ ___ _________.
_____ ______ _____ ____ ______.
_________ ________ _______ _______ _______ ____ ___ ___ ______ __________.
- Solved Assignments
- Study Notes
- Guess Papers
- Question Papers
✓ Unlock up to 60% of the answer
✓ No payment required