Dijkstra algorithm's implementation in java (From one source to all the other nodes in Graph)

import java.io.*;
class Tnode
{
int prev;
int len;
char label;
boolean vis;
public Tnode(char lab)
 {
   label = lab;
   prev=-1;
   len=100000;
   vis=false;
 }
}

Kruskal's algorithm's implementation in java

Kruskal's algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component).

Example run

Image	Description
	AD and CE are the shortest edges, with length 5, and AD has been arbitrarily chosen, so it is highlighted.
	CE is now the shortest edge that does not form a cycle, with length 5, so it is highlighted as the second edge.
	The next edge, DF with length 6, is highlighted using much the same method.
	The next-shortest edges are AB and BE, both with length 7. AB is chosen arbitrarily, and is highlighted. The edge BD has been highlighted in red, because there already exists a path (in green) between B and D, so it would form a cycle (ABD) if it were chosen.
	The process continues to highlight the next-smallest edge, BE with length 7. Many more edges are highlighted in red at this stage: BC because it would form the loop BCE, DE because it would form the loop DEBA, and FE because it would form FEBAD.
	Finally, the process finishes with the edge EG of length 9, and the minimum spanning tree is found.

import java.io.*; 
class Tnode
{
char label;
//boolean vis;
int prev;
public Tnode(char lab) 
 { 
   label = lab; 
   //vis=false;
   prev=-1;
 } 
}

Prim's algorithm's implementation in java

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted, undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

Example run

Image	U	possible edges	V \ U	Description
	{}		{A,B,C,D,E,F,G}	This is our original weighted graph. The numbers near the edges indicate their weight.
	{D}	{D,A} = 5 V {D,B} = 9 {D,E} = 15 {D,F} = 6	{A,B,C,E,F,G}	Vertex D has been arbitrarily chosen as a starting point. Vertices A, B, E and F are connected to D through a single edge. A is the vertex nearest to D and will be chosen as the second vertex along with the edge AD.
	{A,D}	{D,B} = 9 {D,E} = 15 {D,F} = 6 V {A,B} = 7	{B,C,E,F,G}	The next vertex chosen is the vertex nearest to either D or A. B is 9 away from D and 7 away from A, E is 15, and F is 6. F is the smallest distance away, so we highlight the vertex F and the edge DF.
	{A,D,F}	{D,B} = 9 {D,E} = 15 {A,B} = 7 V {F,E} = 8 {F,G} = 11	{B,C,E,G}	The algorithm carries on as above. Vertex B, which is 7 away from A, is highlighted.
	{A,B,D,F}	{B,C} = 8 {B,E} = 7 V {D,B} = 9 cycle {D,E} = 15 {F,E} = 8 {F,G} = 11	{C,E,G}	In this case, we can choose between C, E, and G. C is 8 away from B, E is 7 away fromB, and G is 11 away from F. E is nearest, so we highlight the vertex E and the edge BE.
	{A,B,D,E,F}	{B,C} = 8 {D,B} = 9 cycle {D,E} = 15 cycle {E,C} = 5 V {E,G} = 9 {F,E} = 8 cycle {F,G} = 11	{C,G}	Here, the only vertices available are C and G.C is 5 away from E, and G is 9 away from E.C is chosen, so it is highlighted along with the edge EC.
	{A,B,C,D,E,F}	{B,C} = 8 cycle {D,B} = 9 cycle {D,E} = 15 cycle {E,G} = 9 V {F,E} = 8 cycle {F,G} = 11	{G}	Vertex G is the only remaining vertex. It is 11 away from F, and 9 away from E. E is nearer, so we highlight G and the edge EG.
	{A,B,C,D,E,F,G}	{B,C} = 8 cycle {D,B} = 9 cycle {D,E} = 15 cycle {F,E} = 8 cycle {F,G} = 11 cycle	{}	Now all the vertices have been selected and the minimum spanning tree is shown in green. In this case, it has weight 39.

Implementation:

import java.io.*;
class Tnode
{
int prev;
int len;
char label;
boolean vis;
public Tnode(char lab)
 {
   label = lab;
   prev=-1;
   len=100000;
   vis=false;
 }
}

Dijkstra algorithm's implementation in java (From one source to one destination in Graph)

import java.io.*;
class Tnode
{
int prev;
int len;
char label;
boolean vis;
public Tnode(char lab)
 {
   label = lab;
   prev=-1;
   len=100000;
   vis=false;
 }
}
class graph
{
  public final int MAX = 20;
  public int nverts,i,min;
  public Tnode vlist[];
  public int adj[][];
  public graph()
  {
   nverts = 0;
   adj = new int[MAX][MAX];
   vlist = new Tnode[MAX];
   for(int i=0;i<MAX;i++)
 {
for(int j=0;j<MAX;j++)
adj[i][j] = 0;
 }
  }
  public void addver(char lab)
  {
    vlist[nverts++] = new Tnode(lab);
  }
  public void addedge(int start,int end,int cost)
  {
    adj[start][end] = cost;
  }
  public int getind(char l)
  {
    for(int i=0;i<nverts;i++)
      if(vlist[i].label==l)
      return i;
    return (MAX+1);
  }
  public void brfs(int src, int dest)
  {
 int k;
 int path[]=new int[20];
 vlist[src].len=0;
 vlist[src].vis=true;
k=src;
do{
for(i=0;i<nverts;i++)
{
if((adj[k][i]!=0)&&(vlist[i].vis==false))
{
if(vlist[k].len+adj[k][i]<vlist[i].len)
{
vlist[i].prev=k;
vlist[i].len=vlist[k].len+adj[k][i];
}
}
}
k=0;
min=100000;
for(i=0;i<nverts;i++)
{
if((vlist[i].vis==false)&&(vlist[i].len<min))
{
min=vlist[i].len;
k=i;
}
}
vlist[k].vis=true;
 }while(k!=dest);
i=0;
k=dest;
int c=0;
do{
path[i++]=k;
c++;
k=vlist[k].prev;
}while(k>=0);
System.out.println("shortest path from source to destination is \n");
for(i=c-1;i>=0;i--)
System.out.print("-->"+vlist[path[i]].label);
System.out.println("\n shortest distance from source to destination is \n"+vlist[dest].len);
}
}

