MENU

深度优先搜索DFS(一)

March 13, 2018 • Read: 198 • 算法

从起点出发,走过的点做标记,发现没有走过的点,就随意挑一个往前走,走不了就回退,此种路径搜索策略就称为 “深度优先搜索(Depth First Search)”。

其实称为 “远度优先搜索”更容易理解。因为这种策略能往前走一步就往前走一步,总是试图走的更远,所谓远近(深度),其实是以距离起点来衡量的。

bool DFS(v)
{
    if(v为终点)
        return true;
    if(v为旧点)
        return false;
    将v标记为旧点;
    对和v相邻的每个节点u
    {
        if(DFS(u) == true)
            return true;   
    } 
    return false;
} 
int main()
{
    将所有点都标为新点;
    起点_x = x;
    起点_y = y;
    cout<<Dfs(起点);
}
Node path[Max_len];//Max_len取节点总数即可
int depth;
bool DFS(v)
{
    if(v为终点)
    {
        path[depth] = v;
        return true;
    } 
    if(v为旧点)
        return false;
    将v标记为旧点;
    path[depth] = v;
    ++depth;
    对和v相邻的每个节点u
    {
        if(DFS(u) == true)
            return true;
    } 
    --depth;
    return false;
} 
int main()
{
    将所有的点都标记为新点;
    depth = 0;
    if(DFS(起点))
    {
        for(int i = 0;i <= depth;i++)
        {
            cout<<depth[i]<<endl;
        } 
    } 
}
//深度优先遍历图上所有节点
DFS(v)
{
    if(v是旧点)
        return;
    将v标记为旧点;
    对和v相邻的所有节点u
    {
        DFS(u);
    } 
} 
int main()
{
    将所有的点都标为新点;
    while(在图中能找到新点k)
    {
        DFS(k);
    } 
}
最后编辑于: October 7, 2018
Archives Tip
QR Code for this page
Tipping QR Code