Graph

Transform one word into another by changing only one letter at a time

Posted on July 24, 2014 (Last modified on August 7, 2020) | 2 minutes | Kinshuk Chandra

Problem Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only one letter at a time. The new word you get in each step must be in the dictionary. EXAMPLE Input: DAMP, LIKE Output: DAMP -> LAMP -> LIMP -> LIME -> LIKE Solution Try thinking this problem in terms of graphs: Consider all words in a dictionary as vertices, and insert an edge between each two vertices that differ by only one letter. [Read More]

The Celebrity Problem

Posted on April 2, 2014 (Last modified on August 7, 2020) | 3 minutes | Kinshuk Chandra

Problem In a party of N people, only one person is known to everyone. Such a person may be present in the party, if yes, (s)he doesn’t know anyone in the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in minimum number of questions. Solution We can describe the problem input as an array of numbers/characters representing persons in the party. [Read More]

Graph kodeknight recursion celebrity stack

Find if there is a path between two vertices in a directed graph

Posted on February 9, 2014 (Last modified on August 7, 2020) | 1 minutes | Kinshuk Chandra

Why do you need to have 3 states (“Visited, &… Anonymous - Aug 4, 2016Why do you need to have 3 states (“Visited, “Unvisited”, and “Visiting”)? It seems like we do the same thing - adding the node to the queue - if it’s unvisited, but there is no functional distinction between visited and visiting (in either state we skip it - we won’t enqueue it and we won’t check against it). [Read More]

Graph kodeknight connectivity BFS Directed Graph CrackingTheCodingInterview

Find if there is a path between two vertices in a directed graph

Posted on February 9, 2014 (Last modified on August 7, 2020) | 2 minutes | Kinshuk Chandra

Problem : Given a Directed Graph and two vertices in it, check whether there is a path from the first given vertex to second. Solution We have already seen solution to connectivity in undirected graph via bfs. Now lets see it on directed graph. BFS to check the connectivity public enum State { Unvisited, Visited, Visiting; } public static boolean search(Graph g, Node start, Node end) { LinkedList<Node> q = new LinkedList<Node>(); // operates as Stack for (Node u : g. [Read More]

Graph kodeknight connectivity BFS Directed Graph CrackingTheCodingInterview

Maximum weight independent set (WIS) graph problem using DP

Posted on November 5, 2013 (Last modified on August 7, 2020) | 7 minutes | Kinshuk Chandra

Input - A path graph G = (V,E) with non - negative weights on vertices eg.Consider the graph with vertex weights - 1,4,5,4 Desired output - subset of non-adjacent vertices - an independent set of maximum total weights. Solutions Brute force polynomial time, so lets do better. greedy approach Greedy algos are easy to implement but are sometimes not correct. To apply greedy approach here we have to iteratively choose the max-weight vertex not adjacent to any previously chosen vertex. [Read More]

Graph kodeknight Dynamic Programming DP

BFS (Breadth first search) on Graph

Posted on August 25, 2013 (Last modified on August 7, 2020) | 2 minutes | Kinshuk Chandra

Algorithm Starting at some arbitrarily chosen vertex s (s stands for start vertex) , we mark v so that we know we’ve visited it, process v, and then visit i.e. mark the vertex as visited and process all of v’s neighbors. Now that we’ve visited and processed all of v’s neighbors, we need to visit and process all of v’s neighbors neighbors Pseudocode BFS(graph G, vertex s)

all nodes initially unexplored

\-mark s as explored let Q = queue data structure, initialized with s while (Q not empty) remove the first node of Q, call it v for each edge (v, w): if w is unexplored mark w as explored add w to Q (at the end) We visit each node only once and each edge at most twice (for edge(v, w), we might encounter it when we’re at node v and at node w). [Read More]

Graph kodeknight queue BFS graph-search Undirected Graph

DFS (Depth first search) for graph

Posted on August 25, 2013 (Last modified on August 7, 2020) | 2 minutes | Kinshuk Chandra

What is dfs? This algorithm explores aggressively and backtracks only when necessary. This is similar to how we play a maze game. To code DFS iteratively, we can mimic BFS , but use a Stack instead of a Queue. Another way to code this would be to do it recursively. DFS is very naturally phased as recursive example. We will see both of implementation later. DFS(graph G, vertex s) mark s as explored for every edge (s, v): if v unexplored DFS(G, v) Example : Consider the graph: [Read More]

Graph kodeknight time complexity DFS graph-search

Dijkstra's algorithm for equal weight edges using BFS

Posted on August 25, 2013 (Last modified on August 7, 2020) | 3 minutes | Kinshuk Chandra

This is the application of BFS (breadth first search) dist(v) = fewest number of edges on path s to v. Here is the pseudocode: Initialize dist(v) = {0 if v=s, infinity if v != s} foreach vertex v in all vertices { if(v==s) dist(v) = 0; else dist(v) = infinity; } Now apply BFS, and hen considering edge (v, w), if w is unexplored, then set dist(w) = dist(v)+1, keeping rest of the BFS same. [Read More]

Graph kodeknight BFS graph-search

Random Contraction Algorithm

Posted on August 24, 2013 (Last modified on August 7, 2020) | 3 minutes | Kinshuk Chandra

This algorithm was designed by Karger in 1990, as phd student at stanford. This algorithm is used to solve the min cut problem, which is : Input - An undirected graph G = (V,E) , (note that parallel edges are allowed) Goal - Tom compute a cut with fewest number of crossing edges (a min cut) Karger’s Algorithm We will have just one mail loop, and algorithm terminates when only 2 vertices are remaining. [Read More]

Graph kodeknight incomplete

Graph Representations

Posted on August 24, 2013 (Last modified on August 7, 2020) | 2 minutes | Kinshuk Chandra

We have already discussed what are graphs here. Now graph can be represented in 2ways: Adjacency matrix Adjacency list Adjacency Matrix Undirected graph Represent G by a nXn, n being number of vertices 0-1 matrix A, where Aij = 1 for every edge between 2 nodes. Undirected graph with parallel edges Aij = b*1 where b is number of parallel edges between i and j. Weighted Undirected graph [Read More]

Graph kodeknight incomplete