Tags » BF's

Graphs & Trees - Shortest Path (BFS, Dijkstra, Bellman Ford)

Before exploring this topic, it will help if you go through my previous blog on graph basics which covers the different types of graphs, their representations & different searching techniques. 2,132 more words

Algorithm

Leetcode--Word Ladder

The Problem:

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

  1. Only one letter can be changed at a time…
  2. 408 more words
Tech Interview

Scalability and Memory Limits 5

Problem:

If you were designing a web crawler, how would you avoid getting into infinite loops?

Analysis:

How can a web crawler travel from one page to another? 148 more words

Technical And Interview And Data Science

ACM ICPC Naga 2014 – Problem F: Diameter of a Tree

Dr. Manalastas, the author of this problem, is my friend in Facebook. Since my second year in college, I have seen him as someone who I should have a picture with. 982 more words

UVa Problems

Graph Algorithms - a revision of all the basic ones.

Hello friends! This post will be a short review of the the most common and basic algorithms for undirected graphs. 2,117 more words

Algorithms

Breadth First Search (BFS): Finding Visited Path From a Source to Destination

BreadthFirstPaths.java

package com.graph;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BreadthFirstPaths {
    private boolean[] marked; // Is a shortest path to this vertex known?
    private int[] edgeTo; // last vertex on known path to this vertex
    private final int s; // source

    public BreadthFirstPaths(Graph G, int s) {
        marked = new boolean;
        edgeTo = new int;
        this.s = s;
        bfs(G, s);
    }

    private void bfs(Graph G, int s) {
        Queue<Integer> queue = new LinkedList<Integer>();
        marked[s] = true;
        queue.add(s);
        while (!queue.isEmpty()) {
            int v = queue.peek();
            queue.poll();
            for (int w : G.adj(v))
                if (!marked[w]) {
                    edgeTo[w] = v; // save last edge on a shortest path,
                    marked[w] = true; // mark it because path is known,
                    queue.add(w);
                }
        }
    }

    public boolean hasPathTo(int v) {
        return marked[v];
    }

    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v))
            return null;
        Stack<Integer> path = new Stack<Integer>();
        for (int x = v; x != s; x = edgeTo[x])
            path.push(x);
        path.push(s);
        return path;
    }
} 25 more words
Graph

Hard Question 10

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. 158 more words

Technical And Interview And Data Science