欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

图的遍历——DFS

程序员文章站 2023-12-28 23:51:52
...

最早接触到dfs是在小蝌蚪安家，就是dfs寻找最大连通块，当时对图还没有概念，也不知道这可以是个邻接矩阵，学数据结构之后，知道，一个图有两种存储结构——邻接矩阵和邻接表，遍历一个图也可以是dfs和bfs，dfs核心就是递归，bfs就是队列，然后递归的写法也可以用栈写成非递归的形式。

图的遍历——DFS

这个题中比较关键的首先是建图，题目点明是邻接表，其次是遍历是dfs，然后dfs要求是非递归过程

建立邻接表的过程，以样例1为例，如果是前插法，则邻接表的形式应该是
1 3 2
2 1
3 1
如果是尾插法的话，邻接表的形式应该是
1 2 3
2 1
2 3
然后根据深度优先遍历的结果（1，2，3）来看，应该是尾插法建图，本着举一反三，一题多解的原则，本题我们用三种方法来写，邻接表存储dfs非递归（合题意），邻接表存储dfs递归，邻接矩阵存储dfs递归。

邻接表dfs递归

#include<iostream>
using namespace std;
#include<string.h>

typedef struct ArcNode
{
    int adjvex;
    ArcNode *nextarc;
    int info;
}ArcNode;

typedef struct VNode
{
    int data;
    ArcNode *fistarc;
}VNode;

typedef struct ALGraph
{
    VNode vertices[500];
    int vexnum,arcnum;
}ALGraph;

bool CreateUDG(ALGraph &G)
{
    int i;
    for(i=0;i<500;i++)
    G.vertices[i].data=0;

    for(i=1;i<=G.vexnum;i++)
    {
        G.vertices[i].data=i;
        G.vertices[i].fistarc=NULL;
    }

    for(i=0;i<G.arcnum;i++)
    {
        int h,k;
        cin>>h>>k;

        ArcNode *p1;
        p1=new ArcNode;
        p1->adjvex=k;
        p1->nextarc=NULL;
        if(G.vertices[h].fistarc==NULL)
        G.vertices[h].fistarc=p1;
        else
        {
            ArcNode *temp;
            temp=new ArcNode;
            temp=G.vertices[h].fistarc;
            while(temp->nextarc!=NULL)
            temp=temp->nextarc;

            temp->nextarc=p1;
        }

        ArcNode *p2;
        p2=new ArcNode;
        p2->adjvex=h;
        p2->nextarc=NULL;
        if(G.vertices[k].fistarc==NULL)
        G.vertices[k].fistarc=p2;
        else
        {
            ArcNode *temp;
            temp=new ArcNode;
            temp=G.vertices[k].fistarc;
            while(temp->nextarc!=NULL)
            temp=temp->nextarc;

            temp->nextarc=p2;
        }
    }
}

bool visited[500];
int num;

void DFS_AL(ALGraph G,int v)
{
    num++;
    if(num!=G.vexnum)
    cout<<v<<" ";
    else
    cout<<v<<endl;
    visited[v]=true;
    ArcNode *p;
    p=new ArcNode;
    p=G.vertices[v].fistarc;
    while(p!=NULL)
    {   
        int w;
        w=p->adjvex;
        if(!visited[w])
            DFS_AL(G,w);
        p=p->nextarc;
    }
    //这段代码好简洁
}

int main()
{
    int n,m;//n个顶点，m条边
    while(scanf("%d%d",&n,&m)!=EOF&&n+m)
    {
        ALGraph G;
        G.vexnum=n;
        G.arcnum=m;
        CreateUDG(G);
        int f;
        scanf("%d",&f);
        memset(visited,0,sizeof(visited));
        num=0;
        DFS_AL(G,f);
    } 
    return 0;
}

邻接矩阵dfs递归

#include<iostream>
using namespace std;
#include<algorithm>
#include<string.h>
#define MAXINT 9999999;

typedef struct AMGraph
{
    int arcs[100][100];
    int vexs[100];
    int arcnum,vexnum;
}AMGraph;

