# Graphs 101: Let’s BFS and DFS.

The 2 most common used representation of graphs are the adjacency list and adjacency matrix.

``````	adjacencyList = {
1: [2, 4],
2: [1, 3],
3: [2, 4],
4: [1, 3]
}
``````

## Graph Traversals

There are two graph traversals: breadth first search and depth first search.

BFS visits the nodes one level at a time. To prevent visiting the same node more than once, we’ll maintain a visited object.

For BFS we utilize a Queue to process the nodes in a First In First Out fashion. The time complexity is O(v+e).

#### Pseudocode

``````/*
pcode:
- create result array variable
- create a queue variable
- create a visited map
- add the starting vertex to the queue & visited map
- while queue is not empty:
- dequeue current vertex
- push current vertex to result array
- loop thru current vertex adjacency list:
- for each adjacent vertex, if vertex is unvisited:
- add vertex to visited map
- enqueue vertex
- return result array
*/
``````

#### Code

``````// code:
function bfs(node) {
const result = [];
const queue = [node];
const visited = {};
visited[start] = true;

while (queue.length) {
let currVertex = queue.pop();
result.push(currVertex);

if (!visited[edges]) {
visited[edges] = true;
queue.unshift(edges);
}
});
}
return results;
}
``````

DFS visits the nodes depth wise so we will use a Stack in order to process Last In First Out fashion.

Starting from a vertex, we’ll push the neighboring vertices to our stack. Whenever a vertex is popped, it is marked visited in our visited object. Its neighboring vertices are pushed to the stack. Since we are always popping a new adjacent vertex, our algorithm will always explore a new level.

We can also use the intrinsic stack calls to implement DFS recursively.

The time complexity is the same as BFS, O(v+e).

#### Pseudocode

``````/*
pcode:
- create a stack array
- create a result array
- create a visited map
- push the starting vertex to the stack & visited map
- while the stack is not empty:
- pop and store the vertex
- push current vertex to result array
- loop thru current vertex adjacency list:
- for each adjacent vertex, if vertex is unvisited:
- add vertex to visited map
- push vertex to stack
- return result array
*/
``````

#### Code

``````// code:
function dfsRecursively(node) {
const result = [];
const visited = {};

function dfs(vertex) {
// base case
if (!vertex) return null;

// set visited
visited[vertex] = true;
result.push(vertex);

// recursive action
if (!visited[edge]) {
return dfs(edge);
}
});
}

dfs(node);

return result;
}

function dfsIterative(node) {
const result = [];
const stack = [node];
const visited = {};
visited[start] = true;

while (stack.length) {
let currVertex = stack.pop();
result.push(currVertex);

if (!visited[edge]) {
visited[edge] = true;
stack.push(edge);
}
});
}

return result;
}
``````

There it is, now let’s see how to use this to solve problems.