Graph Algorithms Implementation

Lesson Overview

Welcome to our session on Graph Algorithms Implementation. A large proportion of real-world problems, from social networking to routing applications, can be represented by graphs. Understanding and implementing graph algorithms is thus a key skill to have in your programming toolkit. In this lesson, we introduce and explore one of the most fundamental graph traversal algorithms — the Breadth-First Search (BFS).

Quick Example

Let's take a sneak peek at the BFS algorithm. Given a graph and a starting vertex, BFS systematically explores the edges of the graph to "visit" each reachable vertex. It does this by managing a queue of vertices yet to be explored and consistently visiting all vertices adjacent to the current one before moving on. BFS is particularly efficient because it can find the shortest distance between the starting vertex and all other vertices in a graph.

Here's a sample BFS algorithm implemented in Java that we will dissect in depth and master:

import java.util.*;

public class Graph {
    private Map<Integer, List<Integer>> adjList = new HashMap<>();

    public void addEdge(int src, int dest) {
        adjList.putIfAbsent(src, new ArrayList<>());
        adjList.putIfAbsent(dest, new ArrayList<>());
        adjList.get(src).add(dest);
        adjList.get(dest).add(src);
    }

    public List<Integer> bfs(int start) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> result = new ArrayList<>();

        queue.offer(start);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (!visited.contains(node)) {
                visited.add(node);
                result.add(node);
                for (int neighbor : adjList.get(node)) {
                    if (!visited.contains(neighbor)) {
                        queue.offer(neighbor);
                    }
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        System.out.println("BFS traversal starting from node 2:");
        System.out.println(graph.bfs(2));
    }
}

What's Next?

Sign up

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal