类比二叉树先序遍历与图深度优先搜索

在引入图的深度优先搜索之前,为了更加容易理解.先考究一种特殊的图---二叉树的深度优先搜索算法---即二叉树的递归遍历方法.

二叉树的前序遍历算法:

    void TreeWalk(node* root)  
    {  
        if(root)  
        {  
            visit(root);  
            TreeWalk(root->left);  
            TreeWalk(root->right);  
        }  
    }  

1.如果root不为空,先访问root,

2再递归下降地访问root->left和root->right.

在二叉树中,与root邻接的结点只有left and right.所以,每次只需要递归下降访问这两个节点即可.

对于图来说,可以类比二叉树(特殊情况),总结出一般规律:

1先选定任意一个点vex做为生成树的根结点.访问该根点,

2再递归下降地访问与vex邻接的而且未被访问过的所有结点.

在图中,与vex邻接的结点是不像二叉树一样只有left 和 right,因为是不确定的,因此需要循环地查找判断哪些点邻接并且尚未被访问过.

伪代码:

    void DFS(Graph& g,int vex)  
    {  
        Visit vex and Mark vex is visited;  
        for w=FirstAdjacencyVertex to LastAdjacencyVertex(which is not visited before)  
            DFS(g,w)  
    }  

//深度优先算法,可以形成一棵树  
void DFS(Graph& g,int vex)  
{  
    cout<<vex<<' ';  
    visited[vex]=true;//is visited  
    int w=FirstAdjVertex(g,vex);  
    while(w>0)  
    {  
        DFS(g,w);  
        w=NextAdjVertex(g,vex,w);  
    }  
}  

    //找第一个未被访问过的邻接结点,找不到返回0  
    int FirstAdjVertex(Graph& g,int vex)  
    {  
        for(int i=1;i<=g.vnum;++i)//从点1开始找与vex邻接的第一个结点  
        {  
            if(g.edge[vex][i]==1 && !visited[i])  
                return i;  
        }  
        return 0;  
    }  
    //找下一个未被访问过的邻接结点  
    int NextAdjVertex(Graph& g,int vex,int w)  
    {  
        for(int i=w;i<=g.vnum;++i)//从w开始,找下一个未被访问过的邻接结点  
        {  
            if(g.edge[vex][i]==1 && !visited[i])//若i与vex邻接且i未访问过,下一次遍历,就从这个点往下.  
                return i;  
        }  
        return 0;//点都从1开始,返回0则所以点已访问过  
    }  

    void DFS_traver(Graph& g)  
    {  
        for(int i=1;i<=g.vnum;++i)  
        {  
            if(!visited[i])//如果i结点未被访问过,形成森林  
                DFS(g,i);  
        }  
    }  

int visited[8];
    void BFS(int edge[][8],int vex)  
    {  
        queue<int> q;  
        //visited[vex] = 1;                                //标记已被访问过  
        q.push(vex);                                        //初始化队列  
      
        while(!q.empty())  
        {  
            vex=q.front();  
            q.pop();                                        //取出队头数据  
            if(!visited[vex])
            {
            	cout<<vex<<' ';  	
            	visited[vex] = 1;                    //标记已被访问过  
            }
			
            for ( int j=0; j<8; ++j )   
            {  
                if(edge[vex][j] == 1 && !visited[j] )        //邻接未被访问过的结点入队  
                {  
                    q.push(j);  
                }  
            }  
        }  
    }  
    void BFS_traver(int g[][8])  
    {  
    	int i;
    	for(i=0;i<8;i++)
    		visited[i]=0;
        for(i=0;i<8;++i)  
        {  
            if(!visited[i])
			{
			  BFS(g,i);                             //如果i结点未被访问过,形成森林  
            }
        }  
    } 

深度优先搜索 && 广度优先搜索