Graphs Problems (networks, routes/paths, scheduling…etc)

ref –

https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/
https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/
https://stackoverflow.com/questions/14720691/whats-the-purpose-of-bfs-and-dfs

BFS and DFS are graph search algorithms that can be used for a variety of different purposes. Many problems in computer science can be thought of in terms of graphs. For example, analyzing networks, mapping routes, and scheduling are graph problems. Graph search algorithms like breadth-first search are useful for analyzing and solving graph problems.

One common application of the two search techniques is to identify all nodes that are reachable from a given starting node. For example, suppose that you have a collection of computers that each are networked to a handful of other computers. By running a BFS or DFS from a given node, you will discover all other computers in the network that the original computer is capable of directly or indirectly talking to. These are the computers that come back marked.

BFS specifically can be used to find the shortest path between two nodes in an unweighted graph. Suppose, for example, that you want to send a packet from one computer in a network to another, and that the computers aren’t directly connected to one another. Along what route should you send the packet to get it to arrive at the destination as quickly as possible? If you run a BFS and at each iteration have each node store a pointer to its “parent” node, you will end up finding route from the start node to each other node in the graph that minimizes the number of links that have to be traversed to reach the destination computer.

DFS is often used as a subroutine in more complex algorithms. For example, Tarjan’s algorithm for computing strongly-connected components is based on depth-first search. Many optimizing compiler techniques run a DFS over an appropriately-constructed graph in order to determine in which order to apply a specific series of operations. Depth-first search can also be used in maze generation: by taking a grid of nodes and linking each node to its neighbors, you can construct a graph representing a grid. Running a random depth-first search over this graph then produces a maze that has exactly one solution.

This is by no means an exhaustive list. These algorithms have all sorts of applications, and as you start to explore more advanced algorithms you will often find yourself relying on DFS and BFS as building blocks. It’s similar to sorting – sorting by itself isn’t all that interesting, but being able to sort a list of values is enormously useful as a subroutine in more complex algorithms.

We use graphs to present connected nodes.

Graph consist of nodes and edges.

Adjacent – if two nodes are directed connected. They are neighbors.

If it’s a directed graph, and John has an arrow towards Bob, then John is adjacent to Bob. But opposite not true.

Edges also have a weight. If two people interact a lot, they can have a higher weighted edge.

Finding two shortest path to two nodes.

Adjacency Matrix

An adjacency list is a collection of unordered lists used to represent a finite graph.

Each list describes the set of neighbors of a vertex in the graph.

Let’s do Depth First Search on our example graph

The idea is to go forward in depth while there is any such possibility. If not then backtrack.

Whenever we push an unvisited node, we print it.

Before we start, there are two assumptions:

– we start at node C
– nodes are inserted in alphabetical order.

We use a stack.

So we start at C. We push C onto our stack, and print it.

stack: C
output: C

C is connected to three nodes, A, B, and D. We do this alphabetically so we push A onto the stack, and print it.

stack: C A
output: C A

At A, we have two nodes, B and E. We push B onto our stack, and print it.

stack: C A B
output: C A B

B has one neighbor E. So we push E onto the stack, and print it.

stack: C A B E
output: C A B E

Since E has no connecting neighbors, we pop it.

stack: C A B
output: C A B E

We are now at B. B’s only neighbor of E has already been visited so we pop B.

stack: C A
output: C A B E

A’s neighbors B and E have all been visited. So we push A.

stack: C
output: C A B E

Now we’re at C.

C’s A has been visited, and B has also been visited. But B is unvisited so we push D onto the stack, then print it.

stack: C D
output: C A B E D

D has no unvisited nodes so we pop it.

stack: C
output: C A B E D

C has no unvisited nodes so we pop.

stack:
output: C A B E D

Stack is empty so we’re done.

Source Code

We create a list that has a tail pointing to the latest item we insert. That way, everything is order. Whatever you added first, will be processed first as head is referencing it. Tail will always reference the very last item you add.

let l = console.log;

