Showing posts with label Graphs. Show all posts
Showing posts with label Graphs. Show all posts
Breadth First Paths
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:
- 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.
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.
Graphs: Representation, Traversals-Problem Set
- Suppose a weighted undirected graph has n vertices and e edges. The weights are all integers. Assume that the space needed to store an integer is the same as the space needed to store an object reference, both equal to one unit. What is the minimum value of e for which the
Subscribe to:
Comments
(
Atom
)