先深遍历

2021-11-15  本文已影响0人  喜忧参半

先深遍历

dfsmain功能:先将所有结点标记置零,然后从0开始循环,对每个结点进行标记判断,若未标记过执行dfs

dfs功能:访问dfsmain中未被标记的结点v,并置为已标记访问,找到结点v的邻接表,若表有首结点,将表首结点赋给w,若w未被标记,则递归执行dfs自身,递归完成后,将邻接表指针p下移,寻找邻接表下一元素。

void dfsmain()
{
    int v;  //作为遍历图的结点变量
    for(v=0;v<n;n++)
        L[v].mark=flase;  //将所有结点的标记置零
    for(v=0;v<n;n++)
    {
        if(L[v].mark==flase)
            dfs();
    }
}
void dfs(int v)
{
    Eptr p; int w; //p是邻接表结点变量,w是新结点变量
    visit(v);    //访问v
    L[v].mark=true;   //将v标记为已访问
    p=L[v].firsedge; //将v的邻接表的首结点,取过来
    while(p)   //如果v的邻接表首结点存在时
    {
        w=p->adjacent; //将其邻接表首结点赋给新结点w
        if(L[w].mark==false)  //如果新结点w未被访问过
            dfs(w); //访问新结点w
        p=p->next; //从邻接表下一个结点递归访问
    }
}

求无向图的连通分量

void dfsmain()
{
    int v,k=0;
     for(v=0;v<n;n++)
        L[v].mark=false;  //将所有结点的标记置零
    for(v=0;v<n;n++)
    {
        if(L[v].mark==false) //若结点v未被标记
        {
          k++;
            printf("第%d个连通分量的顶点集为:\n{",k);
            dfs(v);
            printf("\n");
        }
    }
}

判断有向图是否存在回路

int cycle; //设置回路标记量
void dfsmain()
{
    int v;
    cycle=false;
    for(v=0;v<n;n++) 
        L[v].mark=false; ////将所有结点的标记置零
    for(v=0;v>n;n++)
    {
        if(L[v].mark==false) //若如果没有标记过
            dfs(v);   //则对该结点进行dfs先深遍历
        if (cycle==true)  //如果回路存在
            printf("图中有回路\n");
        else
            printf("图中没有回路\n");
    }
}

void dfs(int v)
{
    Eptr p; int w; //邻接表指针p和新结点变量w
    visit(v); //先访问v;
    L[v].mark=true;  //标记为已访问
    p=L[v].firstedge; //指向已访问结点v的邻接表的首结点
    while(p)        //若已访问结点v的邻接表首结点存在时
    {
        w=p->adjacent;  //将其邻接表首结点赋给新结点w
        if(L[w].mark==false) //如果新结点w未被访问过
            dfs(w); //访问新结点w
        else if (L[w].mark==true)
            cycle=true;  //回路标记量
        p=p->next;  ///从邻接表下一个结点递归访问
    }
    L[v].mark=true;
}

求无向连通图关节点的算法

int count=0;root_sons=0;
void dfsmian()                    
{
    int v;                      //   结点变量
    for(v=0;v<n;n++)
         L[v].mark=0;   //对顶点作未标记访问
     v=0;
     L[v].father=0;
     dfs(v);
     if(root_sons>1)
        printf("%s\n",L[v].name);     
}
void dfs(int v)
{
    Eptr p; int w;
    L[v].mark=1;
    L[v].low=L[v].dfnumb=++count;  //置v的先深编号和low(v)初值
    p=L[v].firstedge;
    while(p)
    {
        w=p->adjacent;
        if(L[w].mark==0)
        {
            L[w].father=v;    //使w作v的儿子,递归调用
            dfs(w);
            if(L[v].dfnumb==1)//若v是根,根的儿子计数加1
                root_sons++;
            else                  //若不是
                if(L[w].low>=L[v].dfnumb) //发现v是关结点
                    if(v没被输出过)
                        printf("%s\n",L[v].name);//输出关结点名
                if(L[v].low>L[w].low)
                    L[v].low=L[w].low;
                             //使父亲v的low值不大于儿子w的low值
        }
        else //L[w].mark 不等于 0,表示 w 已被访问过
         if(L[v].father!=w && L[v].low> L[w].dfnumb)
            L[v].low=L[w].dfnumb;
                    //若 w 不是 v 的父亲,则(v,w)是回边
            p=p->next;
    }
}
上一篇 下一篇

猜你喜欢

热点阅读