对于一个有向图,请实现一个算法,找出两点之间是否存在一条路径。
给定图中的两个结点的指针UndirectedGraphNode*a,UndirectedGraphNode* b(请不要在意数据类型,图是有向图),请返回一个bool,代表两点之间是否存在一条路径(a到b或b到a)。
题目分析:
这个题目考察的其实是有向图的遍历,图的遍历分为深度优先遍历和广度优先遍历,深度优先遍历(DFS)用堆栈(Stack)实现,广度优先遍历(BFS)用队列(queue)实现,在该题目中给出了每个节点的子节点,所以最好用广度优先遍历。
图的广度优先遍历和树的层次遍历类似,但是不是完全相同,因为图是连通的,所以我们必须去标志那个节点被访问过,那个节点没有被访问过,最后如果全部访问完以后,还没有找到a到b的路径,则返回false。
类似于一个分层搜索的过程,广度优先遍历需要使用一个队列以保持访问过的结点的顺序,以便按这个顺序来访问这些结点的邻接结点。
具体算法表述如下:
访问初始结点v并标记结点v为已访问。
结点v入队列
当队列非空时,继续执行,否则算法结束。
出队列,取得队头结点u。
查找结点u的第一个邻接结点w。
若结点u的邻接结点w不存在,则转到步骤3;否则循环执行以下三个步骤:
1). 若结点w尚未被访问,则访问结点w并标记为已访问。2). 结点w入队列3). 查找结点u的继w邻接结点后的下一个邻接结点w,转到步骤6。
如下图,其广度优先算法的遍历顺序为:1->2->3->4->5->6->7->8
注意知识点:
(1)图中有环,记得标记是否被访问
class
Path {
public
:
bool
checkPath(UndirectedGraphNode* a, UndirectedGraphNode* b) {
// write code here
return
check(a,b)||check(b,a);
}
bool
check(UndirectedGraphNode* a, UndirectedGraphNode* b) {
// write code here
//a,b为空,直接返回false
if
(a==NULL||b==NULL)
return
false
;
if
(a==b)
//最开始检查//a,b相等,直接返回true
return
true
;
//
为了防止环的产生,已经入栈过的点不再入栈,用map管理
map<UndirectedGraphNode*,
bool
> map1;
//BFS工作队列
queue<UndirectedGraphNode*> que;
//队列保存节点
que.push(a);
//入队列
while
(!que.empty())
//队列不为空
{
UndirectedGraphNode* ptr=que.front();
//弹出队列首元素
map1[ptr]=
true
;
//标记访问//ptr节点被访问
for
(
int
i=0;i<ptr->neighbors.size();i++)
{
if
((ptr->neighbors)[i]==b)
//如果邻居为b
return
true
;
//近邻节点存在,且未被访问,进队列
if
(ptr->neighbors[i]&&map1[ptr->neighbors[i]]!=
true
)
que.push((ptr->neighbors)[i]);
//入队
}
que.pop();
//出队
}
return
false
;
}
};
BFS还有一种方法:
class
Path {
public
:
bool
checkPath(UndirectedGraphNode* a, UndirectedGraphNode* b) {
map<UndirectedGraphNode*,
bool
> flag;
//记录是否已经访问过
if
(atob(a,b,flag))
return
true
;
//检查a->b的路径
if
(atob(b,a,flag))
return
true
;
//检查b->a的路径
return
false
;
}
bool
atob(UndirectedGraphNode* a, UndirectedGraphNode* b,
map<UndirectedGraphNode*,
bool
> flag){
//广度优先搜索
queue<UndirectedGraphNode*> nodes;
//队列保存节点
if
(a == b)
return
true
;
//最开始检查
nodes.push(a);
//入列
while
(!nodes.empty()){
UndirectedGraphNode* node = nodes.front();
nodes.pop();
//出列
flag[node] =
true
;
//标记访问
for
(unsigned
int
i = 0; i < node->neighbors.size(); ++i){
UndirectedGraphNode* n = node->neighbors[i]
//查询邻近节点
if
(flag[n])
continue
;
//跳过已经访问过的
else
{
if
(n == b)
return
true
;
//查询正确
nodes.push(n);
//否则入列
}
}
}
return
false
;
//找不到
}
};
两种方法:基本相同,就是队列的出队时的代码写的地方不同,但是,因为队列是先进先出,所以,写的上面两个地方的位置均可。
深度优先
深度优先遍历,从初始访问结点出发,我们知道初始访问结点可能有多个邻接结点,深度优先遍历的策略就是首先访问第一个邻接结点,然后再以这个被访问的邻接结点作为初始结点,访问它的第一个邻接结点。总结起来可以这样说:每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
我们从这里可以看到,这样的访问策略是优先往纵向挖掘深入,而不是对一个结点的所有邻接结点进行横向访问。
具体算法表述如下:
访问初始结点v,并标记结点v为已访问。
查找结点v的第一个邻接结点w。
若w存在,则继续执行4,否则算法结束。
若w未被访问,对w进行深度优先遍历递归(即把w当做另一个v,然后进行步骤123)。
查找结点v的w邻接结点的下一个邻接结点,转到步骤3。
例如下图,其深度优先遍历顺序为 1->2->4->8->5->3->6->7
从起点遍历整个图,如果到了终点就返回true,否则false这里采用DFS
和书上不同。这里graphNode没有isVisit属性,无法标记是否访问,所以用map辅助
class
Path {
public
:
map<UndirectedGraphNode*,
bool
> nodestate;
//default is false, not visited
bool
checkPath(UndirectedGraphNode* a, UndirectedGraphNode* b) {
if
(dfs(a,b))
return
true
;
//forward
nodestate.clear();
//清空map
return
dfs(b,a);
//reverse
}
//深度优先遍历
bool
dfs(UndirectedGraphNode* a, UndirectedGraphNode* b)
{
//a,b为空,直接返回false
if
(a==0 || b==0)
return
false
;
nodestate[a]=
true
;
//a点被访问
if
(a->label==b->label)
return
true
;
//if(a==b) return true;//这样写也可以,同上一句
for
(
int
i=0;i<(a->neighbors).size();i++)
{
//a的近邻节点
UndirectedGraphNode* x=a->neighbors[i];
if
(
false
==nodestate[x] &&
true
==dfs(x,b))
return
true
;
}
return
false
;
}
};
联系客服