Back to Basics - Data Structures and Algorithms

Being in Silicon Valley, one can quickly fall behind. Technology is advancing so quickly and it can be hard to keep up.

To stay strong, one should spend 10% of their time dedicated towards Professional Development. This includes taking courses and continuing to learn and grow. It includes reading books and autobiographies to learn from others and explore new ideas. It can include keeping a side project to explore solving real world challenges and problems.

However, there are some fundamentals across the board that seem to be a part of a solid foundation. Here, I will explore some basics, which admittedly, I have to brush up on.

To start, here is an site on complexity bigocheatsheet.com.

Vertex

public class Vertex {
 String name;
 public Vertex(String name) {
  this.name = name;
 }
 
 public String getName() {
  return name;
 }
}

Code Formatted by ToGoTutor

Graph

package graph;

import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.Map;

public class Graph {
    Map<Vertex, LinkedHashSet<Vertex>> edgeMap = new LinkedHashMap<Vertex, LinkedHashSet<Vertex>>();

    public LinkedHashSet<Vertex> adjacentEdges(Vertex v) {
        LinkedHashSet<Vertex> set = edgeMap.get(v);
        if(set == null) {
            return new LinkedHashSet<Vertex>();
        } else {
            return set;
        }
    } 
    
    public void connectVertices(Vertex v1, Vertex v2) {
        addVertexToSet(v1, v2);
        addVertexToSet(v2, v1);
    }
    
    private void addVertexToSet(Vertex v1, Vertex v2) {
        LinkedHashSet<Vertex> set1 = edgeMap.get(v1);
        if(set1 == null) {
            set1 = new LinkedHashSet<Vertex>();
            edgeMap.put(v1, set1);
        }
        if(!set1.contains(v2)) {
            set1.add(v2);
        }
    }
}

Code Formatted by ToGoTutor

The Depth First Search at en.wikipedia.org can be implemented in Java as follows:

package graph;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;

public class Main {
    public static void main (String[] args) {
        Vertex A = new Vertex("A");
        Vertex B = new Vertex("B");
        Vertex C = new Vertex("C");
        Vertex D = new Vertex("D");
        Vertex E = new Vertex("E");
        Vertex F = new Vertex("F");
        Vertex G = new Vertex("G");
        
        Graph graph = new Graph();
        graph.connectVertices(A, B);
        graph.connectVertices(A, C);
        graph.connectVertices(A, E);
        graph.connectVertices(B, D);
        graph.connectVertices(B, F);
        graph.connectVertices(C, G);
        graph.connectVertices(E, F);
        
        DFS(graph, A);
        DFS_Iterative(graph, A);
        
        BFS(graph, A);
    }

    static Map<Vertex, Boolean> dfsMap = new LinkedHashMap<Vertex, Boolean>();
    private static void DFS(Graph G, Vertex v) {
        dfsMap.put(v, true);
        System.out.println("dfsMap:"+v.getName());
        for(Vertex w: G.adjacentEdges(v)) {
            if(dfsMap.get(w) == null) {
                DFS(G, w);
            }
        }
    }

    static Stack<Vertex> dfsiStack = new Stack<Vertex>();
    static Map<Vertex, Boolean> dfsiMap = new LinkedHashMap<Vertex, Boolean>();
    private static void DFS_Iterative(Graph G, Vertex v) {
        dfsiStack.push(v);
        while(!dfsiStack.isEmpty()) {
            Vertex popped = dfsiStack.pop();
            if(dfsiMap.get(popped) == null) {
                dfsiMap.put(popped, true);
                System.out.println("dfsiStack:"+popped.getName());
                for(Vertex w: G.adjacentEdges(popped)) {
                    dfsiStack.push(w);
                }
            }
        }
    }
    
    static Map<Vertex, Boolean> bfsMap = new LinkedHashMap<Vertex, Boolean>();
    static Queue<Vertex> bfsQueue = new LinkedList<Vertex>();
    private static void BFS(Graph G, Vertex v) {
        bfsQueue.add(v);
        while(!bfsQueue.isEmpty()) {
            Vertex head = bfsQueue.remove();
            if(bfsMap.get(head) == null) {
                bfsMap.put(head, true);
                System.out.println("bfsMap:"+head.getName());
                for(Vertex w: G.adjacentEdges(head)) {
                    bfsQueue.add(w);
                }
            }
        }
    }
}

Code Formatted by ToGoTutor

The output of this is:
dfsMap:A
dfsMap:B
dfsMap:D
dfsMap:F
dfsMap:E
dfsMap:C
dfsMap:G
dfsiStack:A
dfsiStack:E
dfsiStack:F
dfsiStack:B
dfsiStack:D
dfsiStack:C
dfsiStack:G
bfsMap:A
bfsMap:B
bfsMap:C
bfsMap:E
bfsMap:D
bfsMap:F
bfsMap:G

Notice, the iterative algorithm processes the children in reverse order because the children are put onto a stack before processed. However, both are depth first algorithms. Here, I use a LinkedHashSet which allows us to quickly verify in the item is in the set (careful as hash values are not unqiue) and also retains order.

The depth first uses a stack (last in, first out) and the breadth first uses a queue (first in, first out).

This post was reposted from http://scottizu.wordpress.com/2014/10/26/back-to-basics-data-structures-and-algorithms/, originally written on October 26th, 2014.