dfs-bfs理解

2019-04-14 17:07发布

站内文章 / 模拟电子
18142 0 954
1：dfs被称为深度优先搜索，从字面上就可以理解，其强调的深度，其是一条路走到死，在返回上节点，在选一条路，在走。它最好不要用于最短路径上。我觉的主要用于的是求出数量不大的所有的路径，或者是求路径的条数的问题上 2：bfs被称为广度优先搜索，其强调的是广度，当然，主要用于找到一条最短的路（这里注意这里的最短路径和djiktra的所求的最短路径有所不同我的理解是，bfs所求的最短路径是针对与无权的图，也就是各个点的距离是相等的，而djikstra可以求各个点的距离不相等的） 3：djikstra是一中搜索最短路径的方法，其主要的思想是每部都确定为最优的路径来进行，并时刻更新个点到源点的距离 例如：二叉树              0         1          2  3        4   5        6 分别对它进行dfs，得到 0，1，3，4，2，5，6 bfs得到0，1，2，3，4，5，6 下面附上我的代码： #include
#include
#include
#include
using namespace std;
int maps[7][7] =
{
    {0, 1, 1, 0, 0, 0, 0 },
    {1, 0, 0, 1, 1, 0, 0 },///这是一个邻接数组，横纵坐标表示的两个点，值表示是否联通
    {1, 0, 0, 0, 0, 1, 1 },
    {0, 1, 0, 0, 0, 0, 0 },
    {0, 1, 0, 0, 0, 0, 0 },
    {0, 0, 1, 0, 0, 0, 0 },
    {0, 0, 1, 0, 0, 0, 0 }
};
int vis[7]={0,};
void dfs(int s)
{
    vis[s]=1;
    cout<     for(int i=0;i<7;i++)
        if(!vis[i]&&maps[s][i])
            dfs(i);
}
void bfs(int s)
{
    queue q;
    q.push(s);
    vis[s]=1;
    while(!q.empty())
    {
        int a=q.front();q.pop();
        cout<         for(int i=0;i<7;i++)
        {
            if(!vis[i]&&maps[a][i])
            {
                q.push(i);
                vis[i]=1;
            }
        }
    }
}
int main()
{
    dfs(0);
    memset(vis,0,sizeof vis);
    cout<     bfs(0);
    return 0;
}
    如果有错，请指出，多谢

热门文章