Algorithm - BFS

https://xuezhashuati.blogspot.com/2017/03/lintcode-618-search-graph-nodes.html
Given a undirected graph, a node and a target, return the nearest node to given node which value of it is target, return NULL if you can't find.

There is a mapping store the nodes' values in the given parameters.

Notice
It's guaranteed there is only one available solution


Example
2------3 - 5
 \        |     |
   \      |     |
     \    |     |
       \  |     |
         1 -- 4
Give a node 1, target is 50

there a hash named values which is [3,4,10,50,50], represent:
Value of node 1 is 3
Value of node 2 is 4
Value of node 3 is 10
Value of node 4 is 50
Value of node 5 is 50

Return node 4
从当前节点开始BFS。比较每一个遍历的点mapping出来的值是不是target。如果是就return。如果不是，把这个点的邻居都加入queue里。注意加的时候先检测一下要加的点有没有被遍历过。

 * class UndirectedGraphNode {
 *     int label;
 *     ArrayList<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { 
 *         label = x; neighbors = new ArrayList<UndirectedGraphNode>(); 
 *     }
 * };

    public UndirectedGraphNode searchNode(ArrayList<UndirectedGraphNode> graph,
                                          Map<UndirectedGraphNode, Integer> values,
                                          UndirectedGraphNode node,
                                          int target) {
        // Write your code here
        
        if (node == null) {
            return null;
        }
        
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        queue.offer(node);
        
        HashSet<UndirectedGraphNode> hash = new HashSet<>();
        hash.add(node);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                UndirectedGraphNode currNode = queue.poll();
                if (values.get(currNode) == target) {
                    return currNode;
                }
                else {
                    for (UndirectedGraphNode nei : currNode.neighbors) {
                        if (!hash.contains(nei)) {
                            queue.offer(nei);
                            hash.add(nei);
                        }
                    }
                }
            }
        }
        
        return null;
    }

http://www.cnblogs.com/aprilyang/p/6504050.html

看了下答案还是很简洁的，每个点都会入queue一次，所以可以在外层判断。可是只是可能会慢一点点。

    public UndirectedGraphNode searchNode(ArrayList<UndirectedGraphNode> graph,
                                          Map<UndirectedGraphNode, Integer> values,
                                          UndirectedGraphNode node,
                                          int target) {
        Queue<UndirectedGraphNode> q = new LinkedList<>();
        q.offer(node);
        HashSet<UndirectedGraphNode> visited = new HashSet<>();
        visited.add(node);
        while (!q.isEmpty()) {
            UndirectedGraphNode n = q.poll();
            if (values.get(n) == target) {
                    return n;
            }
            for (UndirectedGraphNode subN : n.neighbors) {
                if (visited.contains(subN)) {
                    continue;
                }
                if (values.get(subN) == target) {
                    return subN;
                }
                q.offer(subN);
                visited.add(subN);
            }
        }
        return null;
    }
}

http://blog.hyoung.me/cn/2017/03/breadth-first-search/

通常而言，BFS 相关的问题可以粗略地分为四大类：

1. 遍历（Traversal）
2. 连通块（Connected Components）
3. 最短路径（Shortest Path）
4. 拓扑排序（Topological Sorting）

BFS 最基本的功能就是搜索，因此对图的遍历是一个使用 BFS 常见的场景。对于这类问题，BFS 和 DFS 通常都可以完成任务，但在都能使用的情况下我们应该尽量使用 BFS，因为 DFS 栈中递归函数的积累有可能导致爆栈，这也是使用 DFS 最大的弊端。

Clone Graph
参见 LintCode 137。
这道题要求我们对一个图进行深度拷贝（Deep Copy）。我们可以先拷贝所有的节点，再拷贝所有的边。

Remove Substrings

