评价网 > 科教论文 > 工学毕业论文 > 自动化论文 > 正文

图的遍历-自动化毕业论文网

2013-06-12 01:03

 

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; （科教作文网 zw.nseac.com整理）
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    //定义无向图                    

（转载自http://www.ＮＳＥＡＣ.com中国科教评价网）

{
 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; 您可以访问中国科教评价网（www.NsEac.com）查看更多相关的文章。
  }
 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) （科教作文网http://zw.ΝsΕac.cOM编辑）
  DFS(G,v,visited);
}

int main()//主函数
{
  ALGraph G;
    CreateDG(G);
  cout<<"深度优先遍历序列:";
  DFSTraverse(G);
  cout<<endl;
  cout<<"广度优先遍历序列：";
    BFSTraverse(G);
  cout<<endl;
    return 0;