function Node(data, next) {

this.data = data;

this.next = next;

this.print = function(){

console.log(`Node - ${this.data}`);

}

let createLinkedListInstance = (function LinkedList() {

let head = null;

let tail = null;

let iterator = null;

return new class LinkedList {

add = function(value) {

if (!head && !tail) {

head = new Node(value, null);

tail = head;

iterator = head;

} else {

tail.next = new Node(value, null);

tail = tail.next;

}

print = () => {

for (let tmp = head; tmp != null; tmp = tmp.next) {

tmp.print();

}

next = () => {

if (iterator) {

let tmp = iterator;

iterator = iterator.next;

return tmp;

} else {

return null;

}

hasNext = () => {

return iterator ? true : false;

}

resetIterator = () => {

iterator = head;

}

});

Create a Graph with x number of nodes.

let createGraphInstance = (function(numOfVertices) {

// private properties

let output = [];

console.log(`create a graph with ${numOfVertices} nodes`);

var numOfNodes = numOfVertices;

var adj = [];

We use recursion on the local stack frame in order to simulate a stack.

Each list that is referenced by an Adj[key] is pushed onto the stack. As we process each node down this list, we get more keys, say key2.

We then push list referenced by Adj[key2] onto the local stack frame by recursively calling the function. We keep doing this until we exhaust this list.

Then the function gets popped off the local stack frame.

let _dfsUtil = function(fromNodeKey, visitedArr) {

l(`PUSH adj[${fromNodeKey}] onto stack`);

output.push(fromNodeKey);

visitedArr[fromNodeKey] = true;

let list = adj[fromNodeKey];

while (list && list.hasNext()) {

let node = list.next();

let nodeKey = node.data;

if (!visitedArr[nodeKey]) {

_dfsUtil(nodeKey, visitedArr);

} else {

l(`node ${fromNodeKey} - `, `already processed ${nodeKey}`);

}

l(`POP adj[${fromNodeKey}] from stack`);

} //

We look at our graph, and add the neighbors that are connected to our node. We always do this before we run the DFS function.

return new class Graph {

// public, prototype

addEdge = function(fromNodeKey, toNodeKey) {

let list = adj[fromNodeKey];

if (!list) {

l('creating new');

adj[fromNodeKey] = createLinkedListInstance();

if (toNodeKey) {

adj[fromNodeKey].add(toNodeKey);

}

} else {

list.add(toNodeKey);

}

} //

After adding all the nodes, and specifying how many nodes we have in the constructor, we are ready to call this function.

// recursion is the stack

dfs(nodeNumber) {

l(`starting from node ${nodeNumber}`);

let visited = new Array(numOfNodes);

_dfsUtil(nodeNumber, visited);

}

print our adjacency list and the lists that they contain

print = () => {

l(`-- printing --`);

let allKeys = Object.keys(adj);

l(allKeys);

for (const key of allKeys) {

l(`------ ${key} --------`);

adj[key].print();

}

print the output array

printOutput = () => {

l(output);

}

});

let g = createGraphInstance(5);

g.addEdge('a', 'b');

g.addEdge('a', 'e');

g.addEdge('b', 'e');

g.addEdge('c', 'a');

g.addEdge('c', 'b');

g.addEdge('c', 'd');

g.addEdge('d', 'e');

g.addEdge('e');

g.print();

// let's do this starting from node 2

g.dfs('c');

g.printOutput();

Breadth First Search on the graph

The trick is that you visit a dequeued node. If that node is NOT visited, we add its neighbors to the queue. If that node HAS ALREADY BEEN visited, we keep dequeueing.

We start at C, so we add C to the queue.

queue: [C]

We remove C from the queue and visit it.

output: C
queue: []

We now must add C’s unvisited neighbors tot he queue (in alphabetical order).

output: C
queue: [A, B, D]

We visit A, and remove it from the queue.

output: C A
queue: [B, D]

Since we visited A, we must add A’s unvisited neighbors to the queue. Those neighbors are B and E.

output: C A
queue: [B, D, B, E]

We visit B, and dequeue it.

output: C A B
queue: [D, B, E]

Since we visited B, let’s look at its neighbors. It has one neighbor E. Let’s add it to the queue.

output: C A B
queue: [D, B, E, E]

No we visit D and print. Then dequeue it.

output: C A B D
queue: [B, E, E].

since we visited D, we must add its unvisited neighbors E.

output: C A B D
queue: [B, E, E, E]

Now we dequeue B, but we see that we have already visited it.

output: C A B D
queue: [E, E, E]

We then dequeue E. It has not been visited so we output it.

output: C A B D E
queue: [E, E]

E has no neighbors so we don’t add anything to the queue.

We then dequeue again. Has no neighbors so we continue to dequeue.

output: C A B D E
queue: [E]

Finally, we dequeue the last E. It has already been printed. And it has no neighbors. The queue is now empty so we’re done.

output: C A B D E
queue: []

We first create a queue.

let createQueue = (function Queue() {

let head = null;

let tail = null;

return new class Queue {

enqueue = value => {

if (!head && !tail) {

head = new Node(value, null);

tail = head;

} else {

tail.next = new Node(value, null);

tail = tail.next;

}

dequeue = () => {

let tmp = head;

head = head.next;

if (!head) { tail = null; }

return tmp;

}

size = () => {

let tmp = head;

let count = 0;

while (tmp) {

count++;

tmp = tmp.next;

}

return count;

}

});

We use the Linked List from the previous example.

So with Breadth first traversal of the graph, the trick is that we start at the initial node.

We then take all the neighbors of that node and add them to the queue. Once we added all those neighbors, we pop the initial node, and then move on to process the next one in queue.

let createBreadthFirstSearchForGraph = (function(numOfVertices) {

// private here

let output = [];

var numOfNodes = numOfVertices;

var adj = [];

return new class BFSGraph {

addEdge = function(fromNodeKey, toNodeKey) {

let list = adj[fromNodeKey];

if (!list) {

l('creating new');

adj[fromNodeKey] = createLinkedListInstance();

if (toNodeKey) {

adj[fromNodeKey].add(toNodeKey);

}

} else {

list.add(toNodeKey);

}

} //

So as you can see, we give it an initial key to start from. In our case it is ‘c’. So fromNodeKey is ‘c’.
We then keep track if they are visited or not via a visited array.

Initially, we only have one node in the queue. So we start processing the while loop. We pop the ‘c’ node and then push all the nodes from its neighbors via an inner while loop.

In this inner loop, we check to see if the key has been processed by associative array access on the visited array. If it has not been visited, we mark it visited and then add it onto our queue to be processed later.

bfs = fromNodeKey => {

let visited = new Array(numOfNodes);

let queue = createQueue();

visited[fromNodeKey] = true;

l(visited);

queue.enqueue(fromNodeKey);

l(queue);

let s;

while (queue.size() != 0) {

// 2) we then process them one by one

// base case is whatever node you want to start from

s = queue.dequeue();

output.push(s.data);

let list = adj[s.data];

// 1) we push all neighbors of current node onto the queue

while (list.hasNext()) {

let node = list.next();

let nodeKey = node.data;

if (!visited[nodeKey]) {

visited[nodeKey] = true;

queue.enqueue(nodeKey);

}

....

}

});

Source Code

Depth First Graph Traversal

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

let l = console.log;

function Node(data, next) {

this.data = data;

this.next = next;

this.print = function(){

console.log(`Node - ${this.data}`);

}

let createLinkedListInstance = (function LinkedList() {

let head = null;

let tail = null;

let iterator = null;

return new class LinkedList {

add = function(value) {

if (!head && !tail) {

head = new Node(value, null);

tail = head;

iterator = head;

} else {

tail.next = new Node(value, null);

tail = tail.next;

}

print = () => {

for (let tmp = head; tmp != null; tmp = tmp.next) {

tmp.print();

}

next = () => {

if (iterator) {

let tmp = iterator;

iterator = iterator.next;

return tmp;

} else {

return null;

}

hasNext = () => {

return iterator ? true : false;

}

resetIterator = () => {

iterator = head;

}

});

let createGraphInstance = (function(numOfVertices) {

// private properties

let output = [];

console.log(`create a graph with ${numOfVertices} nodes`);

var numOfNodes = numOfVertices;

var adj = [];

let _dfsUtil = function(fromNodeKey, visitedArr) {

l(`PUSH adj[${fromNodeKey}] onto stack`);

output.push(fromNodeKey);

visitedArr[fromNodeKey] = true;

let list = adj[fromNodeKey];

while (list && list.hasNext()) {

let node = list.next();

let nodeKey = node.data;

if (!visitedArr[nodeKey]) {

_dfsUtil(nodeKey, visitedArr);

} else {

l(`node ${fromNodeKey} - `, `already processed ${nodeKey}`);

}

l(`POP adj[${fromNodeKey}] from stack`);

} //

return new class Graph {

// public, prototype

addEdge = function(fromNodeKey, toNodeKey) {

let list = adj[fromNodeKey];

if (!list) {

l('creating new');

adj[fromNodeKey] = createLinkedListInstance();

if (toNodeKey) {

adj[fromNodeKey].add(toNodeKey);

}

} else {

list.add(toNodeKey);

}

} //

// recursion is the stack

dfs(nodeNumber) {

l(`starting from node ${nodeNumber}`);

let visited = new Array(numOfNodes);

_dfsUtil(nodeNumber, visited);

}

print = () => {

l(`-- printing --`);

let allKeys = Object.keys(adj);

l(allKeys);

for (const key of allKeys) {

l(`------ ${key} --------`);

adj[key].print();

}

printOutput = () => {

l(output);

}

});

let g = createGraphInstance(5);

g.addEdge('a', 'b');

g.addEdge('a', 'e');

g.addEdge('b', 'e');

g.addEdge('c', 'a');

g.addEdge('c', 'b');

g.addEdge('c', 'd');

g.addEdge('d', 'e');

g.addEdge('e');

g.print();

// let's do this starting from node 2

g.dfs('c');

g.printOutput();

Breadth First Traversal for Graphs

Linked List used is same as above.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

let createQueue = (function Queue() {

let head = null;

let tail = null;

return new class Queue {

enqueue = value => {

if (!head && !tail) {

head = new Node(value, null);

tail = head;

} else {

tail.next = new Node(value, null);

tail = tail.next;

}

dequeue = () => {

let tmp = head;

head = head.next;

if (!head) { tail = null; }

return tmp;

}

size = () => {

let tmp = head;

let count = 0;

while (tmp) {

count++;

tmp = tmp.next;

}

return count;

}

});

let createBreadthFirstSearchForGraph = (function(numOfVertices) {

// private here

let output = [];

var numOfNodes = numOfVertices;

var adj = [];

return new class BFSGraph {

addEdge = function(fromNodeKey, toNodeKey) {

let list = adj[fromNodeKey];

if (!list) {

l('creating new');

adj[fromNodeKey] = createLinkedListInstance();

if (toNodeKey) {

adj[fromNodeKey].add(toNodeKey);

}

} else {

list.add(toNodeKey);

}

} //

bfs = fromNodeKey => {

let visited = new Array(numOfNodes);

let queue = createQueue();

visited[fromNodeKey] = true;

l(visited);

queue.enqueue(fromNodeKey);

l(queue);

let s;

while (queue.size() != 0) {

// 2) we then process them one by one

// base case is whatever node you want to start from

s = queue.dequeue();

output.push(s.data);

let list = adj[s.data];

// 1) we push all neighbors of current node onto the queue

while (list.hasNext()) {

let node = list.next();

let nodeKey = node.data;

if (!visited[nodeKey]) {

visited[nodeKey] = true;

queue.enqueue(nodeKey);

}

print = () => {

l(`-- printing --`);

let allKeys = Object.keys(adj);

l(allKeys);

for (const key of allKeys) {

l(`------ ${key} --------`);

adj[key].print();

}

printOutput = () => {

l(output);

}

});

let b = createBreadthFirstSearchForGraph(5);

b.addEdge('a', 'b');

b.addEdge('a', 'e');

b.addEdge('b', 'e');

b.addEdge('c', 'a');

b.addEdge('c', 'b');

b.addEdge('c', 'd');

b.addEdge('d', 'e');

b.addEdge('e');

b.print();

b.bfs('c');

b.printOutput();