951923615 发表于 2016-3-13 20:40:19

关于图的广度遍历问题

void BFSTraverse(MGraph G)
{
        int i, j;
        Queue Q;
       
        for( i=0; i < G.numVertexes; i++ )
        {
                visited = FALSE;
        }
       
        initQueue( &Q );
       
        for( i=0; i < G.numVertexes; i++ )
        {
                if( !visited )
                {
                        printf("%c ", G.vex);
                        visited = TRUE;
                        EnQueue(&Q, i);
                       
                        while( !QueueEmpty(Q) )
                        {
                                DeQueue(&Q, &i);
                                for( j=0; j < G.numVertexes; j++ )
                                {
                                        if( G.art==1 && !visited )
                                        {
                                                printf("%c ", G.vex);
                                                visited = TRUE;
                                                EnQueue(&Q, j);
                                        }
                                }
                        }
                }
        }
}个人觉得第二个for循环没必要存在，应为当while（）循环结束时，所有顶点都遍历过了，没必要第二个for循环再次i++了

n0noper 发表于 2016-3-13 20:40:20

本帖最后由 n0noper 于 2016-3-14 10:13 编辑

如果没有第二个for(遍历所有节点)，只使用while，那先把第一个父节点入队列，初步一想，是可以的~~
但是这是图，如果有一个节点跟其余节点没有边呢？或者分好几个子图呢？例如：

1      4
| \
3-2

上图，while之前把1节点EnQueue可以实现，但是4节点呢？咋啦，不是亲娘生的就不管了？
撸主可能想把所有节点先压进去再说是吧？好，节点压入顺序就是遍历的顺序，这个不是我们手动写进去的。

如果我理解错了撸主的意思，举个例子，画个流程图大家讨论讨论。

951923615 发表于 2016-3-14 19:53:18

n0noper 发表于 2016-3-14 09:49
如果没有第二个for(遍历所有节点)，只使用while，那先把第一个父节点入队列，初步一想，是可以的~~
但是这 ...

能加个微信好友么？想多点学友，自个一个人钻研，想一块学习

951923615 发表于 2016-3-14 19:56:00

n0noper 发表于 2016-3-14 09:49
如果没有第二个for(遍历所有节点)，只使用while，那先把第一个父节点入队列，初步一想，是可以的~~
但是这 ...

微信号yp2259376

n0noper 发表于 2016-3-15 08:25:15

951923615 发表于 2016-3-14 19:56
微信号yp2259376

加QQ吧，你那个微信号不存在··
QQ的话，传文件啥的比较方便。1263591465 如果不用QQ，邮箱联系也可以: n0noper@yeah.net

千亩计者 发表于 2016-8-16 23:20:02

while之前把1节点EnQueue可以实现
页: [1]
查看完整版本: 关于图的广度遍历问题