c++邻接表存储图(无向),并用广度优先和深度优先遍历(实验)

HighwaytoGraphics 2017-11-29

一开始我是用c写的,后面才发现广搜要用到队列,所以我就直接使用c++的STL队列来写,

因为不想再写多一个队列了。这次实验写了两个多钟,因为要边写边思考,太菜了哈哈。

主要参考《大话数据结构》这本书,然后加上自己的一些东西改编,这次实验算是完成了;

--------------------------------------------------------------------------------

首先我们来看一下邻接表是怎么存储图的,比如说下面有一个无向图

c++邻接表存储图(无向),并用广度优先和深度优先遍历(实验)

则它的邻接表是这样的,邻接表有两个部分,一个是顶点表,一个是边表。顶点表长这样

c++邻接表存储图(无向),并用广度优先和深度优先遍历(实验)

然后就看,它有好多个顶点,所以,我们给它开个数组,长这样

c++邻接表存储图(无向),并用广度优先和深度优先遍历(实验)那个下标是输入顶点的顺序,就是一个位置

上面这一坨就是邻接表的顶点表,顾名思义,就是用来存它的顶点的一个表

然后接下来是边表,边表是用来干什么的呢?边表就是用来存一个顶点的邻接点,

如刚才的无向图,顶点v0的邻接点就是v1,v3了,v2的邻接点就是v1,v3,v4

所以由此我们可得出边表的样子,长这样

c++邻接表存储图(无向),并用广度优先和深度优先遍历(实验)

边表就是这样子,用来存顶点的邻接点的,每一行都是一个边表,所以一个顶点对应一个边表

那些箭头就是指针,指向下一个结点,然后null表示为空

现在顶点表有了,边表也有了,我们把它合并起来就很清楚,look;

c++邻接表存储图(无向),并用广度优先和深度优先遍历(实验)

这个就是一个图的邻接表了,如果是有向图,则在adjvex和next中间加多一个weight用来存储权值就行了,但在这我就不再讲了

好了,图出来了,看看代码怎么实现;

首先,我们得定义好顶点表和边表的结构,因为它们都是一种新的数据类型

代码如下:

//边表节点结构,一个adjvex用来存储邻接点的位置,一个next指针用来指向下一个节点
typedef struct EdgeNode
{
    int adjvex;
    struct EdgeNode * next;
} EdgeNode;

//顶点表节点结构,一个data用来存储数据,一个firstedge是用来指向边表的第一个节点
typedef struct
{
    string data;
    EdgeNode * firstedge;
} AdjList;

然后我们就可以定义一个图的邻接表了,这样

//里面的adjList[15]表示我给顶点表开了15的单位大小,然后numVertex,numEdge是一个图的顶点数和边数
typedef struct
{
    AdjList adjList[15];
    int numVertex,numEdge;
} GraphAdjList;

所以后面我们想定义一个新的图的邻接表,可以直接 GraphAdjList G 就行了;

重点来了,定义图的邻接表我们搞定了,接下来就是创建了

在此之前我们得先看看一个东西

那就是写一个函数,用来返回一个顶点所在的位置,这个会有用到

代码如下:

//这个函数是这样的,它会遍历图的顶点,然后返回一个位置(其实也就是它所在的下标)
int local(GraphAdjList & G,string val)
{
    for(int i=0; i<G.numVertex; i++)
    {
        if(G.adjList[i].data==val)
            return i;
    }
    return -1;
}
//比如v2的位置是在2 这个可以看上面的顶点表图

接下来就是创建一个图的邻接表,我会边用代码边用图来表示,这样就可以更好的理解代码了

创建图的代码如下

void CreateGraph(GraphAdjList & G)
{
    int i,j,k;
    string v1,v2;
    EdgeNode * e,* p,*q;
    cout<<"请输入顶点数和边数,并以空格隔开:"<<endl;
    cin>>G.numVertex>>G.numEdge;
    cout<<"请输入顶点的信息:"<<endl;
    for(i=0; i<(G.numVertex); i++)
    {
        cout<<"第"<<i+1<<"个顶点:"<<endl;
        cin>>G.adjList[i].data;
        G.adjList[i].firstedge=NULL;
    }
    for(k=0; k<(G.numEdge); k++)
    {
        cout<<"请输入边(Vi,Vj)上的顶点信息:"<<endl;
        cin>>v1>>v2;
        i=local(G,v1);
        j=local(G,v2);

        if(G.adjList[i].firstedge==NULL)
        {
            e= new EdgeNode;
            e->adjvex=j;
            e->next=NULL;
            G.adjList[i].firstedge=e;
        }
        else
        {
            p=G.adjList[i].firstedge;
            while(p->next!=NULL)
            {
                p=p->next;
            }
            e = new EdgeNode;
            e->adjvex=j;
            e->next=NULL;
            p->next=e;
        }
        if(G.adjList[j].firstedge==NULL)
        {
            e= new EdgeNode;
            e->adjvex=i;
            e->next=NULL;
            G.adjList[j].firstedge=e;
        }
        else
        {
            p=G.adjList[j].firstedge;
            while(p->next!=NULL)
            {
                p=p->next;
            }
            e = new EdgeNode;
            e->adjvex=i;
            e->next=NULL;
            p->next=e;
        }
    }
}

