数据结构-图的遍历(11)

无向连同图的深度优先遍历：

    先遍历自己结点，然后遍历第一连接点，然后遍历后一连接点，在遍历连接点时遵循相同的规律。

在遍历时，若遇到已经遍历的顶点，则不需要遍历。

这样，会优先遍历一条深度最长的线

 

算法：

intmatrix[][N],图的矩阵链接存储方式所存储的图，

int v：要先遍历的顶点结点。

int visitd[]：如果遍历过相应的顶点，则该位置为1

 

void dfs(int matrix[][N], int v, int visitd[])

{

         遍历v，置相应的标志位；

          int u = v的第一连接点；

         while(u>=0){

                 if（u未被遍历）

                        dfs(u);

                  u = 下一连接点；

          }

 

}

 

广度优先遍历：会优先遍历距离自己最近的顶点：

void bfs(int matrix[][N], int v, int visitd[])

{

        创建一个队列；

        遍历v,并置相应的标志位；

        入队(v)；

        while(队列非空){

               v =  出队（）;

               u = v的下一连接点；

               while(u >= 0){

                   if （u没有被遍历）{

                      遍历u，并置相应的标志位；

                      入队(u);

                    }

                u = 下一连接点；

                }

                

           }

 

}