c++邻接表存储图（无向），并用广度优先和深度优先遍历（实验）
HighwaytoGraphics 2017-11-29
一开始我是用c写的，后面才发现广搜要用到队列，所以我就直接使用c++的STL队列来写，
因为不想再写多一个队列了。这次实验写了两个多钟，因为要边写边思考，太菜了哈哈。
主要参考《大话数据结构》这本书，然后加上自己的一些东西改编，这次实验算是完成了；
--------------------------------------------------------------------------------
首先我们来看一下邻接表是怎么存储图的，比如说下面有一个无向图
则它的邻接表是这样的，邻接表有两个部分，一个是顶点表，一个是边表。顶点表长这样
然后就看，它有好多个顶点，所以，我们给它开个数组，长这样
那个下标是输入顶点的顺序，就是一个位置
上面这一坨就是邻接表的顶点表，顾名思义，就是用来存它的顶点的一个表
然后接下来是边表，边表是用来干什么的呢？边表就是用来存一个顶点的邻接点，
如刚才的无向图，顶点v0的邻接点就是v1，v3了，v2的邻接点就是v1,v3,v4
所以由此我们可得出边表的样子，长这样
边表就是这样子，用来存顶点的邻接点的，每一行都是一个边表，所以一个顶点对应一个边表
那些箭头就是指针，指向下一个结点，然后null表示为空
现在顶点表有了，边表也有了，我们把它合并起来就很清楚，look；
这个就是一个图的邻接表了，如果是有向图，则在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域置空，如图：
②
cin>>v1>>v2;
i=local(G,v1);
j=local(G,v2);
输入每条边的两端的顶点，一般我们是从小到大输入的，例如这里我们
先是输入v0 v1 , v0 v3这样的，然后它会返回位置分别是0 1,0 3
然后后面边表的插入方法时，我用的是尾插法，因为这样才能达到跟图片一样的效果
不然用头插法的话，那个边表的顺序是反的；
当我们执行完这个CreateGraph函数的时候，就已经创建了如下图所示的邻接表了；
创建完成后，我们就可以把邻接表输出了，而且是按照图中所示一样的输出
代码如下：
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;
}
}至此，整篇文章可以结束了，有什么错误或者问题可在下方留言，
一起探讨
贴上测试效果图：
你们可以注意一下邻接表的输出跟我上面给的图是一样的
拜拜，我去做大保健了。
