图的遍历

　　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;   //初始化头结点
　　} for(int k=0;k<G.arcnum;k++)   //输入各边并构造邻接表
　　{
　　cout<<＂请输入第＂<<k+1<<＂条边所对应的的两个结点＂<<endl;
　　e:  int s=LocateVex(G,v
　　1);   //确定v1在G中的位置
　　int t=LocateVex(G,v
　　2);   //确定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,v
　　2);
　　t=LocateVex(G,v
　　1);
　　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;