给定一个长字符串s和一堆短字符串，要求从长字符串中删掉所有的短字符串使得最后剩下的字符串最短。比如，当s = “ccdaabcdbb”，短字符串为["ab", "cd"]时，最后剩下的最短字符串长度为2。删除顺序为：ccdaabcdbb -> ccdacdbb -> cabb -> cb。

这里最关键的问题就是删除短字符串的顺序会影响到最终结果，因此这就变成了一道搜索问题：我们每次删掉一个短字符串，把剩下的字符串当做一个子问题继续进行搜索，在搜索过程中记录所得到的最短字符串长度即可。同时为了避免重复搜索，我们用一个哈希表来记录已经搜索过的字符串。

常而言，一个连通块（Connected Components）是指无向图中的一个子图（Subgraph），其中任意两个节点之间都至少存在一条路径

对于连通块问题，我们同样即可以使用 BFS，也可以使用 DFS，但还是应尽量使用 BFS。除此之外，并查集（Union-Find）也是一种常用的算法，而且有时会更优一点。

Connected Components

参见 LintCode 431。

这道题要求我们找到无向图中的连通块个数。我们可以遍历所有节点，遇到没有访问过的节点用 BFS 进行拓展即可。

Graph Valid Tree

参见 LintCode 178。

给定一个无向图，包括n个节点，分别用0到n-1进行标记，和一个边的数组，要求判断这个无向图是否是一棵树。

若一个无向图是一棵树，则其需要满足两个条件：

# nodes = # edges + 1

不成环

第一个条件很好判断，比较节点数和边数就可以了。重点就在判断是否存在环了。我们可以发现，在满足第一个条件后，若图中存在环，则图中至少存在两个连通块，这意味着我们从任意一个节点出发开始遍历，最后都必然无法遍历整个图。因此只需要任选一个节点出发遍历，若最后遍历得到的联通图中的节点数目小于图中节点总数目，图中就存在环了。

http://blog.hyoung.me/cn/2017/03/breadth-first-search-ii/
Shortest Path in Graph
因为 BFS 的搜索过程类似于水波的扩散过程，是按照起始位置一层层地往外扩展的，所以 BFS 就十分合适于处理最短路径的相关问题了。

拓扑排序（Topological Sorting）是一种按照有向图中节点依赖关系进行「排序」的算法。对于「排序」后的任意节点，它都不依赖于位于它之前的任何节点。换句话说，当一个节点没有其他节点指向它，即入度（in-degree）为0时，它就可以被使用或执行。因此，这个算法的思路也比较清楚了，统计每个节点的入度，然后依次把入度为0的节点从图中「删去」，更新其指向节点的入度，直到图为空。

因为这道题的题设保证了至少存在一种解，因此我们就没有去检查解是否存在了。对于更为一般化的情况而言，即可能不存在解时，我们可以通过比较已经找到的路径中节点数目与图中的节点数目，相符的话即有可行解，不相符的话则说明无解。

http://www.geeksforgeeks.org/distance-nearest-cell-1-binary-matrix/

Given a binary matrix of N x M, containing at least a value 1. The task is to find the distance of nearest 1 in the matrix for each cell. The distance is calculated as |i1 – i2| + |j1 – j2|, where i1, j1 are the row number and column number of the current cell and i2, j2 are the row number and column number of the nearest cell having value 1.

The idea is to use multisource Breadth First Search. Consider each cell as a node and each boundary between any two adjacent cells be an edge. Number each cell from 1 to N*M. Now, push all the node whose corresponding cell value is 1 in the matrix in the queue. Apply BFS using this queue to find the minimum distance of the adjacent node.

