2
$\begingroup$

INPUT: weighted undirected graph in the form of adjacency list

OUTPUT: adjacency list without the edge e

Naive approach is:

for(int i = 0; i < adj.get(e.s).size(); i++) { // loop through adjacent of s
  if(adj.get(e.s).get(i).v == e.t) {           // find t and remove it
    adj.get(e.s).remove(i); 
    break;
  }
}
for(int i = 0; i < adj.get(e.t).size(); i++) { // loop through adjacent of t
  if(adj.get(e.t).get(i).v == e.s) {           // find s and remove it
    adj.get(e.t).remove(i); 
    break;
  }
}
O(k) - k is number of adjacent vertices

A faster approach is to use adjacencyMatrix but my algorithm has alot of traversals involved and looping through each dimension in the adjMat costs more despite a O(1) edge removal.

How can I speed up removing an edge? (used in generating a MST (kruskal))

$\endgroup$
  • 2
    $\begingroup$ You can't, in general (if you're just given an adjacency list) do better. Perhaps you need to augment your data structures to make removing an edge easier (if you really need to, since "removing an edge" is not part of Kruskal's algorithm). $\endgroup$ – Tom van der Zanden Oct 14 '15 at 8:03
  • $\begingroup$ You can use a hash map or a Binary Search Tree. In my bsc Thesis I needed such an operation and BSTs worked fine(better in fact than Hash tables). BTW, Are you in each iteration, looping through all remaining edges and selecting the minimum cost edge? Like Tom said, Kruskal is not (best) implemented this way. $\endgroup$ – jjohn Oct 14 '15 at 13:54
  • $\begingroup$ @jjohn my initial implementation was to build an adjList and adding edges into a max heap, and to poll and remove whilst detecting no cycles. In the end ive implemented the other way around to poll minimum weight edge and build the graph with an adjacent matrix whilst using a ufds to detect cycles and after that translate the adjmat to an adjlist (so this question can be closed but im nt sure how to do that :P). But to be back on topic a bst per vertex for an adjacency list does seem like a good idea (sub linear search, and tree traversal to loop through all). Thanks! $\endgroup$ – iluvAS Oct 14 '15 at 14:50
1
$\begingroup$

I didn't realize what is your problem with Kruskal algorithm. To me, a usual Kruskal has time complexity $O(E \ log E)$ that $E$ is the number of edges in a graph, and I don't have any difficulty to ignore those edges which make a cycle.

To answer you question, all adjacency lists, maintaining adjacent vertices, can be sorted in an ascending order. Then, you can find the position of each adjacent node with $O(log N)$, where $N$ is the number of vertices.

You should also define two one-dimensional arrays, $nex$ and $pre$ for each adjacency list, where $nex$ maintains the position of next vertex in an adjacency list, and $pre$ holds the previous position.

When edge $e = (a, b)$ is about to be removed, the position of $b$ in the adjacency list of $a$ can be found with $O (log \ N)$.

Then, do two following steps to remove $a \to b$:

  • $nex [ \ pre [b] \ ] = nex [b]$
  • $pre [ \ nex [b] \ ] = pre [b]$

Do it also in the adjacency list of $b$ to remove $b \to a$.

If you want to traverse in an adjacency list, the next index can be reached by the means of $nex$ array.

To traverse an adjacency list from the beginning a random value, as a dump, can be utilized since the first node might be removed.

$\endgroup$
  • $\begingroup$ If the adjacency list is implemented by a linked list per node as usual, then removing such an edge changes to O(n) instead of O(log n). So, it depends. $\endgroup$ – jonaprieto Sep 23 '18 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.