接下来我们拆分一些主要代码,看看是怎么实现的;

cin>>G.adjList[i].data;

G.adjList[i].firstedge=NULL;

这里是往顶点表插入顶点,并把firstedge域置空,如图:

c++邻接表存储图(无向),并用广度优先和深度优先遍历(实验)

cin>>v1>>v2;

i=local(G,v1);

j=local(G,v2);

输入每条边的两端的顶点,一般我们是从小到大输入的,例如这里我们

先是输入v0 v1 , v0 v3这样的,然后它会返回位置分别是0 1,0 3

然后后面边表的插入方法时,我用的是尾插法,因为这样才能达到跟图片一样的效果

不然用头插法的话,那个边表的顺序是反的;

当我们执行完这个CreateGraph函数的时候,就已经创建了如下图所示的邻接表了;

c++邻接表存储图(无向),并用广度优先和深度优先遍历(实验)

创建完成后,我们就可以把邻接表输出了,而且是按照图中所示一样的输出

代码如下:

void Prin(GraphAdjList & G)
{
    cout<<"所建立的邻接表如以下所示:"<<endl;
    for(int i=0; i<G.numVertex; i++)
    {
        cout<<G.adjList[i].data;             //先输出顶点信息
        EdgeNode * e = G.adjList[i].firstedge;
        while(e)                              //然后就开始遍历输出每个边表所存储的邻接点的下标
        {
            cout<<"-->"<<e->adjvex;
            e=e->next;
        }
        cout<<endl;
    }
}

至此,我们创建一个图的邻接表并可以输出该邻接表了,接下来我们

就是广度优先遍历和深度优先遍历了

关于这两个遍历的定义我也不多讲了,你们可以查资料,我直接就贴

上代码就好了

①深度优先遍历

这个遍历的重点就是它的算法

void DFS(GraphAdjList & G,int i)
{

    EdgeNode * p;
    DFSvisited[i]=true;
    cout<<G.adjList[i].data<<"  ";
    p=G.adjList[i].firstedge;
    while(p)
    {
        if(!DFSvisited[p->adjvex])
            DFS(G,p->adjvex);
        p=p->next;
    }
}

不断的递归遍历一个顶点的边表

然后就是使用这个算法了

void DFSTraverse(GraphAdjList & G)
{
    for(int i=0; i<G.numVertex; i++)
        DFSvisited[i]=false;
    for(int i=0; i<G.numVertex; i++)
    {
        if(!DFSvisited[i])
            DFS(G,i);
    }
}

所以这两部分代码结合起来就是深度优先遍历了

对了,那个DFSvisited[i]是一个bool型的数组,

用来标记是否遍历过的,可以在前面加上

bool DFSvisited[50];  //用于深搜的标记数组
bool BFSvisited[50];  //用于广搜的标记数组

②广度优先遍历

这个遍历直接一个函数就能搞定,需要用到队列,

相信你们既然在看图的部分的话,那么队列肯定

也早已学会了,嘿嘿。

void BFSTraverse(GraphAdjList & G)
{
    EdgeNode * p;
    queue<int>q;
    for(int i=0; i<G.numVertex; i++)
        BFSvisited[i]=false;
    for(int i=0; i<G.numVertex; i++)
    {
        if(!BFSvisited[i])
        {
            BFSvisited[i]=true;
            cout<<G.adjList[i].data<<"  ";
            q.push(i);
            while(!q.empty())
            {
                int count =q.front();
                q.pop();
                p=G.adjList[count].firstedge;
                while(p)
                {
                    if(!BFSvisited[p->adjvex])
                    {
                        BFSvisited[p->adjvex]=true;
                        cout<<G.adjList[p->adjvex].data<<"  ";
                        q.push(p->adjvex);
                    }
                    p=p->next;
                }
            }
        }
    }
}

啊咧咧,还有一个销毁图的操作

void DestoryGraph(GraphAdjList & G)
{
    EdgeNode * p = NULL;
    for(int i=0; i<G.numVertex; i++)
    {
        p=G.adjList[i].firstedge;
        while(p)
        {
            EdgeNode * temp = p;
            p=p->next;
            delete temp;
        }
        G.adjList[i].firstedge=NULL;
    }
}

至此,整篇文章可以结束了,有什么错误或者问题可在下方留言,

一起探讨

贴上测试效果图:

c++邻接表存储图(无向),并用广度优先和深度优先遍历(实验)

你们可以注意一下邻接表的输出跟我上面给的图是一样的

拜拜,我去做大保健了。

相关推荐