// Java program to print BFS traversal from a given source vertex.

// BFS(int s) traverses vertices reachable from s.

import java.io.*;

import java.util.*;

// This class represents a directed graph using adjacency list

// representation

class Graph

{

private int V; // No. of vertices

private LinkedList<Integer> adj[]; //Adjacency Lists

// Constructor

Graph(int v)

{

V = v;

adj = new LinkedList[v];

for (int i=0; i<v; ++i)

adj[i] = new LinkedList();

}

// Function to add an edge into the graph

void addEdge(int v,int w)

{

adj[v].add(w);

}

// prints BFS traversal from a given source s

void BFS(int s)

{

// Mark all the vertices as not visited(By default

// set as false)

boolean visited[] = new boolean[V];

// Create a queue for BFS

LinkedList<Integer> queue = new LinkedList<Integer>();

// Mark the current node as visited and enqueue it

visited[s]=true;

queue.add(s);

while (queue.size() != 0)

{

// Dequeue a vertex from queue and print it

s = queue.poll();

System.out.print(s+” “);

// Get all adjacent vertices of the dequeued vertex s

// If a adjacent has not been visited, then mark it

// visited and enqueue it

Iterator<Integer> i = adj[s].listIterator();

while (i.hasNext())

{

int n = i.next();

if (!visited[n])

{

visited[n] = true;

queue.add(n);

}

}

}

}

// Driver method to

public static void main(String args[])

{

Graph g = new Graph(4);

g.addEdge(0, 1);

g.addEdge(0, 2);

g.addEdge(1, 2);

g.addEdge(2, 0);

g.addEdge(2, 3);

g.addEdge(3, 3);

System.out.println(“Following is Breadth First Traversal “+

“(starting from vertex 2)”);

g.BFS(2);

}

}

**output:**

Following is Breadth First Traversal (starting from vertex 2)

2 0 3 1

**Note**:

The code shown above traverses only the vertices reachable from a given source vertex. All the vertices may not be reachable from a given vertex (example Disconnected graph). To print all the vertices, we can modify the BFS function to do traversal starting from all nodes one by one and for this we will use **Depth-First Graph Traversal Algorithm.**

// Java program to print DFS traversal from a given given graph

import java.io.*;

import java.util.*;

// This class represents a directed graph using adjacency list

// representation

class Graph

{

private int V; // No. of vertices

// Array of lists for Adjacency List Representation

private LinkedList<Integer> adj[];

// Constructor

Graph(int v)

{

V = v;

adj = new LinkedList[v];

for (int i=0; i<v; ++i)

adj[i] = new LinkedList();

}

//Function to add an edge into the graph

void addEdge(int v, int w)

{

adj[v].add(w); // Add w to v’s list.

}

// A function used by DFS

void DFSUtil(int v,boolean visited[])

{

// Mark the current node as visited and print it

visited[v] = true;

System.out.print(v+” “);

// Recur for all the vertices adjacent to this vertex

Iterator<Integer> i = adj[v].listIterator();

while (i.hasNext())

{

int n = i.next();

if (!visited[n])

DFSUtil(n, visited);

}

}

// The function to do DFS traversal. It uses recursive DFSUtil()

void DFS(int v)

{

// Mark all the vertices as not visited(set as

// false by default in java)

boolean visited[] = new boolean[V];

// Call the recursive helper function to print DFS traversal

DFSUtil(v, visited);

}

public static void main(String args[])

{

Graph g = new Graph(4);

g.addEdge(0, 1);

g.addEdge(0, 2);

g.addEdge(1, 2);

g.addEdge(2, 0);

g.addEdge(2, 3);

g.addEdge(3, 3);

System.out.println(“Following is Depth First Traversal “+

“(starting from vertex 2)”);

g.DFS(2);

}

}

**output:**

Following is Depth First Traversal (starting from vertex 2)

2 0 1 3

// A Java program for Dijkstra’s single source shortest path algorithm.

// The program is for adjacency matrix representation of the graph

import java.util.*;

import java.lang.*;

import java.io.*;

class ShortestPath

{

// A utility function to find the vertex with minimum distance value,

// from the set of vertices not yet included in shortest path tree

static final int V=9;

int minDistance(int dist[], Boolean sptSet[])

{

// Initialize min value

int min = Integer.MAX_VALUE, min_index=-1;

for (int v = 0; v < V; v++)

if (sptSet[v] == false && dist[v] <= min)

{

min = dist[v];

min_index = v;

}

return min_index;

}

// A utility function to print the constructed distance array

void printSolution(int dist[], int n)

{

System.out.println(“Vertex Distance from Source”);

for (int i = 0; i < V; i++)

System.out.println(i+” tt “+dist[i]);

}

**Dijkstra’s** **algorithm for a distance traversal of a Graph from** **source** **vertex** s

// Funtion that implements Dijkstra’s single source shortest path

// algorithm for a graph represented using adjacency matrix

// representation

void dijkstra(int graph[][], int src)

{

int dist[] = new int[V]; // The output array. dist[i] will hold

// the shortest distance from src to i

// sptSet[i] will true if vertex i is included in shortest

// path tree or shortest distance from src to i is finalized

Boolean sptSet[] = new Boolean[V];

// Initialize all distances as INFINITE and stpSet[] as false

for (int i = 0; i < V; i++)

{

dist[i] = Integer.MAX_VALUE;

sptSet[i] = false;

}

// Distance of source vertex from itself is always 0

dist[src] = 0;

// Find shortest path for all vertices

for (int count = 0; count < V-1; count++)

{

// Pick the minimum distance vertex from the set of vertices

// not yet processed. u is always equal to src in first

// iteration.

int u = minDistance(dist, sptSet);

// Mark the picked vertex as processed

sptSet[u] = true;

// Update dist value of the adjacent vertices of the

// picked vertex.

for (int v = 0; v < V; v++)

// Update dist[v] only if is not in sptSet, there is an

// edge from u to v, and total weight of path from src to

// v through u is smaller than current value of dist[v]

if (!sptSet[v] && graph[u][v]!=0 &&

dist[u] != Integer.MAX_VALUE &&

dist[u]+graph[u][v] < dist[v])

dist[v] = dist[u] + graph[u][v];

}

// print the constructed distance array

printSolution(dist, V);

}

// Driver method

public static void main (String[] args)

{

/* Let us create the example graph discussed above */

int graph[][] = new int[][]{{0, 4, 0, 0, 0, 0, 0, 8, 0},

{4, 0, 8, 0, 0, 0, 0, 11, 0},

{0, 8, 0, 7, 0, 4, 0, 0, 2},

{0, 0, 7, 0, 9, 15, 0, 0, 0},

{0, 0, 0, 9, 0, 10, 0, 0, 0},

{0, 0, 4, 15, 10, 0, 2, 0, 0},

{0, 0, 0, 0, 0, 2, 0, 1, 6},

{8, 11, 0, 0, 0, 0, 1, 0, 7},

{0, 0, 2, 0, 0, 0, 6, 7, 0}

};

ShortestPath t = new ShortestPath();

t.dijkstra(graph, 0);

}

}

Output:

Vertex Distance from Source

0 0

1 4

2 12

3 19

4 21

5 11

6 9

7 8

8 15