package main.java.algo.datastructures.graphs; import java.util.LinkedList; import java.util.List; import java.util.Queue; public class BreadthFirstSearch { public void doBFS(Graph g, GNode root) { GNode n = root; List<GNode> adjacents = null; // using a queue // Note in Java - Queue is an Interface and not a class like Stack. LinkedList internally implements it. // so this is how we use a queue // Queue provides add and poll methods for enqueue and dequeue respectively Queue<GNode> q = new LinkedList<GNode>(); // in BFS - we process the siblings first than the children. Example - process nodes at same depth in a tree before going to the next level. q.add(n); while (!q.isEmpty()) { // dequeue n = q.poll(); 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; q.add(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; } } 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()); } }
This blog contains series of posts explaing basic and advanced concepts in data structures, algorithms, parallel processing, system design along with fundamentals in Java and unix with the sample code.
Sunday, September 18, 2011
Graph - Breadth First Search
Subscribe to:
Post Comments (Atom)
lớp học kế toán tổng hợp
ReplyDeletelớp học kế toán thực hành
khóa học kế toán tổng hợp tại vinh nghệ an
trung tâm đào tạo kế toán tại vinh nghệ an
khóa học kế toán thực hành
Khóa học kế toán tổng hợp thực hành tại bắc ninh
Khóa học kế toán tổng hợp thực hành tại hải phòng
Khóa học kế toán tổng hợp thực hành tại tphcm
Khóa học kế toán tổng hợp thực hành tại bình dương
Khóa học kế toán tổng hợp thực hành tại hà đông
Khóa 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 tổng hợp thực hành tại long biên
Khóa học kế toán tổng hợp thực hành tại thanh xuân
dịch vụ kê khai làm báo cáo thuế hàng tháng
dịch vụ kế toán thuế trọn gói chuyên nghiệp giá rẻ
dịch vụ làm báo cáo tài chính giá rẻ
dịch vụ kế toán trọn gói chuyên nghiệp giá rẻ
dịch vụ rà soát dọn dẹp sổ sách kế toán chuyên nghiệp giá rẻ
dịch vụ quyết toán thuế chuyên nghiệp giá rẻ