Home/Coding Guide/Graphs: Implementations & Problems
⌂ Main Page
Coding Interview Preparation Guide

Graphs: Implementations & Problems

Graph representations (adjacency list), BFS and DFS implementations, word-ladder and knight's-tour examples, and graph interview questions.

Challenges on this page

01Implementation of Graph Overview

Source notebook: Implementation of Graph Overview.ipynb

Implementation of Graph Overview

In this lecture we will implement a simple graph by focusing on the Node class. Refer to this lecture for the solution to the Interview Problem

The graph will be directed and the edges can hold weights.

We will have three classes, a State class, a Node class, and finally the Graph class.

We're going to be taking advantage of two built-in tools here, OrderDict and Enum

Python
from enum import Enum  

class State(Enum):
    unvisited = 1 #White
    visited = 2 #Black
    visiting = 3 #Gray

Now for the Node class we will take advantage of the OrderedDict object in case we want to keep trak of the order keys are added to the dictionary.

Python
from collections import OrderedDict

class Node:

    def __init__(self, num):
        self.num = num
        self.visit_state = State.unvisited
        self.adjacent = OrderedDict()  # key = node, val = weight

    def __str__(self):
        return str(self.num)

Then finally the Graph:

Python
class Graph:

    def __init__(self):
        self.nodes = OrderedDict()  # key = node id, val = node

    def add_node(self, num):
        node = Node(num)
        self.nodes[num] = node
        return node

    def add_edge(self, source, dest, weight=0):
        if source not in self.nodes:
            self.add_node(source)
        if dest not in self.nodes:
            self.add_node(dest)
        self.nodes[source].adjacent[self.nodes[dest]] = weight
Python
g = Graph()
g.add_edge(0, 1, 5)
Python
g.nodes
Output
OrderedDict([(0, <__main__.Node instance at 0x103a761b8>),
             (1, <__main__.Node instance at 0x104dfef80>)])

Great Job!

02Implementation of Adjacency List

Source notebook: Implementation of Adjacency List.ipynb

Implementation of a Graph as an Adjacency List

Using dictionaries, it is easy to implement the adjacency list in Python. In our implementation of the Graph abstract data type we will create two classes: Graph, which holds the master list of vertices, and Vertex, which will represent each vertex in the graph.

Each Vertex uses a dictionary to keep track of the vertices to which it is connected, and the weight of each edge. This dictionary is called connectedTo. The constructor simply initializes the id, which will typically be a string, and the connectedTo dictionary. The addNeighbor method is used add a connection from this vertex to another. The getConnections method returns all of the vertices in the adjacency list, as represented by the connectedTo instance variable. The getWeight method returns the weight of the edge from this vertex to the vertex passed as a parameter.

Python
class Vertex:
    def __init__(self,key):
        self.id = key
        self.connectedTo = {}

    def addNeighbor(self,nbr,weight=0):
        self.connectedTo[nbr] = weight

    def __str__(self):
        return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])

    def getConnections(self):
        return self.connectedTo.keys()

    def getId(self):
        return self.id

    def getWeight(self,nbr):
        return self.connectedTo[nbr]

In order to implement a Graph as an Adjacency List what we need to do is define the methods our Adjacency List object will have:

Python
class Graph:
    def __init__(self):
        self.vertList = {}
        self.numVertices = 0

    def addVertex(self,key):
        self.numVertices = self.numVertices + 1
        newVertex = Vertex(key)
        self.vertList[key] = newVertex
        return newVertex

    def getVertex(self,n):
        if n in self.vertList:
            return self.vertList[n]
        else:
            return None

    def __contains__(self,n):
        return n in self.vertList

    def addEdge(self,f,t,cost=0):
        if f not in self.vertList:
            nv = self.addVertex(f)
        if t not in self.vertList:
            nv = self.addVertex(t)
        self.vertList[f].addNeighbor(self.vertList[t], cost)

    def getVertices(self):
        return self.vertList.keys()

    def __iter__(self):
        return iter(self.vertList.values())

Let's see a simple example of how to use this:

Python
g = Graph()
for i in range(6):
    g.addVertex(i)
Python
g.vertList
Output
{0: <__main__.Vertex instance at 0x10476b680>,
 1: <__main__.Vertex instance at 0x104cce5f0>,
 2: <__main__.Vertex instance at 0x10395d950>,
 3: <__main__.Vertex instance at 0x1039c00e0>,
 4: <__main__.Vertex instance at 0x1039c4e60>,
 5: <__main__.Vertex instance at 0x1039c45f0>}
