先深遍历

先深遍历

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;
    }
}