程序员面试金典4.2 图有向路径检查

雪柳花明 2017-04-24

展开全文

对于一个有向图，请实现一个算法，找出两点之间是否存在一条路径。

给定图中的两个结点的指针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）图中有环，记得标记是否被访问

（2）要分别检测两个方向（a->b，b->a）

//BFS

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管理

//用来标记是否访问过该节点

//上不同。这里graphNode没有isVisit属性，无法标记是否访问，所以用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;
    }
};