Minimum Spanning Tree (MST)

The minimum spanning tree is the “best” tree one can iden­tify in a given graph with edge weights. Recall that edge weights represent some “cost” of communicating on that edge. The cost may be delay or expense in terms of real dollars to use the link.

The MST problem is to find a set of edges with a total minimum cost so that the nodes in the graph remain con­nected. A greedy algorithm can be used to find this set of edges, called MSTE. The algorithm starts with one edge with minimum weight. Then it finds an edge “e,” the best candidate that has not yet been considered and adds it if it is feasible. An edge can only be added to this set if it does not create a cycle in the graph with the same set of nodes as the original graph and set ofedges MSTE. MSTE is com­plete when it contains N — 1 edges in an N node graph. It is known that a greedy algorithm indeed finds an MSTE.

Several algorithms are available to find an MST. We will consider two algorithms here based on the greedy ap­proach, but their complexities may differ slightly.

Kruskal Algorithm. This algorithm essentially requires all edges to be sorted, shortest first. Then the edges are included in set MSTE, one at a time, in an order such that the edges do not form a cycle. The test for forming a cy­cle can be efficiently made by maintaining a proper data structure of edges included thus far. The complexity of sort­ing is O(M log M)), the test is of complexity O(M + N) as suggested by Tarjan (12). As the process terminates once the set MSTE includes N — 1 edges, one may not have to sort all edges (the first few may be sufficient). This result be achieved by putting all edge weights in a heap that can be created in O(M) time. An edge with the smallest weight can be removed from the heap in O(log M) time. If k edges have to be considered to select N — 1 edges for inclusion in MSTE, then the complexity of the selection process is O(M + klog M). Therefore, the total complexity is O(M + N + k log M). An example of execution of Kruskal’s algorithm is shown in Fig. 12. Each edge is labeled with its weight and its number (shown in brackets). In each pass, the selected edge and the included nodes are shown in the table.

Prim’s Algorithm. For a dense network, when M is of O(N2), an alternative method to find an MST is from Prim (13). This algorithm maintains a tree and adds additional nodes to the tree using minimum cost edges. For this pur-

Krushal Algorithm Figure 12. Kruskal’s MST algorithm.

pose, the minimum distance of each node that is out of the tree is maintained from the tree nodes. Each time a new node is added, the distances ofnodes that are not yet in the tree from the tree change. Therefore, these distances need to be revised. In fact, the distances of the nodes outside the partial tree from the newly inserted node only need to be considered as that is the only change in the tree. The al­gorithm has a complexity of O(N2). We need N passes, one each to select N nodes to be included in the tree. Each time we need to find a node with minimum distance (this is an O(N) procedure) and update distances of all other nodes after considering the new node (another O(N) procedure if the distances are maintained in the adjacency list). Both O(N) procedures can be performed in O(d) if the maximum degree of each node is only d because we only need to con­sider d neighbors of the new node introduced in the tree. Thus, the overall complexity of the procedure is O(dN).

Constrained MST. The MST computation may be con­strained using some optimality criteria or requirements. In the case of constrained MST computation, the Selection of edges is constrained using appropriate selection criteria consistent with the specified constraints. For example, in the previous algorithm, it is assumed that the weight of an edge is the only criterion. But the new constraint may be that no node can have more than a certain number ofedges connected to it. In that case, the algorithm may have to de­cide on a selectable candidate differently. If a node already has a given number of edges originating from it, then no more edges connected to that node may become part of the solution.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *