ivan.cu wrote:Help please!!!
Some one can give me test cases such not work for the following greedy algorithm:
Code: Select all
1. Select not visit node whit max degree (N), put guard on it and count.
2. Visit all adjacent junctions and street.
3. Decrease degree for junctions adjacent to all junctions adjacent to N.
4. go to 1 if remain junctions unvisited.
if exist unvisited street print -1
else print guards
Thank in advance
ivan
It fails for certain types of graphs that are almost regular, because on some graphs, more than one node will have max degree.
consider this:
Code: Select all
10 10
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 0
Probably your algorithm will visit 0 first, then delete edges, but there are now many nodes with max degree 2, you don't know which one to pick.
If you pick any odd numbered nodes, your algorithm will output wrong answer. The way to fix it is to fix your step 4. Instead of picking any node with largest degree to visit, why don't you just put a guard on a unvisited node adjacent to a neighbor of the node where you have already put a guard.