算法

DFS

算法原理：
选择一个起始点V作为当前节点

1、访问当前节点，并标注为已访问，到下一步

2、如果存在和当前节点相邻并且还没有被访问的节点U，则将U设为当前节点，返回上一步

3、如果当前节点没有未被访问的相邻节点，则回溯，回退到上一个当前节点

上面所说的当前节点用栈来维护，每次访问到的节点入栈，回溯的时候出栈

伪代码：

DFS（V）
    visited[v] = true;
    dosomething(v);
    for u in adjecnt_list[v]
        if visited[u] == false
            DFS(u)

BFS

选择一个起点v放入先进先出队列中

1、如果队列不为空，弹出队列首元素作为当前节点，执行下一步；如果队列为空，则算法结束

2、将与当前节点相邻且未被访问的所有节点信息更新，并全部放入队列，继续执行上一步

伪代码：

BFS(v):
    resetArray(visited,false);
    visted[v] = true;
    queue.push(v);
    while(!queue.isEmpty()){
        v = queue.poll();
        for u in adjecent_list[v]:
            if(visited[u] == false)
                dosomething(u);
                queue.push(u);
    }