void CreateGraph(AMGraph &G)
{
    int i,j;
    for(i=0;i<100;i++)
        G.vexs[i]=0;

    for(i=0;i<100;i++)
        for(j=0;j<100;j++)
            G.arcs[i][j]=0;

    for(i=1;i<=G.vexnum;i++)
        G.vexs[i]=i;

    for(i=1;i<=G.arcnum;i++)
    {
        int h,k;
        scanf("%d%d",&h,&k);
        G.arcs[h][k]=1; 
        G.arcs[k][h]=1;
    }
}

bool visited[100];
int num;

void DFS_AMG(AMGraph G,int v)
{
    num++;
    visited[v]=true;
    if(num!=G.vexnum)
        cout<<v<<" ";
    else
        cout<<v<<endl;

    int j;

    for(j=1;j<=G.vexnum;j++)
    {
        //cout<<visited[j]<<endl;
        //cout<<G.arcs[v][j]<<endl;
        if((visited[j]==0)&&(G.arcs[v][j]==1))
            DFS_AMG(G,j);
    }

}


int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF&&n+m)
    {
        AMGraph G;
        G.vexnum=n;
        G.arcnum=m;
        CreateGraph(G);
        int i;
        for(i=0;i<100;i++)
        visited[i]=false;
        //memset(visited,0,sizeof(visited));
        num=0;
        int v;
        scanf("%d",&v);

        DFS_AMG(G,v);
    }
    return 0;
}

这段代码开始的时候在我的编译器上怎么也运行不出来，我以为算法出了问题，结果是数组开大了，开始时500*500的，后来我换成了100*100的就可以了，这启示我们，二维数组这种东西，还真的是很有局限性…

邻接表非递归版dfs

#include<iostream>
using namespace std;
#include<stack>
#include<algorithm>
#include<string.h>

typedef struct ArcNode
{
    int adjvex;
    ArcNode *nextarc;
};

typedef struct VNode
{
    int data;
    ArcNode *fistarc;
};

typedef struct ALGraph
{
    int vexnum,arcnum;
    VNode vertices[500];
};

void CreateGraph(ALGraph &G)
{
    int i;
    for(i=0;i<500;i++)
    G.vertices[i].data=0;

    for(i=1;i<=G.vexnum;i++)
    {
        G.vertices[i].data=i;
        G.vertices[i].fistarc=NULL;
    }

    for(i=0;i<G.arcnum;i++)
    {
        int h,k;
        cin>>h>>k;

        ArcNode *p1;
        p1=new ArcNode;
        p1->adjvex=k;
        p1->nextarc=G.vertices[h].fistarc;
        G.vertices[h].fistarc=p1;

        ArcNode *p2;
        p2=new ArcNode;
        p2->adjvex=h;
        p2->nextarc=G.vertices[k].fistarc;
        G.vertices[k].fistarc=p2;
    }
}

bool visited[500];
int num;

void dfs_stack(ALGraph G,int f)
{
    stack<int>v;        
    v.push(f);
    while(!v.empty())
    {
        num++;
        if(!visited[v.top()])
        {
            if(num!=G.vexnum)
                printf("%d ",v.top());
            else
                printf("%d\n",v.top());
        }

        visited[v.top()]=1; 
        ArcNode *p;
        p=new ArcNode;
        p=G.vertices[v.top()].fistarc;
        v.pop();

        while(p!=NULL)
        {
            if(!visited[p->adjvex])
            {
                v.push(p->adjvex);
            }
            p=p->nextarc;
        }
    }
}

int main()
{
    int n,m;//n个顶点，m条边
    while(scanf("%d%d",&n,&m)!=EOF&&n+m)
    {
        ALGraph G;
        G.vexnum=n;
        G.arcnum=m;
        CreateGraph(G);
        int f;
        scanf("%d",&f);
        int i;
        for(i=0;i<500;i++)
        visited[i]=0;
        num=0;
        dfs_stack(G,f);
    } 
    return 0;
}

用栈来实现非递归版dfs就是把数据一个一个存起来，然后在输出的时候再将vis数组置1，有一个问题就是比如1有2，3两个节点，是先访问哪一个呢，这个题目是用的前插法建图，然后输出的时候会倒过来，就这样，再琢磨一下吧！

上一篇：

下一篇：

推荐阅读