CCI题目4-2:判断图中的两个节点是否连通

By | 2012 年 11 月 24 日

用广度优先遍历做就行了。
代码只写了核心,旁边的额辅助函数只定义了而已。



题目
Given a directed graph, design an algorithm to find out whether there is a route be- tween two nodes.



代码


//
//  main.cpp
//  CCI.4.2.Reachable in Graph
//
//  Created by Qiu Xiangyu on 12-11-24.
//  Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

#include 
#include 
#include 
using namespace std;
enum VisitState {
    Unvisite = 0,
    Visiting = 1,
    Visited = 2
    };
class GraphNode {
public:
    VisitState visiteState;
};
class Graph {
    
    
public:
    void setAllVisiteState(VisitState targetState);
    list adjacentNodes(GraphNode *node);
    bool isNodeInGraph(GraphNode *node);
    bool isNodeConnectToNode(GraphNode *sourceNode, GraphNode *targetNode) {
        if (!isNodeInGraph(sourceNode) || !isNodeInGraph(targetNode)) {
            return false;
        }
        setAllVisiteState(Unvisite);
        //unvisit, not visited at all
        //visiting, in the queue, but not examed and expaned
        //vivited, expanded and visited.
        queue q;
        q.push(sourceNode);
        while (q.size()) {
            GraphNode *curNode = q.front();
            q.pop();
            if (curNode->visiteState == Visited) {
                continue;
            }
            if (curNode == targetNode) {
                return true;
            }
            curNode->visiteState = Visited;
            list adjacents = adjacentNodes(curNode);
            for (list::iterator it = adjacents.begin(); it != adjacents.end(); ++it) {
                GraphNode *cnode = *it;
                if (cnode->visiteState == Unvisite) {
                    cnode->visiteState = Visiting;
                    q.push(cnode);
                }
            }
        }
        return false;
    }
};

int main(int argc, const char * argv[])
{
    // insert code here...
    std::cout << "Hello, World!\n";
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注