美文网首页
图的遍历

图的遍历

作者: 我好菜啊_ | 来源:发表于2019-12-04 13:55 被阅读0次

广度优先搜索BFS

bool visited[MAX_VERTEX_NUM];     //访问标记数组
void BFSTraverse(Graph G){
    for(i=0;i<G.vexnum;++i)
        visited[i]=FALSE;
    InitQueue(Q);
    for(i=0;i<G.vexnum;++i)
        if(!visited[i])    //对每个连通分量调用一次BFS
             BFS(G, i);
}

//先访问再入队,出队的时候再把未被访问过的邻接点都访问并入队
void BFS(Graph G, int v){
    visited(v);
    visited[v]=TRUE;
    EnQueue(Q, v);
    while(!isEmpty(Q)){
        DeQueue(Q, v);
        for(w=FirstNeighbor(G, v);w>=0;w=NextNeighbor(G, v, w))
            if(!visited[w]){
                visited(w);
                visited[w]=TRUE;
                EnQueue(Q, w);
            }
    }
}

空间复杂度 O(|V|)
时间复杂度 邻接表O(|V|+|E|)
邻接矩阵O(|V|^2)

BFS求单源最短路径

void BFS_MIN_Distance(Graph G, int u)
{
    for(i=0;i<G.vexnum;++i)
        d[i]=∞;
    visited[u]=TRUE;
    d[u]=0;
    EnQueue(Q, u);
    while(!isEmpty(Q)){
        DeQueue(Q, u);
        for(w=FirstNeighbor(G, u);w>=0;w=NextNeighbor(G, u, w))
            if(!visited[w]){
                visited[w]=TRUE;
                d[w]=d[u]+1;
                EnQueue(Q, w)
            }
    }
}

深度优先搜索DFS

bool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph G)
{
    for(v=0;v<G.vexnum;++v)
        visited[v]=FALSE;
    for(v=0;v<G.vexnum;++v)
        if(!visited[v])
            DFS(G, v);
}

void DFS(Graph G, int v)
{
    visited(v);
    visited[v]=TRUE;
    for(w=FirstNeighbor(G, v);w>=0;w=NextNeighbor(G, v, w))
        if(!visited[w]){
            DFS(G, w);
        }
}

空间复杂度 O(|V|)
时间复杂度 邻接表O(|V|+|E|)
邻接矩阵O(|V|^2)


注意:图的邻接矩阵表示是唯一的,但对于邻接表来说,若边的输入次序不同,生成的邻接表也不同。因此,对于同一个图,基于邻接矩阵的遍历所得到的DFS序列和BFS序列唯一,但基于邻接表的不唯一。(生成树也不唯一)
连通图可得到广度/深度优先生成树,否则产生生成森林。

相关文章

  • 图的深度优先遍历

    数据结构遍历的意义 树的遍历 图的遍历 树的前序遍历 图遍历和树遍历区别 知识回顾 树的深度优先遍历 普通函数和递...

  • 图的深度优先遍历和马踏棋盘算法

    图的深度优先遍历思想 图的遍历通常有两种遍历次序方案: 深度优先遍历和广度优先遍历。深度优先遍历(DepthFir...

  • 图的DFS && BFS遍历

    对图的深度优先遍历: 对图的广度优先遍历:

  • 数据结构与算法学习-图的遍历

    图的遍历可以分为:深度优先遍历和广度优先遍历 一、深度优先遍历 深度优先遍历的实现思路 将图的顶点和边信息输⼊入到...

  • 图和遍历

    邻接矩阵定义一个图 其实就是二维数组来定义 图的遍历 深度搜索遍历 2.广度搜索遍历 遍历

  • 图 深度和宽度遍历

    图的深度遍历依赖于递归、 图的宽度优先遍历依赖于队列

  • 哈夫曼实现 图:十字链表,邻接多重链表,邻接表(无向),邻接表

    图的遍历: 无论是广度优先,还是深度优先都是以箭头方向右边的优先遍历; 广度优先遍历(无向图): 深度优先(无向图...

  • 11.图的广度优先遍历与无权图的最短路径

    图的广度优先遍历与无权图的最短路径 点击这里,前提知晓... 一、图的广度优先遍历 和树的广度优先遍历的思想一样,...

  • 基本数据结构

    一.图二.树 一.图 1.图的遍历: 通过深度优先遍历DFS和广度优先遍历BFS两种方式。深度优先遍历0 1 2 ...

  • 图的遍历

    树的遍历:从图中某一顶点出发,沿着一些边访问图中所有顶点,但使每个顶点仅被访问一次,这个过程叫做图的遍历。一个通常...

网友评论

      本文标题:图的遍历

      本文链接:https://www.haomeiwen.com/subject/mtajwctx.html