数据结构总结系列（一）——深度优先遍历之生成森林

最近忙于做数据结构的作业，因此想要总结一下自己在写代码时遇到的一些困难，c++可能不能顺利总结了呜呜呜~ 就从最近的事情开始吧。

【任务描述】

扩充深度优先搜索算法，在遍历图的过程中建立生成森林的左子女-右兄弟链表。

【想法】

首先得出这个结构为一个树的结构，然后思考这个树应该用什么样的结构来存储呢？

任务里给出答案——链表，当然在图的章节里还有邻接矩阵的数据结构，但拿来存图却有时显得浪费，因此个人推荐用链表来生成一个森林。

闲话少说，让我们开始完成这个任务吧~

第一步：

建立结构：

由于要生成森林，同时使用图的邻接表来存储图，因此有两部分结构

图：

#define MAXMIZE 20

//创建图的邻接表结构
typedef struct ArcNode
{
    int adjvex;//边指向的顶点位置
    struct ArcNode *nextarc=NULL;//指向下一条边的指针
    int *info;//该边相关信息的指针
}ArcNode;

typedef struct VNode
{
    int data;//顶点信息
    ArcNode *firstarc;//指向第一条依附该顶点的边的指针
}VNode,AdjList[MAXMIZE];

typedef struct{
    AdjList vertices;//可以间接使用数组
    int vexnum,arcnum;//顶点，边
}ALGraph;

由于树是左子女-右兄弟，因此要对之前的二叉树做一个小小的改动：

//创建一个树的左子女，右兄弟结构
typedef struct node
{
    int data;
    node *firstChild=NULL;
    node *nextSibling=NULL;
}TreeNode,*BinTree;

那么这样结构就出来了~

第二步：

建立一个图

话不多说，直接上代码：

//按照图的结构创建邻接表表示的图
void creatGraph(ALGraph &G)
{
    cout << "请输入图的顶点数目：" ;
    cin >> G.vexnum ;//ok
    cout << "请输入图的边的数目：" ;
    cin >> G.arcnum ;//ok
    cout << "顶点赋值：" ;
    for(int i=1;i<=G.vexnum;i++)
    {
        cin >> G.vertices[i].data;
        G.vertices[i].firstarc=NULL;//ok
    }
    for(int j=1;j<=G.arcnum;j++)//创建领接表,每一条边
    {
        int point1,point2;
        cout << "边赋值：" ;
        cin>> point1 >> point2 ;
        ArcNode *a1 = new ArcNode;//创建新边,从1到2
        a1->adjvex=point2;
        a1->nextarc=G.vertices[point1].firstarc;
        G.vertices[point1].firstarc=a1;
        ArcNode *a2 = new ArcNode;//创建新边,从2到1
        a2->adjvex=point1;
        a2->nextarc=G.vertices[point2].firstarc;
        G.vertices[point2].firstarc=a2;
    }
   cout << endl;
}

//销毁图
void Destroy(ALGraph &G)
{
    for(int i=1;i<=G.vexnum;i++)
    {
        G.vertices[i].firstarc->nextarc=NULL;
    }
    cout << "销毁成功！" << endl;
}

这部分还是比较简单的，那么让我们大家头疼的自然是第三步：生成一棵树。

看到这里大家不禁会问：题目说的生成森林，那你这一棵树有什么用呢？

不知道大家注意到没有：左子女-右兄弟这种类型的树，正好就是用来存储森林的最好方式！

由于右面用来存储兄弟，而根节点显然没有兄弟，那么我们正好可以将另一个树连接到这个树的右兄弟空着的节点上去，看起来非常巧妙对不对！

那么我们还是，直接上代码！

void Dfs(ALGraph G,int i,BinTree &T)
{
    visited[i]=1;
    bool first=true;//表示是否为当前节点第一个孩子
    TreeNode *locat;//同样是定位作用
    while(G.vertices[i].firstarc!=NULL)//从此节点出发，访问邻接节点。
    {
        if(visited[G.vertices[i].firstarc->adjvex]==0)
        {
            visited[G.vertices[i].firstarc->adjvex]=1;
            TreeNode *t=new TreeNode;//建立一颗小树
            t->data=G.vertices[i].firstarc->adjvex;
            if(first)//是当前节点第一个孩子
            {
                T->nextSibling=t;//建立右孩子
                first=false;//表示不是传进来的第一个孩子,则是孩子们的兄弟
            }
            else
            {
                locat->nextSibling=t;
            }
            locat=t;
            Dfs(G,G.vertices[i].firstarc->adjvex,t);//继续对小树找兄弟
        }
        G.vertices[i].firstarc=G.vertices[i].firstarc->nextarc;
    }
}

void DFS_Traverse(ALGraph G,BinTree &T)
{
    TreeNode *locat;//此处定义一个定位指针，用来定位当前树的位置
    for(int i=1;i<=G.vexnum;i++)
    {
        visited[i]=0;
    }
    for(int i=1;i<=G.vexnum;i++)
    {
        if(visited[i]==0)
        {
            TreeNode *t=new TreeNode;//这代表一个小树
            t->data=G.vertices[i].data;
            if(T==NULL)
            {
                T=t;//若树为空，建立头节点
            }
            else
            {
                locat->nextSibling=t;//若树不空，则是森林，插入右兄弟
            }
            locat=t;//定位至小树
            Dfs(G,i,locat);//建立小树
        }
    }
}

