关于图的广度遍历问题

951923615

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

n0noper

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

1        4
| \
3-2

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

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

951923615

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

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

951923615

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

微信号yp2259376

n0noper

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

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

千亩计者

while之前把1节点EnQueue可以实现