# Graphs HackerRank Solution Guide

### 1. DFS Graph Traversal
What is the result of running preorder DFS starting on node C?

**Note:** ties are broken alphabetically, so if node A had both node B and node C as neighbors, node B would be added to the stack first

**Solution: CBAFEDG**

### 2. BFS Graph Traversal

BFS traversal, using C as the root node?

**Note:** ties are broken alphabetically, so if node A had both node B and node C as neighbors, node B would be visited first

**Solution: CBGAEFD**

### 3. Topological Sort
What is a valid topological sorting of this graph?

**Solution: HICBAGFED**

### 4. DFS Bug
The following code is meant to run a DFS on a directed graph, but there's a bug. Fix this code snippet so that it is a proper DFS function!

**Solution:**
Python –

def dfs(graph, start):
    visited, stack = list(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            if vertex in graph:
                neighbors = graph[vertex]
                unvisited = [n for n in neighbors if n not in visited]
                stack.extend(unvisited)
                visited.append(vertex)
            else:
                visited.append(vertex)
    return visited

Java -

public static ArrayList<String> dfs(HashMap<String, ArrayList<String>> graph, String start) {
    ArrayList<String> visited = new ArrayList<String>();
    Stack<String> stack = new Stack<String>();
    stack.push(start);

    while(!stack.isEmpty()) {
        String vertex = stack.pop();
        if (!visited.contains(vertex)) {
            if (graph.containsKey(vertex)) {
                ArrayList<String> neighbors = graph.get(vertex);
                ArrayList<String> unvisited = new ArrayList<String>();
                for (String n : neighbors) {
                    if (!visited.contains(n)) {
                        unvisited.add(n);
                    }
                }
                for (String s : unvisited)
                    stack.push(s);
                visited.add(vertex);
            } else {
                visited.add(vertex); 
            }
        }
    }

    return visited;
}

### 5. Tree Checker
Write a function that returns true if a given undirected graph is tree and false otherwise.

For example, the following graph is a tree.
But the following graph is not a tree.

An undirected graph is tree if...
* There is no cycle.
* The graph is connected.

**Solution:**
Python –

def isTree(self):
    # Mark all the vertices as not visited 
    # and not part of recursion stack
    visited = [False] * self.V

    # The call to isCyclicUtil serves multiple 
    # purposes. It returns true if graph reachable 
    # from vertex 0 is cyclcic. It also marks 
    # all vertices reachable from 0.
    if self.isCyclicUtil(0, visited, -1) == True:
        return False

    # If we find a vertex which is not reachable
    # from 0 (not marked by isCyclicUtil(), 
    # then we return false
    for i in range(self.V):
        if visited[i] == False:
            return False

    return True

Java –

Boolean isTree()
{
    // Mark all the vertices as not visited and not part
    // of recursion stack
    Boolean visited[] = new Boolean[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;

    // The call to isCyclicUtil serves multiple purposes
    // It returns true if graph reachable from vertex 0
    // is cyclcic. It also marks all vertices reachable
    // from 0.
    if (isCyclicUtil(0, visited, -1))
        return false;

    // If we find a vertex which is not reachable from 0
    // (not marked by isCyclicUtil(), then we return false
    for (int u = 0; u < V; u++)
        if (!visited[u])
            return false;

    return true;
}

[via GeeksforGeeks](https://www.geeksforgeeks.org/check-given-graph-tree/)

### 6. Alien Language
Given a sorted dictionary (array of words) of an alien language, find order of characters in the language.

Examples:

Input:  words[] = {"baa", "abcd", "abca", "cab", "cad"}
Output: Order of characters is 'b', 'd', 'a', 'c'
Note that words are sorted and in the given language "baa" 
comes before "abcd", therefore 'b' is before 'a' in output.
Similarly we can find other orders.

Input:  words[] = {"caa", "aaa", "aab"}
Output: Order of characters is 'c', 'a', 'b'

**Solution:**
Python –

def printOrder(words, alpha):
    g = Graph(alpha)
    for i in range(len(words) - 1):
        word1 = words[i]
        word2 = words[i+1]
        for j in range(min(len(word1), len(word2))):
            if word1[j] != word2[j]:
                g.addEdge(ord(word1[j]) - ord('a'), ord(word2[j]) - ord('a'))
                break
    return g.topologicalSort()

Java –

 public static ArrayList<Character> getOrder(String[] words, int alpha) {
   // Create a graph with 'alpha' edges
    Graph graph = new Graph(alpha);

    for (int i = 0; i < words.length - 1; i++)
    {
        // Take the current two words and find the first mismatching
        // character
        String word1 = words[i];
        String word2 = words[i+1];
        for (int j = 0; j < Math.min(word1.length(), word2.length()); j++)
        {
            // If we find a mismatching character, then add an edge
            // from character of word1 to that of word2
            if (word1.charAt(j) != word2.charAt(j))
            {
                graph.addEdge(word1.charAt(j) - 'a', word2.charAt(j)- 'a');
                break;
            }
        }
    }
    return graph.topologicalSort();
 }

[via GeeksforGeeks](https://www.geeksforgeeks.org/given-sorted-dictionary-find-precedence-characters/)

### 7. Course Schedule
There are a total of n courses you have to take, labeled from 0 to ```n - 1```.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: ```[0,1]```

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note:
* The input prerequisites is a graph represented by a list of edges, not adjacency matrices.
* You may assume that there are no duplicate edges in the input prerequisites.

**Solution:**
Python -

def canFinish(numCourses, prerequisites):
    graph = [[] for _ in xrange(numCourses)]
    visit = [0 for _ in xrange(numCourses)]
    for x, y in prerequisites:
        graph[x].append(y)
    def dfs(i):
        if visit[i] == -1:
            return False
        if visit[i] == 1:
            return True
        visit[i] = -1
        for j in graph[i]:
            if not dfs(j):
                return False
        visit[i] = 1
        return True
    for i in xrange(numCourses):
        if not dfs(i):
            return False
    return True

[via LeetCode](https://leetcode.com/problems/course-schedule/discuss/58586/Python-20-lines-DFS-solution-sharing-with-explanation)

Java -

public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[][] matrix = new int[numCourses][numCourses]; // i -> j
    int[] indegree = new int[numCourses];
    
    for (int i=0; i<prerequisites.length; i++) {
        int ready = prerequisites[i][0];
        int pre = prerequisites[i][1];
        if (matrix[pre][ready] == 0)
            indegree[ready]++; //duplicate case
        matrix[pre][ready] = 1;
    }
    
    int count = 0;
    Queue<Integer> queue = new LinkedList();
    for (int i=0; i<indegree.length; i++) {
        if (indegree[i] == 0) queue.offer(i);
    }
    while (!queue.isEmpty()) {
        int course = queue.poll();
        count++;
        for (int i=0; i<numCourses; i++) {
            if (matrix[course][i] != 0) {
                if (--indegree[i] == 0)
                    queue.offer(i);
            }
        }
    }
    return count == numCourses;
}

[via LeetCode](https://leetcode.com/problems/course-schedule/discuss/58516/Easy-BFS-Topological-sort-Java)