dfs.java

import java.util.*;

public class dfs {

	static class Node{
		int id;
		static int lastid = 0;
		{
			this.id = lastid++;
		}
		Node parent = null;
		boolean visited = false;
		HashMap<Node, Integer> connections = new HashMap<>();
		public void connect(Node n, int cost){
			if(cost == 0 || n == this)
				return;
			Integer current = this.connections.getOrDefault(n, 0);
			this.connections.put(n, current + cost);
		}


		@Override
		public String toString() {
//			StringBuilder sb = new StringBuilder("Node "+this.id + ": ");
//			this.connections.entrySet().forEach( (Map.Entry<Node, Integer> e)->{
//				sb.append("\n")
//					.append(e.getKey().id)
//					.append(" : ")
//					.append(e.getValue());
//			});
//			return sb.toString();
			return Integer.toString(this.id);
		}

	}

	public void run(int[][] matrix){
		Node[] nodes = new Node[matrix.length];

		for (int i = 0; i < matrix.length; i++) {
			nodes[i] = new Node();
		}

		for (int x = 0; x < matrix.length; x++) {
			for (int y = 0; y < matrix[x].length; y++) {
				nodes[x].connect(nodes[y], matrix[x][y]);
			}
		}

		Node startNode = nodes[1];
		double[] traversed = traverseDFS(startNode);
		System.out.println(Arrays.toString(traversed));
	}

	public static double[] traverseDFS(Node startNode){

		Stack<Node> stack = new Stack<>();
		stack.push(startNode);

		int iters = 0;
		HashSet<Node> nodeSet = new HashSet<>();

		while(!stack.empty()){
			if(iters++ >= 1000)
				throw new RuntimeException("Too many iterations");
			Node v = stack.pop();

			if(v.visited) continue;

			v.visited = true;
			nodeSet.add(v);

			for(Node w : v.connections.keySet()) {
				if(w==v || v.connections.get(w) == 0 || w.parent != null || w.visited) continue;
				stack.push(w);
				w.parent = v;
			}
		}

//		return nodeSet.toArray(new Node[nodeSet.size()]);
		return nodeSet.stream().map(node -> node.id).mapToDouble(Integer::doubleValue).toArray();
	}

	public static void main (String[] args) {
		int NODES = 50;
		int[][] matrix = new int[NODES][NODES];
		Random r = new Random(System.currentTimeMillis());
		for (int x = 0; x < matrix.length; x++) {
			for (int y = 0; y < matrix[x].length; y++) {
				matrix[x][y] = r.nextDouble() <= 0.8 ? 1 : 0;
			}
		}
		new dfs().run(matrix);
	}
}