Python
g.addEdge(0,1,2)
Python
for vertex in g:
    print vertex
    print vertex.getConnections()
    print '\n'
Output
0 connectedTo: [1]
[<__main__.Vertex instance at 0x104cce5f0>]


1 connectedTo: []
[]


2 connectedTo: []
[]


3 connectedTo: []
[]


4 connectedTo: []
[]


5 connectedTo: []
[]

Great Job!

Source notebook: Implementation of Depth First Search.ipynb

Implementation of Depth-First Search

This algorithm we will be discussing is Depth-First search which as the name hints at, explores possible vertices (from a supplied root) down each branch before backtracking. This property allows the algorithm to be implemented succinctly in both iterative and recursive forms. Below is a listing of the actions performed upon each visit to a node.

We will assume a simplified version of a graph in the following form:

Python
graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

Connected Component

The implementation below uses the stack data-structure to build-up and return a set of vertices that are accessible within the subjects connected component. Using Python’s overloading of the subtraction operator to remove items from a set, we are able to add only the unvisited adjacent vertices.

Python
def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited

dfs(graph, 'A')
Output
{'A', 'B', 'C', 'D', 'E', 'F'}

The second implementation provides the same functionality as the first, however, this time we are using the more succinct recursive form. Due to a common Python gotcha with default parameter values being created only once, we are required to create a new visited set on each user invocation. Another Python language detail is that function variables are passed by reference, resulting in the visited mutable set not having to reassigned upon each recursive call.

Python
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    for nxt in graph[start] - visited:
        dfs(graph, nxt, visited)
    return visited

dfs(graph, 'A')
Output
{'A', 'B', 'C', 'D', 'E', 'F'}

Paths

We are able to tweak both of the previous implementations to return all possible paths between a start and goal vertex. The implementation below uses the stack data-structure again to iteratively solve the problem, yielding each possible path when we locate the goal. Using a generator allows the user to only compute the desired amount of alternative paths.

Python
def dfs_paths(graph, start, goal):
    stack = [(start, [start])]
    while stack:
        (vertex, path) = stack.pop()
        for nxt in graph[vertex] - set(path):
            if nxt == goal:
                yield path + [nxt]
            else:
                stack.append((nxt, path + [nxt]))

list(dfs_paths(graph, 'A', 'F'))
Output
[['A', 'B', 'E', 'F'], ['A', 'C', 'F']]
Resources

Source notebook: Implementation of Breadth First Search.ipynb

Implementation of Breadth First Search

An alternative algorithm called Breath-First search provides us with the ability to return the same results as DFS but with the added guarantee to return the shortest-path first. This algorithm is a little more tricky to implement in a recursive manner instead using the queue data-structure, as such I will only being documenting the iterative approach. The actions performed per each explored vertex are the same as the depth-first implementation, however, replacing the stack with a queue will instead explore the breadth of a vertex depth before moving on. This behavior guarantees that the first path located is one of the shortest-paths present, based on number of edges being the cost factor.

We'll assume our Graph is in the form:

Python
graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

Connected Component

Similar to the iterative DFS implementation the only alteration required is to remove the next item from the beginning of the list structure instead of the stacks last.

Python
def bfs(graph, start):
    visited, queue = set(), [start]
    while queue:
        vertex = queue.pop(0)
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(graph[vertex] - visited)
    return visited

bfs(graph, 'A')
Output
{'A', 'B', 'C', 'D', 'E', 'F'}

Paths

This implementation can again be altered slightly to instead return all possible paths between two vertices, the first of which being one of the shortest such path.

Python
def bfs_paths(graph, start, goal):
    queue = [(start, [start])]
    while queue:
        (vertex, path) = queue.pop(0)
        for next in graph[vertex] - set(path):
            if next == goal:
                yield path + [next]
            else:
                queue.append((next, path + [next]))

list(bfs_paths(graph, 'A', 'F'))
Output
[['A', 'C', 'F'], ['A', 'B', 'E', 'F']]

Knowing that the shortest path will be returned first from the BFS path generator method we can create a useful method which simply returns the shortest path found or ‘None’ if no path exists. As we are using a generator this in theory should provide similar performance results as just breaking out and returning the first matching path in the BFS implementation.

Python
def shortest_path(graph, start, goal):
    try:
        return next(bfs_paths(graph, start, goal))
    except StopIteration:
        return None

shortest_path(graph, 'A', 'F')
Output
['A', 'C', 'F']
Resources

05Word Ladder Example Problem

Source notebook: Word Ladder Example Problem.ipynb

