Wykrywanie mostów w grafie (DFS + funkcja low) - java

0

Napisałem algorytm DFS z funkcją low, który powinien znajdować mosty w grafie, niestety wypisuje mi jakieś bzdury. Siedzę nad tym już od jakiegoś czasu i nie wiem co jest źle :( . Proszę o pomoc.

 

import java.util.HashMap;
import java.util.Vector;


public class DFS
{
	private HashMap <Integer, Integer> orderMap; // klucz to nr Węzła
	private Graph graph;
	private int cnt = 0; // kolejność
	private int low; // minimalny nr węzła do którego można się cofnąć za pomocą krawędzi powrotnej
	
	/***********************************************************/
	
	public DFS(Graph g)
	{
		orderMap = new HashMap <Integer, Integer>();
		graph = g;
	}
	
	/***********************************************************/
	
	public int dfs_bridges(Node v, Node w)
	{	
		orderMap.put(w.number, cnt);
		low = cnt++;
		
		for(int i=0; i<w.adjacencyList.size(); i++)
		{
			Node t = w.adjacencyList.get(i);
			
			if(orderMap.get(t.number) == null)
			{
				int tmp = dfs_bridges(w, t);
				
				if(orderMap.get(t.number) == tmp)
					System.out.println(w.number+"--"+t.number+"jest mostem");
				else if( tmp<low )
					low = tmp;
			}
			else if(t.number != v.number)
			{
				low = Math.min(low,orderMap.get(w.number));
			}
		}
		
		return low;
	}
	
	/***********************************************************/
	
	public void printData()
	{
		for(int i=0; i<graph.getNodesList().size(); i++)
		{
			Node node = graph.getNodesList().get(i);
			
			System.out.println(node.number +"-"+ orderMap.get(node.number)+"-"+lowMap.get(node.number));
		}
	}
	
	/***********************************************************/
}


0

To napisz swój od 0.

1 użytkowników online, w tym zalogowanych: 0, gości: 1