Sunday, September 18, 2011

Graphs - Depth First Search



package main.java.algo.datastructures.graphs;

import java.util.List;
import java.util.Stack;

public class DepthFirstSearch {

	public void doDFS(Graph g, GNode root) {

		GNode n = root;
		List<GNode> adjacents = null;
		
		//using a stack
		Stack<GNode> s = new Stack<GNode>();
		// in stack - we drill down the edge first - finish the legs before picking the siblings
		// in BFS - we use  Queue (linkedlist internally). Queue uses less memory as compared to a stack - because in stack - every level of recursion adds a new layer to the memory.
		
		s.push(n);
		
		while (!s.isEmpty()) {
			
			n = s.pop();
			if (n == null)
				continue;
			
			adjacents = g.getAdjacents(n); // get all nodes that are linked to n. This method getAdjacents() is implemented in my Graph class
			
			for (GNode node : adjacents) {
				
				// In a graph pick an element only ones, to avoid cycles and loops
				if (node.state == State.UNVISTED) {
					
					// once picked, mark as visited and put in stack for processing
					node.state = State.VISITED;
					s.push(node);
					
					//if we want to process and edge
					processEdge(n, node);
					
				}
			}
			// we have picked all the connecting edges of a vertex n. Now if we want to process a vertex.
			// now we are done with that vertex, we mark it as processed.
			processVertex(n);
			n.state = State.PROCESSED;
		}
	}

	// this can be used to process edge - like check if 2 nodes are connected
	public void processEdge(GNode a, GNode b) {
		System.out.println("Edge processd in : " + a.toString() + ", " + b.toString());
	}
	
	public void processVertex(GNode n) {
		System.out.println("Vertex processd : " + n.toString());
	}

}

1 comment:

  1. Lớp học kế toán tổng hợp thực hành tại hải phòng
    Lớp học kế toán tổng hợp thực hành tại biên hòa đồng nai
    Lớp học kế toán tổng hợp thực hành tại vinh nghệ an
    Lớp học kế toán tổng hợp thực hành tại hải dương
    Lớp học kế toán tổng hợp thực hành tại ninh bình
    Lớp học kế toán tổng hợp thực hành tại hưng yên
    Lớp học kế toán tổng hợp thực hành tại phú thọ
    Lớp học kế toán tổng hợp thực hành tại hà nam
    Lớp học kế toán tổng hợp thực hành tại vĩnh phúc
    Lớp học kế toán tổng hợp thực hành tại bắc giang
    Lớp học kế toán tổng hợp thực hành tại thái nguyên
    Lớp học kế toán tổng hợp thực hành tại thái bình
    Lớp học kế toán tổng hợp thực hành tại nam định
    Lớp học kế toán tổng hợp thực hành tại thanh hóa
    Lớp học kế toán tổng hợp thực hành tại tphcm
    Lớp học kế toán tổng hợp thực hành tại bắc ninh
    Lớp học kế toán tổng hợp thực hành tại hà đông
    Lớp học kế toán tổng hợp thực hành tại long biên
    Lớp học kế toán tổng hợp thực hành tại thanh xuân
    Lớp học kế toán tổng hợp thực hành tại cầu giấy
    khóa học kế toán toán dành cho giám đốc và nhà quản lý
    công cụ dụng cụ
    thủ tục thanh lý tài sản cố định
    bảng cân đối kế toán
    thuế thu nhập cá nhân năm 2015
    phần mềm htkk 3.3.1

    ReplyDelete