Log In
0 votes
Time taken in adding/removing an edge to/from adjacent list ?
in Algorithms 138 views
O(n). time when All elemets related to one edge.
In case of adjacency list we have to travel the linked list so it takes O(n) and in case of adjacency matrix it it takes O(1) becoz we just have to put 0 in the cell of corresponding matrix
I think to remove an edge will take O(n) nd adding an edge will take constant time.
where n is no of edges in graph originally.
Is somewhere time is related to degree of a particular vertex ?
yes saurabh if u add in starting then yes take constant time.

we can insert new node at start node or last node.

if we insert at first node only one pointer variable is changed so time complexity is o(1),but at last we can traverse the linked list so time complexity is o(n).

in case of deletion we exactly dont know where the required node present so time complexity is o(n)

Please log in or register to answer this question.

Related questions

1 vote
2 answers
Which of the following statement is true? For a directed graph, the absence of back edges in a DFS tree can have cycle. If all edge in a graph have distinct weight then the shortest path between two vertices is unique. The depth of any DFS (Depth First Search) tree rooted at a vertex is atleast as depth of any BFS tree rooted at the same vertex. Both (a) and (c)
asked Jan 4, 2019 in Algorithms Abhishek Kumar 38 846 views
0 votes
0 answers
If the DFS finishing time f[u] < f[v] for two vertices u and v in a directed graph G, and u and v are in the same DFS tree in the DFS forest, then u is an ancestor of v in the depth first tree ? True /False can anyone explain it ?
asked Jan 2, 2019 in Algorithms Prince Sindhiya 242 views
0 votes
0 answers
According To Me Answer Should Be 6… Anyone Please Try Once!!! Given Is 5 With No Explaination !!!! like 11-12-12 then for second square 4 times 13 so c(4,2) any two of then lead to me @ answer @6.
asked Dec 26, 2018 in Algorithms CHïntän ÞäTël 126 views
0 votes
0 answers
Dijktra Algo selects shortest path having maximum number of shortest edges, for non adjacent nodes. Is it true? Please justify..
asked Nov 25, 2018 in Algorithms Shamim Ahmed 153 views