1. Create a graph with values assigned from 1 to M*N to all vertices. The purpose is to store position and adjacent information.
2. Create an empty queue.
3. Traverse all matrix elements and insert positions of all 1s in queue.
4. Now do a BFS traversal of graph using above created queue. In BFS, we first explore immediate adjacent of all 1’s, then adjacent of adjacent, and so on. Therefore we find minimum distance.

    void createGraph()

    {

        int k = 1;  // A number to be assigned to a cell

        for (int i = 1; i <= n; i++)

        {

            for (int j = 1; j <= m; j++)

            {

                // If last row, then add edge on right side.

                if (i == n)

                {

                    // If not bottom right cell.

                    if (j != m)

                    {

                        g[k].push_back(k+1);

                        g[k+1].push_back(k);

                    }

                }

                // If last column, then add edge toward down.

                else if (j == m)

                {

                    g[k].push_back(k+m);

                    g[k+m].push_back(k);

                }

                // Else make edge in all four direction.

                else

                {

                    g[k].push_back(k+1);

                    g[k+1].push_back(k);

                    g[k].push_back(k+m);

                    g[k+m].push_back(k);

                }

                k++;

            }

        }

    }

    // BFS function to find minimum distance

    void bfs(bool visit[], int dist[], queue<int> q)

    {

        while (!q.empty())

        {

            int temp = q.front();

            q.pop();

            for (int i = 0; i < g[temp].size(); i++)

            {

                if (visit[g[temp][i]] != 1)

                {

                    dist[g[temp][i]] =

                    min(dist[g[temp][i]], dist[temp]+1);

                    q.push(g[temp][i]);

                    visit[g[temp][i]] = 1;

                }

            }

        }

    }

    // Printing the solution.

    void print(int dist[])

    {

        for (int i = 1, c = 1; i <= n*m; i++, c++)

        {

            cout << dist[i] << " ";

            if (c%m == 0)

                cout << endl;

        }

    }

};

// Find minimum distance

void findMinDistance(bool mat[N][M])

{

    // Creating a graph with nodes values assigned

    // from 1 to N x M and matrix adjacent.

    graph g1(N, M);

    g1.createGraph();

    // To store minimum distance

    int dist[MAX];

    // To mark each node as visited or not in BFS

    bool visit[MAX] = { 0 };

    // Initalising the value of distance and visit.

    for (int i = 1; i <= M*N; i++)

    {

        dist[i] = INT_MAX;

        visit[i] = 0;

    }

    // Inserting nodes whose value in matrix

    // is 1 in the queue.

    int k = 1;

    queue<int> q;

    for (int i = 0; i < N; i++)

    {

        for (int j = 0; j < M; j++)

        {

            if (mat[i][j] == 1)

            {

                dist[k] = 0;

                visit[k] = 1;

                q.push(k);

            }

            k++;

        }

    }

    // Calling for Bfs with given Queue.

    g1.bfs(visit, dist, q);

    // Printing the solution.

    g1.print(dist);

}

http://www.geeksforgeeks.org/count-binary-digit-numbers-smaller-n/

Given a limit N, we need to find out the count of binary digit numbers which are smaller than N. Binary digit numbers are those numbers which contains only 0 and 1 as their digits as 1, 10, 101 etc are binary digit numbers.

One simple way to solve this problem is to loop from 1 till N and check each number whether it is a binary digit number or not. If it is a binary digit number, increase the count of such numbers but this procedure will take O(N) time. We can do better, as we know that count of such numbers will be much smaller than N, we can iterate over binary digit numbers only and check whether generated numbers are smaller than N or not.
In below code, BFS like approach is implemented to iterate over only binary digit numbers. We start with 1 and each time we will push (t*10) and (t*10 + 1) into the queue where t is the popped element, if t is a binary digit number then (t*10) and (t*10 + 1) will also binary digit number, so we will iterate over these numbers only using queue. We will stop pushing elements in the queue when popped number crosses the N.

int countOfBinaryNumberLessThanN(int N)

{

    //  queue to store all intermediate binary

    // digit numbers

    queue<int> q;

    //  binary digits start with 1

    q.push(1);

    int cnt = 0;

    int t;

    //  loop untill we have element in queue

    while (!q.empty())

    {

        t = q.front();

        q.pop();

        //  push next binary digit numbers only if

        // current popped element is N

        if (t <= N)

        {

            cnt++;

            // uncomment below line to print actual

            // number in sorted order

            // cout << t << " ";

            q.push(t * 10);

            q.push(t * 10 + 1);

        }

    }

    return cnt;

}

