Kodr

Kodr

  • Content
  • Blog
  • About
  • Languages iconEnglish
    • Español

›Key Concepts

Technical Interviews

  • What are technical interviews based on?
  • Essential content & how to solve algorithms

Big-O Notation

  • Big-O Notation
  • Big-O Examples
  • Big-O Exercises

Optimisation Techniques

  • BUD optimisation
  • DIY Optimisation

Key Concepts

  • Linked Lists
  • Stack & Queues
  • Trees
  • Graphs
  • Tries
  • Sorting
  • Searching
  • Recursion
  • Dynamic Programming

Problems: Arrays & Strings

  • Is Unique
  • String Rotation
  • Check Permutation
  • URLify
  • One Edit Away
  • String Compression
  • Rotate Matrix
  • Zero Matrix
  • Valid Parenthesis

Problems: Linked Lists

  • Remove duplicates
  • Kth to last node
  • Delete Middle Node
  • Partition
  • Sum List
  • Palindrome
  • Intersection
  • Loop Detection

Problems: Stacks & Queues

  • Stack Min
  • Stack Of Plates
  • Queue via Stacks
  • Sort Stack
  • Animal Shelter

Problems: Trees

  • Path Sum
  • Construct Binary Tree from Inorder and Postorder Traversal

Problems: Binary Search Trees & Graphs

  • Route Between Two Nodes
  • Minimal Tree
  • List of Depths
  • Check Balanced
  • Validate BST
  • Successor
  • Build Order
  • First Common Ancestor
  • Check Sub-Tree
  • (Harder) Random Node

Problems: Sorting & Searching

  • Merge Sorted Array
  • First Bad Version

Problems: Dynamic Programming

  • Triple Step
  • Magic Index
  • (Hard) Towers Of Hanoi

Graphs

image

What is a graph? 🤠

A Graph is a collection of nodes, similar to a Tree, and actually a Tree is a type of graph, but not all graphs are Trees.

When the nodes in a graph are connected we call them edges, and there are two types of connections between nodes. Directed which is like a one way street (unidirectional) and Undirected edges which are like a two-way street.

Is also important to note that graphs don't have to be interconnected, they might also consists of multiple isolated subgraphs. When there is a path between every pair of vertices we call it a connected graph.

Let's have a look at a graphical representation of a graph:

graphs

But, how do we represent this in a programme? Let me show you 2 common ways.

Adjacency lists

In this representation, for every node we have we store a list of its adjacent nodes, let me show you an example:

If we have the classes for the graph and node:

class Graph {
    public Node[] nodes;
}

Class Node {
    public int data;
    public Node[] children;
}

Remember that unlike a Tree, in a graph we might be unable to reach all the nodes from the "root", hence why we need a parent Graph class.

In the case of the graph that I drew in the example it would be represented like this:

NodeAdjacency list
01
12
20, 3
32
46
54
65

Adjacency Matrices

This is a Matrix which is NxN (N is the number of nodes). It can be filled with 0/1 or true/false values indicating true whenever there is an edge from node I to node J.

Imagine the graph: Adjacency Graph

The Matrix would be represented as:

-0123
00100
10010
21000
30010

The same graph algorithms that are used on adjacency lists (breadth-first search, etc.) can be performed with adjacency matrices, but they may be somewhat less efficient. In the adjacency list representation, you can easily iterate through the neighbors of a node. In the adjacency matrix representation, you will need to iterate through all the nodes to identify a node's neighbors.

Graph Search

There are 2 common approaches when it comes to searching a graph.

Let's compare them with the same graph: search Graph


Depth-First Search (DFS)

Here we start at an arbitrarily selected Node, then we explore each branch completely before moving onto the next branch. We go deep first prior going wide.

DFS is the preferred search if we want to visit every single node in the graph. Bear in mind both can do it but DFS is a bit simpler.

Let's look at some PseudoCode implementation for this:

void search(Node Root) {
   if (root == null) return;
   visit(root);
   root.visited = true;
   for each (Node n in root.adjacent) {
       if (n.visited == false) search(n);
   }   
} 

As previously stated, in DFS we visit a node (N1), then we iterate through each of N1 neighbours. When visiting a node N2 which is a neighbour of N1, we visit all of N2s neighbours before going on to N1s other neighbours. We do this exhaustively until we've searched all the neighbours.

Search order for example graph: 0, 1, 3, 2, 4, 5

Note that pre-order and other forms of tree traversal are a form of DFS. The key difference is that when implementing this algorithm for a graph, we must check if the node has been visited. If we don't, we risk getting stuck in an infinite loop.

Breadth-First Search (BFS)

Same as before, we arbitrarily select a Node, but here we explore each neighbour first, before going to any children. That is, we go wide prior going deep.

BFS is generally better if we want to find the shortest path between any nodes.

Let's look at some PseudoCode implementation for this:

void search(Node root) {
    Queue queue = new Queue();
    root.marked = true;
    queue.enqueue(root); // add to the end of the Q
    
    while(!queue.isEmpty()) {
        Node r = queue.dequeue(); // remove from the front of the Q
        visit(r);
        foreach (Node n in r.adjacent) {
            if (n.marked == false) {
                n.marked = true;
                queue.enqueue(n);
            }       
        }   
    }
}

As previously stated, in BFS a node visits each of N1 neighbours prior moving onto the neighbours of each neighbour. Try not to make the mistake of trying to implement this recursively, an iterative approach using a queue tends to be much easier.

Search order for example graph: 0, 1, 4, 5, 3, 2

Quick Example Comparison

Imagine representing all the friendships in the entire world in a graph. If we wanted to find a path of friendship between Diego and Chris (who are already friends).

In DFS, we could take a path like this: Diego -> Carlos -> John -> Antonio -> Jair -> Jake -> Arianna -> Luis -> etc. Then we would find ourselves very far away. We may in fact go through most of the world without realising that, in fact Diego and Chris are already friends. It also wouldn't find us the shortest path.

In BFS, we would stay close to Diego for as long as possible, we might iterate through Diego's friends, but we wouldn't go to his more distant connections until it becomes necessary. If Chris is the friend of a friend of Diego, we would find him relatively quickly as well.

Last updated on 3/26/2020
← TreesTries →
  • What is a graph? 🤠
  • Adjacency lists
  • Adjacency Matrices
  • Graph Search
  • Depth-First Search (DFS)
  • Breadth-First Search (BFS)
  • Quick Example Comparison
Kodr
Content
IntroBig O NotationOptimisation
Coding Problems
Check PermutationIsUniqueURLify
Blogs
Tecnica Pomodoro
Social
About MeGitHub
Follow @diego_romero_x
Copyright © 2021 Kodr