//建立图深度优先搜索森林
void DFSForest(ALGraph G,BinTree &T)
{
    DFS_Traverse(G,T);
}

这里博主用了递归的方式来建立森林，因此非常需要注重顺序的要求呦~

那么我们怎么知道我们的森林是什么样子呢？

让我们来写一个函数来帮我们检查一下~

void Display(BinTree T)
{
    if(T)
    {
        cout << T->data << ' ';
        Display(T->firstChild);
        Display(T->nextSibling);
    }
}

好了，这就是深度优先遍历生成森林的完整程序啦~

那么让我们看看整个的程序吧：

#include <iostream>

using namespace std;
#define MAXMIZE 20

int visited[MAXMIZE];

//创建一个树的左子女，右兄弟结构
typedef struct node
{
    int data;
    node *firstChild=NULL;
    node *nextSibling=NULL;
}TreeNode,*BinTree;


//创建图的邻接表结构
typedef struct ArcNode
{
    int adjvex;//边指向的顶点位置
    struct ArcNode *nextarc=NULL;//指向下一条边的指针
    int *info;//该边相关信息的指针
}ArcNode;

typedef struct VNode
{
    int data;//顶点信息
    ArcNode *firstarc;//指向第一条依附该顶点的边的指针
}VNode,AdjList[MAXMIZE];

typedef struct{
    AdjList vertices;//可以间接使用数组
    int vexnum,arcnum;//顶点，边
}ALGraph;



//按照图的结构创建邻接表表示的图
void creatGraph(ALGraph &G)
{
    cout << "请输入图的顶点数目：" ;
    cin >> G.vexnum ;//ok
    cout << "请输入图的边的数目：" ;
    cin >> G.arcnum ;//ok
    cout << "顶点赋值：" ;
    for(int i=1;i<=G.vexnum;i++)
    {
        cin >> G.vertices[i].data;
        G.vertices[i].firstarc=NULL;//ok
    }
    for(int j=1;j<=G.arcnum;j++)//创建领接表,每一条边
    {
        int point1,point2;
        cout << "边赋值：" ;
        cin>> point1 >> point2 ;
        ArcNode *a1 = new ArcNode;//创建新边,从1到2
        a1->adjvex=point2;
        a1->nextarc=G.vertices[point1].firstarc;
        G.vertices[point1].firstarc=a1;
        ArcNode *a2 = new ArcNode;//创建新边,从2到1
        a2->adjvex=point1;
        a2->nextarc=G.vertices[point2].firstarc;
        G.vertices[point2].firstarc=a2;
    }
   cout << endl;
}

//销毁图
void Destroy(ALGraph &G)
{
    for(int i=1;i<=G.vexnum;i++)
    {
        G.vertices[i].firstarc->nextarc=NULL;
    }
    cout << "销毁成功！" << endl;
}

void Dfs(ALGraph G,int i,BinTree &T)
{
    visited[i]=1;
    bool first=true;//表示是否为当前节点第一个孩子
    TreeNode *locat;//同样是定位作用
    while(G.vertices[i].firstarc!=NULL)//从此节点出发，访问邻接节点。
    {
        if(visited[G.vertices[i].firstarc->adjvex]==0)
        {
            visited[G.vertices[i].firstarc->adjvex]=1;
            TreeNode *t=new TreeNode;//建立一颗小树
            t->data=G.vertices[i].firstarc->adjvex;
            if(first)//是当前节点第一个孩子
            {
                T->nextSibling=t;//建立右孩子
                first=false;//表示不是传进来的第一个孩子,则是孩子们的兄弟
            }
            else
            {
                locat->nextSibling=t;
            }
            locat=t;
            Dfs(G,G.vertices[i].firstarc->adjvex,t);//继续对小树找兄弟
        }
        G.vertices[i].firstarc=G.vertices[i].firstarc->nextarc;
    }
}

void DFS_Traverse(ALGraph G,BinTree &T)
{
    TreeNode *locat;//此处定义一个定位指针，用来定位当前树的位置
    for(int i=1;i<=G.vexnum;i++)
    {
        visited[i]=0;
    }
    for(int i=1;i<=G.vexnum;i++)
    {
        if(visited[i]==0)
        {
            TreeNode *t=new TreeNode;//这代表一个小树
            t->data=G.vertices[i].data;
            if(T==NULL)
            {
                T=t;//若树为空，建立头节点
            }
            else
            {
                locat->nextSibling=t;//若树不空，则是森林，插入右兄弟
            }
            locat=t;//定位至小树
            Dfs(G,i,locat);//建立小树
        }
    }
}

//建立图深度优先搜索森林
void DFSForest(ALGraph G,BinTree &T)
{
    DFS_Traverse(G,T);
}

void Display(BinTree T)
{
    if(T)
    {
        cout << T->data << ' ';
        Display(T->firstChild);
        Display(T->nextSibling);
    }
}


int main()
{
    ALGraph G;
    BinTree T;
    creatGraph(G);
    DFSForest(G,T);
    Display(T);
    return 0;
}

以上！

（博主是某大一菜狗一枚，第一次写博客，错误一定非常的多，希望能和大家互相学习，共同进步鸭，希望博主期末能够及格==）

最后当然要老婆了对不对~