CODEWITHSUNDEEP
algorithmdepth-first-search
elias rizik
elias rizik

Reputation: 263

Find spanning tree that specific v has k degrees

can someone explain for me how to solve it i know that we should use DFS but i cant understand what we do after that.

input : undirected graph G and specific v that belong to the G
output : spanning tree that v has k degree

Upvotes: 1

Views: 854

Answers (3)

Petar Petrovic
Petar Petrovic

Reputation: 414

I will suggest the following way. Here I assume G is connected. First remove v from the graph, find spanning tree for each of the remaining component.

Now you may have a single spanning tree or a forest depending on the graph, you can add back v and use the edges to connecting v and each of the spanning tree.

Then you will have a spanning tree of G, and there will be three cases.

case 1: degree v > k, in this case, the task is impossible

case 2: degree v = k, you have the answer.

case 3: degree v < k, then you just add unused edges of v. Each time you add an edge you will create a cycle, then you can just choose an edge which does not touch v and remove it. You keep adding edges until you have your answer or all edges run out. However, I cannot think of a fast way to query a cycle besides doing bfs/dfs.

Update: There is a faster way for case 3 by Matt, after connecting v to k appropriate neighbors, use Kruskal's or Prim's algorithm to fill in the rest of the spanning tree, starting with the edges from v that you already have.

Upvotes: 3

Sandipan Dey
Sandipan Dey

Reputation: 23129

We can think this way too:

  1. For the given vertex v among all the neighbor v_i s.t. (v,v_i) in E(G) pick k edges with the smallest weights w(v,v_i), we need O(d*lg(d)) time where deg(v)=d >= k. Add these edges to the spanning tree edge set S. We have to add these edges to S anyway to ensure that the constraint holds.

  2. Remove vertex v from the graph G along with all edges incident on v. Now run Prim/Kruskal on the graph G \ {v} starting with the edge set S, the algorithm itself will add edges ensuring the acyclic and minimum properties. This will run in O(m*lg(n)).

Assuming d small step 1 & 2 runs in O(m*lg(n)).

Upvotes: 0

Sumeet
Sumeet

Reputation: 8292

Here is an algorithm that I am providing, but its pretty much brute force.

Condition for such tree to exist: if the degree of v < k, then such tree does not exist.

else follow the algorithm as:

Pick k vertices out of all the adjacent vertices of v,

1.mark all adjacent vertices of v as VISITED.

2.From each of those adjacent vertices , call DFS and the spanning tree grows.

3.After all DFS is complete,if all vertices of graph G are marked VISITED, then we
have our spanning tree, if a single vertex or more are left UNVISITED, then the 
4.pick another set of k vertices.

if v has X as degree and X > k, then step 4 has to be repeated XCk(X choose k) times in the worst case.

Upvotes: 0

Related Questions