Alkusolmu

gistfile1.java

package harjoitus9;

import java.util.Arrays;
import java.util.List;

/**
 * @author Kari
 */
public class Alkusolmu {
	static class Solmu {
		public List<Integer> vieruslista;

		public Solmu(Integer... vierus) {
			vieruslista = Arrays.asList(vierus);
		}
	}

	static class Etsijä {
		final Solmu [] solmut;
		final boolean [] tarkistettu;
		int alkusolmu = -1;

		public Etsijä(Solmu[] solmut) {
			this.solmut = solmut;
			this.tarkistettu = new boolean[solmut.length];
		}

		public int etsiAlkusolmu() {
			for (int i = 0; i < tarkistettu.length; i++) {
				if (!tarkistettu[i]) {
					alkusolmu = i;
					tarkista(i);
				}
			}

      // TODO: Aloitetaan uusi syvyyshaku alkusolmuehdokkaasta ja tsekataan kävikö se kaikissa solmuissa
			return alkusolmu;
		}

		public void tarkista(int i) {
			tarkistettu[i] = true;

			// merkataan käydyksi
			for (int v : solmut[i].vieruslista) {
				if (!tarkistettu[v]) {
					tarkista(v);
				}
			}
		}
	}

	public static void main(String [] args) {
		Solmu [] solmut = {
				new Solmu(3),
				new Solmu(),
				new Solmu(1),
				new Solmu(4, 5),
				new Solmu(1, 6),
				new Solmu(6),
				new Solmu(7),
				new Solmu(2),
				new Solmu(0),
				new Solmu(8, 10),
				new Solmu(),
		};

		Etsijä e = new Etsijä(solmut);
		System.out.println(e.etsiAlkusolmu());
	}
}