http://www.geeksforgeeks.org/find-minimum-numbers-moves-needed-move-one-cell-matrix-another/

Given a N X N matrix (M) filled with 1 , 0 , 2 , 3 . Find the minimum numbers of moves needed to move from source to destination (sink) . while traversing through blank cells only. You can traverse up, down, right and left.
A value of cell 1 means Source.
A value of cell 2 means Destination.
A value of cell 3 means Blank cell.
A value of cell 0 means Blank Wall.
Note : there is only single source and single destination.they may be more than one path from source to destination(sink).each move in matrix we consider as ‘1’

int Graph :: BFS(int s, int d)

{

    // Base case

    if (s == d)

        return 0;

    // make initial distance of all vertex -1

    // from source

    int *level = new int[V];

    for (int i = 0; i < V; i++)

        level[i] = -1  ;

    // Create a queue for BFS

    list<int> queue;

    // Mark the source node level[s] = '0'

    level[s] = 0 ;

    queue.push_back(s);

    // it will be used to get all adjacent

    // vertices of a vertex

    list<int>::iterator i;

    while (!queue.empty())

    {

        // Dequeue a vertex from queue

        s = queue.front();

        queue.pop_front();

        // Get all adjacent vertices of the

        // dequeued vertex s. If a adjacent has

        // not been visited ( level[i] < '0') ,

        // then update level[i] == parent_level[s] + 1

        // and enqueue it

        for (i = adj[s].begin(); i != adj[s].end(); ++i)

        {

            // Else, continue to do BFS

            if (level[*i] < 0 || level[*i] > level[s] + 1 )

            {

                level[*i] = level[s] + 1 ;

                queue.push_back(*i);

            }

        }

    }

    // return minimum moves from source to sink

    return level[d] ;

}

bool isSafe(int i, int j, int M[][N])

{

    if ((i < 0 || i >= N) ||

            (j < 0 || j >= N ) || M[i][j] == 0)

        return false;

    return true;

}

// Returns minimum numbers of  moves  from a source (a

// cell with value 1) to a destination (a cell with

// value 2)

int MinimumPath(int M[][N])

{

    int s , d ; // source and destination

    int V = N*N+2;

    Graph g(V);

    // create graph with n*n node

    // each cell consider as node

    int k = 1 ; // Number of current vertex

    for (int i =0 ; i < N ; i++)

    {

        for (int j = 0 ; j < N; j++)

        {

            if (M[i][j] != 0)

            {

                // connect all 4 adjacent cell to

                // current cell

                if ( isSafe ( i , j+1 , M ) )

                    g.addEdge ( k , k+1 );

                if ( isSafe ( i , j-1 , M ) )

                    g.addEdge ( k , k-1 );

                if (j< N-1 && isSafe ( i+1 , j , M ) )

                    g.addEdge ( k , k+N );

                if ( i > 0 && isSafe ( i-1 , j , M ) )

                    g.addEdge ( k , k-N );

            }

            // source index

            if( M[i][j] == 1 )

                s = k ;

            // destination index

            if (M[i][j] == 2)

                d = k;

            k++;

        }

    }

    // find minimum moves

    return g.BFS (s, d) ;

}

http://www.geeksforgeeks.org/find-whether-path-two-cells-matrix/

Given N X N matrix filled with 1 , 0 , 2 , 3 . Find whether there is a path possible from source to destination, traversing through blank cells only. You can traverse up, down, right and left.

• A value of cell 1 means Source.
• A value of cell 2 means Destination.
• A value of cell 3 means Blank cell.
• A value of cell 0 means Blank Wall.

Note : there is only single source and single destination(sink).

