Re: Graph Problem

On 1 Maj, 18:24, spineybabb...@xxxxxxxxx wrote:
Hi,
This came while i was writing a networking program. Suppose you have a
Graph G, and you are given a set of vertices. What I need to find is
minimum set of edges which connects all those edges ( assume the graph
is unweighted). By connection among edges i mean there should be  some
path form one vertex to the other.

I think this can be done by finding shortest path between every two
vertices but that is way too inefficient. I researched a bit but
couldn't find anything that useful. Anyone with any idea?

Thanks in advance!

Indeed it sounds like you want a minimum spanning tree. But you say
that the edges have no weighting. This implies that any spanning tree
will be minimum, since any spanning tree has V-1 egdes.

In the weighted case, look up Kruskal's algorithm.
.

Relevant Pages

  • Re: Graph Algorithms
    ... compute a spanning tree and then sort the tree. ... Some advanced compiler books ... compiler optimizations do a lot of graph manipulations. ... Kruskal and Prim are Spanning Tree algorithms. ...
    (comp.lang.tcl)
  • Re: Graph Algorithms
    ... compute a spanning tree and then sort the tree. ... Some advanced compiler books ... compiler optimizations do a lot of graph manipulations. ... Kruskal and Prim are Spanning Tree algorithms. ...
    (comp.lang.tcl)
  • Re: A statement about polynomial time solvability
    ... > Consider the minimum spanning tree problem on a graph with n vertices. ... OTOH, if you're looking for a k-coloring of G, you get a k-coloring of ...
    (sci.math)
  • Graph Problem
    ... This came while i was writing a networking program. ... Graph G, and you are given a set of vertices. ... I think this can be done by finding shortest path between every two ...
    (comp.theory)
  • Re: Graph theory
    ... > If I was to generalise? ... If N is the number of nodes in your graph, then any spanning tree will ... contain exactly N-1 edges. ...
    (sci.math)