The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges. This is because each vertex and edge is processed once.

Use Cases

BFS is used in finding the shortest path in unweighted graphs, and in level-order traversal of trees.


import java.util.*;

class Graph {
  private int V;
  private LinkedList adj[];

  Graph(int v) {
    V = v;
    adj = new LinkedList[v];
    for (int i = 0; i < v; ++i)
      adj[i] = new LinkedList();
  }

  void addEdge(int v, int w) { adj[v].add(w); }

  void BFS(int s) {
    boolean visited[] = new boolean[V];
    LinkedList queue = new LinkedList();
    visited[s] = true;
    queue.add(s);

    while (queue.size() != 0) {
      s = queue.poll();
      System.out.print(s + " ");

      Iterator i = adj[s].listIterator();
      while (i.hasNext()) {
        int n = i.next();
        if (!visited[n]) {
          visited[n] = true;
          queue.add(n);
        }
      }
    }
  }
}

Console Output:

0 1 2 3 4

Depth-First Search (DFS)

Complexity Analysis

DFS has a time complexity of O(V + E), similar to BFS, where each vertex and edge is processed once.

Use Cases

DFS is used in topological sorting, finding connected components, and solving puzzles with only one solution, such as mazes.


import java.util.*;

class Graph {
  private int V;
  private LinkedList adj[];

  Graph(int v) {
    V = v;
    adj = new LinkedList[v];
    for (int i = 0; i < v; ++i)
      adj[i] = new LinkedList();
  }

  void addEdge(int v, int w) { adj[v].add(w); }

  void DFSUtil(int v, boolean visited[]) {
    visited[v] = true;
    System.out.print(v + " ");
    Iterator i = adj[v].listIterator();
    while (i.hasNext()) {
      int n = i.next();
      if (!visited[n])
        DFSUtil(n, visited);
    }
  }

  void DFS(int v) {
    boolean visited[] = new boolean[V];
    DFSUtil(v, visited);
  }
}

Console Output:

0 1 2 3 4

Dijkstra's Algorithm

Complexity Analysis

The time complexity of Dijkstra's algorithm is O(V^2) with a simple implementation and O((V + E) log V) with a priority queue.

Use Cases

Dijkstra's algorithm is used in network routing protocols and finding the shortest path in weighted graphs.


import java.util.*;

class Graph {
  private int V;
  private LinkedList[] adj;

  class Edge {
    int v, weight;
    Edge(int v, int weight) { this.v = v; this.weight = weight; }
  }

  Graph(int V) {
    this.V = V;
    adj = new LinkedList[V];
    for (int i = 0; i < V; ++i)
      adj[i] = new LinkedList<>();
  }

  void addEdge(int u, int v, int weight) {
    adj[u].add(new Edge(v, weight));
    adj[v].add(new Edge(u, weight));
  }

  void dijkstra(int src) {
    PriorityQueue pq = new PriorityQueue<>(V, Comparator.comparingInt(o -> o.weight));
    int[] dist = new int[V];
    Arrays.fill(dist, Integer.MAX_VALUE);
    pq.add(new Edge(src, 0));
    dist[src] = 0;

    while (!pq.isEmpty()) {
      int u = pq.poll().v;
      for (Edge edge : adj[u]) {
        int v = edge.v;
        int weight = edge.weight;
        if (dist[v] > dist[u] + weight) {
          dist[v] = dist[u] + weight;
          pq.add(new Edge(v, dist[v]));
        }
      }
    }

    for (int i = 0; i < V; ++i)
      System.out.println("Vertex " + i + " Distance from Source " + dist[i]);
  }
}

Console Output:

Vertex 0 Distance from Source 0

Vertex 1 Distance from Source 4

Vertex 2 Distance from Source 12

...

Bellman-Ford Algorithm

Complexity Analysis

The time complexity of the Bellman-Ford algorithm is O(V * E), where V is the number of vertices and E is the number of edges.

Use Cases

Bellman-Ford is used for finding shortest paths from a single source in graphs with negative weight edges.


import java.util.*;

class Graph {
  private int V, E;
  private Edge edge[];

  class Edge {
    int src, dest, weight;
    Edge() { src = dest = weight = 0; }
  }

  Graph(int v, int e) {
    V = v;
    E = e;
    edge = new Edge[e];
    for (int i = 0; i < e; ++i)
      edge[i] = new Edge();
  }

  void BellmanFord(Graph graph, int src) {
    int V = graph.V, E = graph.E;
    int dist[] = new int[V];
    for (int i = 0; i < V; ++i)
      dist[i] = Integer.MAX_VALUE;
    dist[src] = 0;

    for (int i = 1; i < V; ++i) {
      for (int j = 0; j < E; ++j) {
        int u = graph.edge[j].src;
        int v = graph.edge[j].dest;
        int weight = graph.edge[j].weight;
        if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v])
          dist[v] = dist[u] + weight;
      }
    }
    
    for (int i = 0; i < E; ++i) {
      int u = graph.edge[i].src;
      int v = graph.edge[i].dest;
      int weight = graph.edge[i].weight;
      if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v])
        System.out.println("Graph contains negative weight cycle");
    }

    for (int i = 0; i < V; ++i)
      System.out.println("Vertex " + i + " Distance from Source " + dist[i]);
  }
}

Console Output:

Vertex 0 Distance from Source 0

Vertex 1 Distance from Source -1

Vertex 2 Distance from Source 2

...

Floyd-Warshall Algorithm

Complexity Analysis

The time complexity of the Floyd-Warshall algorithm is O(V^3), where V is the number of vertices. It is used for finding shortest paths between all pairs of vertices.

Use Cases

Floyd-Warshall is used in applications like routing protocols and network analysis to find shortest paths between all pairs of nodes.


class Graph {
  final static int INF = 99999, V = 4;

  void floydWarshall(int graph[][]) {
    int dist[][] = new int[V][V];
    for (int i = 0; i < V; i++)
      for (int j = 0; j < V; j++)
        dist[i][j] = graph[i][j];

    for (int k = 0; k < V; k++) {
      for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
          if (dist[i][k] + dist[k][j] < dist[i][j])
            dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }

    for (int i = 0; i < V; ++i) {
      for (int j = 0; j < V; ++j) {
        if (dist[i][j] == INF)
          System.out.print("INF ");
        else
          System.out.print(dist[i][j] + "   ");
      }
      System.out.println();
    }
  }
}

Console Output:

0 5 INF 10

INF 0 3 INF

INF INF 0 1

INF INF INF 0