Simple solution is that find the source index of cell in matrix and then recursively find a path from source index to destination in matrix .
algorithm :

Find source index in matrix , let we consider ( i , j )
After that Find path from source(1) to sink(2)
FindPathUtil ( M[][N] , i  , j )

   IF we seen M[i][j] == 0 (wall) ||
      ((i, j) is out of matrix index)
     return false ;
   IF we seen destination M[i][j] == 2
     return true ;
   
   Next move in path by traverse all 4 adjacent  
   cell of current cell
   IF (FindPathUtil(M[][N], i+1, j) ||
       FindPathUtil(M[][N], i-1, j) ||
       FindPathUtil(M[][N], i, j+1) ||
       FindPathUtil(M[][N], i, j-1));
      return true ;

 return false ;

Efficient solution (Graph)
The idea is to use Breadth First Search. Consider each cell as a node and each boundary between any two adjacent cells be an edge. so total number of Node is N*N.

 1. Create an empty Graph having N*N node ( Vertex ).
 2. push all  node into graph.
 3. notedown source and sink vertex
 4. Now Appling BFS to find is there is path between
    to vertex or not in  graph
        IF Path found return true
        Else return False

bool Graph :: BFS(int s, int d)

{

    // Base case

    if (s == d)

        return true;

    // Mark all the vertices as not visited

    bool *visited = new bool[V];

    for (int i = 0; i < V; i++)

        visited[i] = false;

    // Create a queue for BFS

    list<int> queue;

    // Mark the current node as visited and

    // enqueue it

    visited[s] = true;

    queue.push_back(s);

    // it will be used to get all adjacent

    // vertices of a vertex

    list<int>::iterator i;

    while (!queue.empty())

    {

        // Dequeue a vertex from queue

        s = queue.front();

        queue.pop_front();

        // Get all adjacent vertices of the

        // dequeued vertex s. If a adjacent has

        // not been visited, then mark it visited

        // and enqueue it

        for (i = adj[s].begin(); i != adj[s].end(); ++i)

        {

            // If this adjacent node is the destination

            // node, then return true

            if (*i == d)

                return true;

            // Else, continue to do BFS

            if (!visited[*i])

            {

                visited[*i] = true;

                queue.push_back(*i);

            }

        }

    }

    // If BFS is complete without visiting d

    return false;

}

bool isSafe(int i, int j, int M[][N])

{

    if ((i < 0 || i >= N) ||

        (j < 0 || j >= N ) || M[i][j] == 0)

        return false;

    return true;

}

// Returns true if there is a path from a source (a

// cell with value 1) to a destination (a cell with

// value 2)

bool findPath(int M[][N])

{

    int s , d ; // source and destination

    int V = N*N+2;

    Graph g(V);

    // create graph with n*n node

    // each cell consider as node

    int k = 1 ; // Number of current vertex

    for (int i =0 ; i < N ; i++)

    {

        for (int j = 0 ; j < N; j++)

        {

            if (M[i][j] != 0)

            {

                // connect all 4 adjacent cell to

                // current cell

                if ( isSafe ( i , j+1 , M ) )

                    g.addEdge ( k , k+1 );

                if ( isSafe ( i , j-1 , M ) )

                    g.addEdge ( k , k-1 );

                if (j< N-1 && isSafe ( i+1 , j , M ) )

                    g.addEdge ( k , k+N );

                if ( i > 0 && isSafe ( i-1 , j , M ) )

                    g.addEdge ( k , k-N );

            }

            // source index

            if( M[i][j] == 1 )

                s = k ;

            // destination index

            if (M[i][j] == 2)

                d = k;

            k++;

        }

    }

    // find path Using BFS

    return g.BFS (s, d) ;

}

http://www.geeksforgeeks.org/minimum-steps-reach-target-knight/

Given a square chessboard of N x N size, the position of Knight and position of a target is given. We need to find out minimum steps a Knight will take to reach the target position.