BFS implementation using Java

import java.io.*;
class quelist
{
  public int front;
  public int rear;
  public int maxsize;
  public int que[];
  public quelist(int size)
  {
    maxsize = size;
    que = new int[size];
    front = rear = -1;
  }
  public void enque(int x)
  {
     if(front==-1)
     front = 0;
     que[(++rear)%maxsize]=x;
  }
  public int deque()
  {
    int temp = que[front];
    front = (front +1)%maxsize;
    return temp;
  }
   public boolean isempty()
  {
    return((front>rear)||(front==-1));
  }
}  
class vertex
{
 public char label;
 public boolean wasvisited;
 public vertex(char lab)
 {
   label = lab;
   wasvisited = false;
 }
}
class graph
{
  public final int MAX = 20;
  public int nverts;
  public int adj[][];
  public vertex vlist[];
  quelist qu;
  public graph()
  {
   nverts = 0;
   vlist = new vertex[MAX];
   adj = new int[MAX][MAX];
   qu = new quelist(MAX);
   for(int i=0;i<MAX;i++)
    for(int j=0;j<MAX;j++)
     adj[i][j] = 0;
  }
  public void addver(char lab)
  {
    vlist[nverts++] = new vertex(lab);
  }
  public void addedge(int start,int end)
  {
    adj[start][end] = 1;
    adj[end][start] = 1;
  }
  public int getadjunvis(int i)
  {
    for(int j=0;j<nverts;j++)
      if((adj[i][j]==1)&&(vlist[j].wasvisited==false))
      return j;
    return (MAX+1);  
  }
  public int getind(char l)
  {
    for(int i=0;i<nverts;i++)
      if(vlist[i].label==l)
      return i;
    return (MAX+1);
  }
  public void brfs()
  {
    vlist[0].wasvisited = true;
    System.out.print(vlist[0].label);
    qu.enque(0);
    int v2;
    while(!(qu.isempty()))
    {
     int v1 = qu.deque();
     while((v2=getadjunvis(v1))!=(MAX+1))
      {
    vlist[v2].wasvisited = true;
        System.out.print(vlist[v2].label);
        qu.enque(v2);
      }  
    }
    System.out.print("\n");
  }
}

DFS implementation using Java

import java.io.*;
class stcklist
{
  public int top;
  public int maxsize;
  public int[] stck;

  public stcklist(int size)
  {
    maxsize = size;
    stck = new int[size];
    top= -1;
  }

  public void push(int x)
  {
     stck[++top]=x;
  }

  public int pop()
  {
    int temp = stck[top];
    top--;
    return temp;
  }
  public int top()
  {
    int temp = stck[top];
    return temp;
  }
  public boolean isempty()
  {
    return(top==-1);
  }
}  

class vertex
{
 public char label;
 public boolean wasvisited;

 public vertex(char lab)
 {
   label = lab;
   wasvisited = false;
 }
}

class graph
{
  public final int MAX = 20;
  public int nverts;
  public int adj[][];
  public vertex vlist[];
  stcklist st;

  public graph()
  {
   nverts = 0;
   vlist = new vertex[MAX];
   adj = new int[MAX][MAX];
   st = new stcklist(MAX);
   for(int i=0;i<MAX;i++)
    for(int j=0;j<MAX;j++)
     adj[i][j] = 0;
  }

  public void addver(char lab)
  {
    vlist[nverts++] = new vertex(lab);
  }

  public void addedge(int start,int end)
  {
    adj[start][end] = 1;
    adj[end][start] = 1;
  }
 
  public int getadjunvis(int i)
  {
    for(int j=0;j<nverts;j++)
      if((adj[i][j]==1)&&(vlist[j].wasvisited==false))
      return j;
    return (MAX+1);  
  }

  public int getind(char l)
  {
    for(int i=0;i<nverts;i++)
      if(vlist[i].label==l)
      return i;
    return (MAX+1);
  }

  public void drfs()
  {
    vlist[0].wasvisited = true;
    System.out.print(vlist[0].label);
    st.push(0);
    int v2;
    while(!(st.isempty()))
    {
     int v1 = st.top();
// v2=getadjunvis(v1));
     if((v2=getadjunvis(v1))!=(MAX+1))
      {
    vlist[v2].wasvisited = true;
        System.out.print(vlist[v2].label);
        st.push(v2);
      }
 else
 st.pop();
    }
  }
}