1．需求分析
【实验目的】
很多涉及图上操作的算法都是以图的遍历操作为基础的，通过这个实验的算法设计，可以巩固所学的有关图的基本知识。
【基本要求】
以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。
2．算法设计
1）为了实现上述程序功能，需要定义单链表的抽象数据类型：
定义边结点 ArcNode
数据成员 int adjvex;
struct ArcNode *nextarc;
定义顶点信息 VNode
数据成员 VertexType data;
ArcNode *firstarc;
定义无向图 typedef struct
数据成员 AdjList vertices;
int vexnum,arcnum;
定义链表 typedef struct LNode
数据成员 ElemType data;
struct LNode *next;
定义头结点 typedef struct QNode
数据成员 QElemType data;
struct QNode *next;
定义队列 typedef struct
数据成员 QueuePtr front;
QueuePtr rear;
2）本程序用到的主要函数：
InitQueue(LinkQueue &Q) //初始化队
EnQueue(LinkQueue &Q,QElemType e) //入队
DeQueue(LinkQueue &Q,QElemType &e) //出队
LocateVex(ALGraph G,char v) //确定v在G中的位置
CreateDG(ALGraph &G) //创建无向连通图的邻接表结构
FirstAdjvex(ALGraph G,int v) //返回G中顶点v的第一个邻接点
NextAdjVex(ALGraph G,int v,int w) //返回G中顶点v相对于w的下一个邻接点
BFSTraverse(ALGraph G) //进行深度优先遍历
DFS(ALGraph G,int v,int *visited)
DFSTraverse(ALGraph G) //进行广度优先遍历3．调试分析
刚开始输入的是abcdef可是遍历出来的是123456的数字，后来将入前的出输改写成G.vertices[w].data形式就可以了。
4．经验收获和体会
每次都要写这个，我都不知写什么好了呵呵，嗯总体来说还是那句话程序要自已编出来的才叫好。无论编得怎么样总会学到东西的，编写的同时也可以复习以前的知识这样很好。
5．测试数据及结果
6．附录
#include"iostream.h"
#include"stdlib.h"
typedef char VertexType;
typedef int QElemType;
typedef int ElemType;
typedef int Status;
#define MAX 20
#define ok 1
bool visit[MAX];
typedef struct ArcNode //定义边结点
{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode //定义顶点信息
{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX];
typedef struct //定义无向图
{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;
typedef struct LNode //定义链表
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
typedef struct QNode //定义头结点
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct //定义队列
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
Status InitQueue(LinkQueue &Q) //初始化队
{
Q.front=new QNode;
if(!Q.front)exit(-1);
Q.front->next=NULL;
Q.rear=Q.front;
return ok;
}
Status EnQueue(LinkQueue &Q,QElemType e) //入队
{
QueuePtr p;
p=new QNode;
if(!p)exit(-1);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return ok;
}
Status DeQueue(LinkQueue &Q,QElemType &e) //出队
{
if(Q.front==Q.rear)return false;
QueuePtr p;
p=Q.front->next;
Q.front->next=p->next;
e=p->data;
if(Q.rear==p)Q.rear=Q.front;
delete p;
return ok;
}
int LocateVex(ALGraph G,char v) //确定v在G中的位置
{
for(int i=0;i<G.vexnum;i++)
if(G.vertices[i].data==v)
return i;
if(i==G.vexnum)
{
cout<<"你的输入有错请重新输入"<<endl;
return -1;
}
return 0;
}
void CreateDG(ALGraph &G) //创建无向连通图的邻接表结构
{
cout<<"请输入图的结点数:"<<endl;
cin>>G.vexnum;
cout<<"请输入图的边数:"<<endl;
cin>>G.arcnum;
for(int i=0;i<G.vexnum;i++) //构造表头向量
{
cout<<"请输入第"<<i+1<<"个结点的信息"<<endl;
cin>>G.vertices[i].data;
G.vertices[i].firstarc=NULL; //初始化头结点
}
char v1,v2;
for(int k=0;k<G.arcnum;k++) //输入各边并构造邻接表
{
cout<<"请输入第"<<k+1<<"条边所对应的的两个结点"<<endl;
e:
cin>>v1>>v2;
int s=LocateVex(G,v1); //确定v1在G中的位置
int t=LocateVex(G,v2); //确定v2在G中的位置
if(s<0||t<0)
goto e;
ArcNode *p=new ArcNode;
p->adjvex=t;
ArcNode *q=G.vertices[s].firstarc; //采用头插法插入链表
G.vertices[s].firstarc=p;
p->nextarc=q; //因为是无向图，每条边对应两个结点
s=LocateVex(G,v2);
t=LocateVex(G,v1);
p=new ArcNode;
p->adjvex=t;
q=G.vertices[s].firstarc;
G.vertices[s].firstarc=p;
p->nextarc=q;
}
}
void BFSTraverse(ALGraph G) //进行广度优先遍历
{
int v,w,u;
int visited[MAX];
LinkQueue Q;
for(v=0;v<G.vexnum;++v)
visited[v]=0;
InitQueue(Q);
for(v=0;v<G.vexnum;++v)
if(visited[v]==0)
{
visited[v]=1;
cout<<G.vertices[v].data<<" ";
EnQueue(Q,v);
while(!(Q.rear==Q.front))
{
DeQueue(Q,u);
for(w=G.vertices[u].data;
G.vertices[u].firstarc!=NULL;
w=G.vertices[u].firstarc->adjvex,
G.vertices[u].firstarc=G.vertices[u].firstarc->nextarc)
if(visited[w]==0)
{
visited[w]=1;
cout<<G.vertices[w].data<<" ";
EnQueue(Q,w);
}
}
}
}
void DFS(ALGraph G,int v,int *visited)
{
int w;
visited[v]=1;
cout<<G.vertices[v].data<<" ";
for(w=G.vertices[v].data;
G.vertices[v].firstarc!=NULL;
w=G.vertices[v].firstarc->adjvex,
G.vertices[v].firstarc=G.vertices[v].firstarc->nextarc)
if(visited[w]==0)
DFS(G,w,visited);
}
void DFSTraverse(ALGraph G) //进行深度优先遍历
{
int v;
int visited[MAX];
for(v=0;v<G.vexnum;++v)
visited[v]=0;
for(v=0;v<G.vexnum;++v)
if(visited[v]==0)
DFS(G,v,visited);
}
int main()//主函数
{
ALGraph G;
CreateDG(G);
cout<<"深度优先遍历序列:";
DFSTraverse(G);
cout<<endl;
cout<<"广度优先遍历序列：";
BFSTraverse(G);
cout<<endl;
return 0;