Word Ladder Example Code

Below is the Vertex and Graph class used for the Word Ladder example code:

Python
class Vertex:
    def __init__(self,key):
        self.id = key
        self.connectedTo = {}

    def addNeighbor(self,nbr,weight=0):
        self.connectedTo[nbr] = weight

    def __str__(self):
        return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])

    def getConnections(self):
        return self.connectedTo.keys()

    def getId(self):
        return self.id

    def getWeight(self,nbr):
        return self.connectedTo[nbr]
Python
class Graph:
    def __init__(self):
        self.vertList = {}
        self.numVertices = 0

    def addVertex(self,key):
        self.numVertices = self.numVertices + 1
        newVertex = Vertex(key)
        self.vertList[key] = newVertex
        return newVertex

    def getVertex(self,n):
        if n in self.vertList:
            return self.vertList[n]
        else:
            return None

    def __contains__(self,n):
        return n in self.vertList

    def addEdge(self,f,t,cost=0):
        if f not in self.vertList:
            nv = self.addVertex(f)
        if t not in self.vertList:
            nv = self.addVertex(t)
        self.vertList[f].addNeighbor(self.vertList[t], cost)

    def getVertices(self):
        return self.vertList.keys()

    def __iter__(self):
        return iter(self.vertList.values())

Code for buildGraph function:

Python
def buildGraph(wordFile):
    d = {}
    g = Graph()
    
    wfile = open(wordFile,'r')
    # create buckets of words that differ by one letter
    for line in wfile:
        print line
        word = line[:-1]
        print word
        for i in range(len(word)):
            bucket = word[:i] + '_' + word[i+1:]
            if bucket in d:
                d[bucket].append(word)
            else:
                d[bucket] = [word]
    # add vertices and edges for words in the same bucket
    for bucket in d.keys():
        for word1 in d[bucket]:
            for word2 in d[bucket]:
                if word1 != word2:
                    g.addEdge(word1,word2)
    return g

Please reference the video for full explanation!

06Knight's Tour Example Problem

Source notebook: Knight's Tour Example Problem.ipynb

Knight's Tour Code

** Below is th ecode referenced in the video lecture. Please refer to the video lectures for full explanation.**

Python
def knightGraph(bdSize):
    ktGraph = Graph()
    for row in range(bdSize):
        for col in range(bdSize):
            nodeId = posToNodeId(row,col,bdSize)
            newPositions = genLegalMoves(row,col,bdSize)
            for e in newPositions:
                nid = posToNodeId(e[0],e[1],bdSize)
                ktGraph.addEdge(nodeId,nid)
    return ktGraph

def posToNodeId(row, column, board_size):
    return (row * board_size) + column
Python
def genLegalMoves(x,y,bdSize):
    newMoves = []
    moveOffsets = [(-1,-2),(-1,2),(-2,-1),(-2,1),
                   ( 1,-2),( 1,2),( 2,-1),( 2,1)]
    for i in moveOffsets:
        newX = x + i[0]
        newY = y + i[1]
        if legalCoord(newX,bdSize) and \
                        legalCoord(newY,bdSize):
            newMoves.append((newX,newY))
    return newMoves

def legalCoord(x,bdSize):
    if x >= 0 and x < bdSize:
        return True
    else:
        return False
Python
def knightTour(n,path,u,limit):
        u.setColor('gray')
        path.append(u)
        if n < limit:
            nbrList = list(u.getConnections())
            i = 0
            done = False
            while i < len(nbrList) and not done:
                if nbrList[i].getColor() == 'white':
                    done = knightTour(n+1, path, nbrList[i], limit)
                i = i + 1
            if not done:  # prepare to backtrack
                path.pop()
                u.setColor('white')
        else:
            done = True
        return done

07Implement a Graph

Source notebook: Implement a Graph.ipynb

Implement a Graph Class!

That's it!

Best of luck and reference the video lecture for any questions!

You have to fully worked out implementations in the lectures, so make sure to refer to them!

Good Luck!

08Implement Depth First Search Algorithm

Source notebook: Implement Depth First Search Algorithm.ipynb

Implement a Depth First Search Algorithm

For this problem, implement a DFS Algorithm! You can assume that the graph is in the simplified form:

Python
graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

Good Luck!

09Implement Breadth First Search Algorithm

Source notebook: Implement Breadth First Search Algorithm.ipynb

Implement a Breadth First Search Algorithm

For this problem, implement a BFS Algorithm! You can assume that the graph is in the simplified form:

Python
graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

Good Luck!