grafuri

import java.awt.*;



public class Vertex {

   
        Color color;
        Vertex predecessor;
        int distance;
        int discovered;
        int finalized;
        char label;
        int index;
        int infinite = 100;
       
    public Vertex(int i){
        index=i;
        color=Color.white;
        distance=infinite;
        predecessor=null;
    }
}

//////////////////////////////////////////////////

import java.awt.*;
import java.util.*;


public class Graph {
   
        int maxVerts = 20;
        int nVerts = 0;
        ArrayList vertexList = new ArrayList();
        int A[][] = new int[maxVerts][maxVerts];
       
public Graph(){
   
    for(int i=0; i<maxVerts ; i++)
        for(int j=0 ; j<maxVerts; j++)
             A[i][j]=0;
}
public void addVertex(){
    vertexList.add(new Vertex(nVerts++));
}
public void addEdge(int v1,int v2){
    A[v1][v2]=1;
    A[v2][v1]=1;
}
public void addEdge (int v1, int v2, int w) {
     
      A[v1][v2] = w;
      A[v2][v1] = w;
   
     }



public static void main( String[] args){
    Graph graph = new Graph();
    graph.addVertex();
    graph.addVertex();
    graph.addVertex();
    graph.addVertex();
    graph.addEdge(0,1);
    graph.addEdge(1,2);
    graph.addEdge(0,3);
    graph.BFS(0);
    graph.DFS();
    graph.DJIKSTRA(0);
}
   
public void BFS(int s){   // asta nu intra la examen
        System.out.println("Parcurgerea in latime");
    LinkedList queue = new LinkedList();
    ((Vertex)vertexList.get(s)).color=Color.gray;
    ((Vertex)vertexList.get(s)).distance=0;
   
    queue.addFirst(vertexList.get(s));
   
    while(!queue.isEmpty()){
        Vertex u=(Vertex)queue.getLast();
       
        System.out.println(u.index);
     for(int v=0;v<nVerts;v++)
         if(A[v][u.index]==1&&((Vertex)vertexList.get(v)).color==Color.white){
             ((Vertex)vertexList.get(v)).color=Color.gray;
             ((Vertex)vertexList.get(v)).distance=u.distance+1;
             ((Vertex)vertexList.get(v)).predecessor=u;
             queue.addFirst(vertexList.get(v));
         }
         queue.removeLast();
         u.color=Color.black;
     }       
    }
public void DFS(){
    System.out.println("Parcurgerea in adancime");
   
    int t;
   
    Iterator u= vertexList.iterator();
    Vertex v;
   
      while(u.hasNext()){
          ((Vertex)u.next()).color=Color.white; }
     t=0;
   
     u=vertexList.iterator();
   
     while (u.hasNext()){
         v = (Vertex)u.next();
          if (v.color==Color.white)
              EXPLORARE(v);
     }
}
public void EXPLORARE (Vertex u){
    u.color=Color.gray;
   
    int t; t=0;
   
    System.out.println(u.index);
    u.distance=t;
    t++;
   
    Iterator i= vertexList.iterator();
     while (i.hasNext()){
         Vertex v=(Vertex)i.next();
         if (v.color==Color.white)
             v.predecessor=u;
     }
     u.color = Color.black;
     u.finalized=t;
     t++;       
}
public void DJIKSTRA(int s){
   
        System.out.println("Algoritmul D");
       
        Vertex u;
    Iterator i = vertexList.iterator();
      while (i.hasNext()){
          u=(Vertex)i.next();
          u.distance=u.infinite;
          u.predecessor=null;
      }
    ((Vertex)vertexList.get(s)).distance=0;
      ArrayList DList = (ArrayList) vertexList.clone();
     
      while (!DList.isEmpty()){
          int min =0;
          for(int k=1;k<DList.size();++k)
              if(((Vertex)DList.get(min)).distance > ((Vertex)DList.get(k)).distance)
                min=k;
          u=(Vertex)DList.get(min);
          DList.remove(min);
    for(int k=0; k<nVerts;k++)
             if(A[k][u.index]!=0)
                 if(((Vertex)vertexList.get(k)).distance > u.distance + A[k][u.index])
                 {
                     ((Vertex)vertexList.get(k)).distance = u.distance + A[k][u.index];
                     ((Vertex)vertexList.get(k)).predecessor=u;
                 }
    for( int k=0 ; k< nVerts ; ++k){
              System.out.println("Distance: "+((Vertex)vertexList.get(k)).distance+ " ");
           
          }
      }
}
}