CseWay

A Way For Learning

Breadth First Paths

, No comments

BreadthFirstPaths Add and implement a distTo() method to the BreadthFirstPaths API on undirected graph G, which returns the number of edges on the shortest path from the source to a given vertex. A distTo() query should run in constant time.

Solution:
  1. MainClass:

import java.util.Scanner;

public class Problem{
public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int V = in.nextInt();
        int E = in.nextInt();
        int s = in.nextInt();
        int v,w;
        Graph G = new Graph(V);
        for (int i=0;i<E;i++){

            v = in.nextInt();
            w = in.nextInt();
            G.addEdge(v,w);
        }

        BFS bfs= new BFS(G,s);
        Iterable<Integer> paths;
        for (v = 0; v < G.V(); v++){
            if (bfs.hasPathTo(v)){
                System.out.printf("%d to %d (%d): ",s,v,bfs.distTo[v]);
                paths = bfs.pathTo(v);
                for (int e: paths){
                    if (e == s) System.out.print(s);
                    else System.out.print("-"+e);
                }
            }
            else {
                System.out.printf("%d to %d (-): not connected",s,v);
            }
            System.out.println();
        }
    }
}

-------------------------------------------------------------------------------------------------------------------------
2.  BFS Class
import java.util.Scanner;


public class BFS {
    private int[] edgeTo;
    private boolean[] marked;
    int[] distTo;
    private static final int INF = Integer.MAX_VALUE;
    int s;
    BFS(Graph G, int s){
        this.s = s;
        edgeTo = new int[G.V()];
        marked = new boolean[G.V()];
        distTo = new int[G.V()];
        for (int v=0; v<G.V(); v++)
            distTo[v] = INF;
        bfs(G,s);
    }

    private void bfs(Graph G, int s){
        Queue<Integer> q = new Queue<>();
        q.enqueue(s);
        marked[s] = true;
        distTo[s] = 0;

        while (!q.isEmpty()){
            int v =q.dequeue();
            for (int w: G.adj(v)){
                if (!marked[w]){
                    marked[w] = true;
                    edgeTo[w] = v;
                    distTo[w] = distTo[v]+1;
                    q.enqueue(w);
                }
            }
        }
    }

    boolean hasPathTo(int v){
        return marked[v];
    }
    Iterable<Integer> pathTo(int v){
        Stack<Integer> paths = new Stack<>();
        for (int x = v; x !=s; x=edgeTo[x]){
            paths.push(x);
        }
        paths.push(s);
        return paths;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int V = in.nextInt();
        int E = in.nextInt();
        int s = in.nextInt();
        int v,w;
        Graph G = new Graph(V);
        for (int i=0;i<E;i++){

            v = in.nextInt();
            w = in.nextInt();
            G.addEdge(v,w);
        }

        BFS bfs= new BFS(G,s);
        Iterable<Integer> paths;
        for (v = 0; v < G.V(); v++){
            if (bfs.hasPathTo(v)){
                System.out.printf("%d to %d (%d): ",s,v,bfs.distTo[v]);
                paths = bfs.pathTo(v);
                for (int e: paths){
                    if (e == s) System.out.print(s);
                    else System.out.print("-"+e);
                }
            }
            else {
                System.out.printf("%d to %d (-): ",s,v);
            }
            System.out.println();
        }
    }
}
-------------------------------------------------------------------------------------------------------------------------
3. Graph Class
import java.util.Scanner;
class Graph{
    private int E;
    private int V;
    private Bag<Integer>[] adj ;
    private int[] inDegree;
    private int[] outDegree;
    Graph(int V){
        this.V = V;
        inDegree = new int[V];
        outDegree = new int[V];
        adj = (Bag<Integer>[]) new Bag[V];
        for (int v =0; v<V; v++)
            adj[v] = new Bag<Integer>();
    }

    int V(){
        return V;
    }

    int E(){
        return E;
    }


    void addEdge(int v, int w){


        E++;
        adj[v].add(w);
        adj[w].add(v);
        inDegree[w]++;
        outDegree[v]++;
    }

    int inDegree(int w){
        validVertex(w);
        return inDegree[w];
    }

    int outDegree(int w){
        validVertex(w);
        return outDegree[w];
    }



    boolean hasEdge(int v, int w){

        validVertex(v);
        if (!(v < 0 || v >V-1)) validVertex(w);

        for (int i: adj[v]){
            if (i==w) return true;
        }
        return false;
    }

    Iterable<Integer> adj(int v){
        return adj[v];
    }

    void validVertex(int v){
        try{
            if (v < 0 || v >V-1) throw new Exception();
        }
        catch (Exception e){
            System.out.print("vertex "+v+" is not between "+0+" and "+(V-1));
            System.out.println();
        }

    }

    public String toString(){
        String s = "";
        s = s+V+" vertices, "+E+" edges"+" \n";
        for (int v=0; v < V; v++){
            s = s+ v + ":";
            for (int w: adj[v]){
                s = s + " "+w;
            }
            s = s+ " \n";
        }
        return s;
    }


}
------------------------------------------------------------------------------------------------------------------------
4.

No comments :

Post a Comment

Subscribe to: Post Comments ( Atom )