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里。注意加的时候先检测一下要加的点有没有被遍历过。
http://blog.hyoung.me/cn/2017/03/breadth-first-search/
Clone Graph
参见 LintCode 137。
这道题要求我们对一个图进行深度拷贝(Deep Copy)。我们可以先拷贝所有的节点,再拷贝所有的边。
http://blog.hyoung.me/cn/2017/03/breadth-first-search-ii/
Shortest Path in Graph
因为 BFS 的搜索过程类似于水波的扩散过程,是按照起始位置一层层地往外扩展的,所以 BFS 就十分合适于处理最短路径的相关问题了。
拓扑排序(Topological Sorting)是一种按照有向图中节点依赖关系进行「排序」的算法。对于「排序」后的任意节点,它都不依赖于位于它之前的任何节点。换句话说,当一个节点没有其他节点指向它,即入度(in-degree)为
http://www.geeksforgeeks.org/distance-nearest-cell-1-binary-matrix/
http://www.geeksforgeeks.org/count-binary-digit-numbers-smaller-n/
http://www.geeksforgeeks.org/find-minimum-numbers-moves-needed-move-one-cell-matrix-another/
http://www.geeksforgeeks.org/find-whether-path-two-cells-matrix/
http://www.geeksforgeeks.org/minimum-steps-reach-target-knight/
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; } }
通常而言,BFS 相关的问题可以粗略地分为四大类:
- 遍历(Traversal)
- 连通块(Connected Components)
- 最短路径(Shortest Path)
- 拓扑排序(Topological Sorting)
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
不成环
第一个条件很好判断,比较节点数和边数就可以了。重点就在判断是否存在环了。我们可以发现,在满足第一个条件后,若图中存在环,则图中至少存在两个连通块,这意味着我们从任意一个节点出发开始遍历,最后都必然无法遍历整个图。因此只需要任选一个节点出发遍历,若最后遍历得到的联通图中的节点数目小于图中节点总数目,图中就存在环了。
Shortest Path in Graph
因为 BFS 的搜索过程类似于水波的扩散过程,是按照起始位置一层层地往外扩展的,所以 BFS 就十分合适于处理最短路径的相关问题了。
拓扑排序(Topological Sorting)是一种按照有向图中节点依赖关系进行「排序」的算法。对于「排序」后的任意节点,它都不依赖于位于它之前的任何节点。换句话说,当一个节点没有其他节点指向它,即入度(in-degree)为
0
时,它就可以被使用或执行。因此,这个算法的思路也比较清楚了,统计每个节点的入度,然后依次把入度为0
的节点从图中「删去」,更新其指向节点的入度,直到图为空。
因为这道题的题设保证了至少存在一种解,因此我们就没有去检查解是否存在了。对于更为一般化的情况而言,即可能不存在解时,我们可以通过比较已经找到的路径中节点数目与图中的节点数目,相符的话即有可行解,不相符的话则说明无解。
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.
- Create a graph with values assigned from 1 to M*N to all vertices. The purpose is to store position and adjacent information.
- Create an empty queue.
- Traverse all matrix elements and insert positions of all 1s in queue.
- 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);
}
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.
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;
}
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’
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) ;
}
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 :
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.
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) ;
}
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.