GenericVisitOfAConnectedComponent(G,w) { D = { w } // a new set while (not (empty(D))) { choose(D,v) // pick a v in D and remove it from D if (not (marked(v))) { mark(v) print(v) D = union(D, AdjSet(G,v)) } } } Example: D = {A} choose A AdjSet(A) = {B, D} D = {B, D} choose B AdjSet(B) = {C} D = {C, D} choose C AdjSet(C) = {D,E} D = {D, E} choose E AdjSet(E) = {C*} D = {D, C*} choose C* IGNORE C* D = {D} choose D AdjSet(D) = {} D = {} GenericVisitOfAGraph(G) { for each w in Vertices(G) { if (not (marked(w))) { // From now on, same code as for one connected component D = { w } // a new set while (not (empty(D))) { choose(D,v) // pick a v in D and remove it from D if (not (marked(v))) { mark(v) print(v) D = union(D, AdjSet(G,v)) } } } } } How many times is the while loop executed? At each iteration I remove from D one element. Thus, it is the number of elements ever removed from D. Thus, it is the number of elements ever added to D. How many times do I add an element to D? 1. once per w in V ==> #V 2. (at most) once per element of AdjSet(v) per v in V (the second "per" is justified by the "if (not (marked(v)))": I only compute and add the AdjSet(v) if this is the only time that v is unmarked) (the "at most" is because the union can detect that an element is already in and avoid choosing it twice) ==> \Sigma_v | AdjSet(v) | = #E (or 2 #E if the graph is undirected) Answer: #V + #E COMPLEXITY ANALYSIS: 1 Vertices(G) #V marked(w) O(1) #V { w } #V+#E empty(D) #V+#E choose(v) #V+#E marked(v) O(1) #V mark(v) O(1) #V print(v) O(1) #V AdjSet(v) #V union ###### 1 case: adjacency matrix for the graph bitvector for AdjSet bitvector for D ###### 1 Vertices(G) O(1) O(1) #V marked(w) O(1) O(#V) #V { w } O(#V) O(#V^2) #V+#E empty(D) O(#V) O(#V^2 + #V #E) #V+#E choose(v) O(#V) O(#V^2 + #V #E) #V+#E marked(v) O(1) O(#V+#E) #V mark(v) O(1) O(#V) #V print(v) O(1) O(#V) #V AdjSet(v) O(1) O(#V) #V union O(#V) O(#V^2) ===================== O(#V#E + #V^2) ###### 2 case: adjacency matrix for the graph bitvector for AdjSet list for D ###### 1 Vertices(G) O(1) O(1) #V marked(w) O(1) O(#V) #V { w } O(1) O(#V) #V+#E empty(D) O(1) O(#V + #E) #V+#E choose(v) O(1) O(#V + #E) #V+#E marked(v) O(1) O(#V + #E) #V mark(v) O(1) O(#V) #V print(v) O(1) O(#V) #V AdjSet(v) O(1) O(#V) #V union O(#D * #AdjSet(v)) =O(#V * #V) O(#V^3) ===================== O(#E + #V^3) ###### 3 case: adjacency matrix for the graph bitvector for AdjSet list with duplicates for D ###### 1 Vertices(G) O(1) O(1) #V marked(w) O(1) O(#V) #V { w } O(1) O(#V) #V+#E empty(D) O(1) O(#V + #E) #V+#E choose(v) O(1) O(#V + #E) #V+#E marked(v) O(1) O(#V + #E) #V mark(v) O(1) O(#V) #V print(v) O(1) O(#V) #V AdjSet(v) O(1) O(#V) #V union O(#AdjSet(v)) O(#E = \Sigma_v |AdjSet(v)|) ===================== O(#E + #V) ##### 4 case: adjacency set for the graph vector for AdjSet sorted list without duplicates for D ###### 1 Vertices(G) O(1) O(1) #V marked(w) O(1) O(#V) #V { w } O(1) O(#V) #V+#E empty(D) O(1) O(#V + #E) #V+#E choose(v) O(1) O(#V + #E) #V+#E marked(v) O(1) O(#V+#E) #V mark(v) O(1) O(#V) #V print(v) O(1) O(#V) #V AdjSet(v) O(1) O(#V) #V union O(max{#AdjSet(v),#D) =O(max{#V,#V}) O(#V^2) ===================== O(#E + #V^2) ##### BFS ###### 5 case: adjacency list for the graph list for AdjSet queue for D ###### 1 Vertices(G) O(1) O(1) #V marked(w) O(1) O(#V) #V { w } O(1) O(#V) #V+#E empty(D) O(1) O(#V + #E) #V+#E choose(v) O(1) O(#V + #E) choose = deque #V+#E marked(v) O(1) O(#V+#E) #V mark(v) O(1) O(#V) #V print(v) O(1) O(#V) #V AdjSet(v) O(1) O(#V) #V union O(#AdjSet(v)) O(#E) union = for each w in AdjSet(v) enqueue(w) ===================== O(#E + #V) ##### DFS ###### 6 case: adjacency list for the graph list for AdjSet stack for D ###### 1 Vertices(G) O(1) O(1) #V marked(w) O(1) O(#V) #V { w } O(1) O(#V) #V+#E empty(D) O(1) O(#V + #E) #V+#E choose(v) O(1) O(#V + #E) choose = pop #V+#E marked(v) O(1) O(#V+#E) #V mark(v) O(1) O(#V) #V print(v) O(1) O(#V) #V AdjSet(v) O(1) O(#V) #V union O(#AdjSet(v)) O(#E) union = for each w in AdjSet(v) push(w) ===================== O(#E + #V)