图的遍历_自动化专业毕业论文范文-经管之家官网！

免费学术公开课,扫码加入

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;iG.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;
 cinG.vexnum;
 cout"请输入图的边数:"endl;
 cinG.arcnum;
 for(int i=0;iG.vexnum;i++)     //构造表头向量
 {
  cout"请输入第"i+1"个结点的信息"endl;
  cinG.vertices[i].data;
  G.vertices[i].firstarc=NULL;   //初始化头结点  
 }
 char v1,v2;
 for(int k=0;kG.arcnum;k++)   //输入各边并构造邻接表
 {
  cout"请输入第"k+1"条边所对应的的两个结点"endl;
e:
  cinv1v2;
  int s=LocateVex(G,v1);   //确定v1在G中的位置
  int t=LocateVex(G,v2);   //确定v2在G中的位置
  if(s0||t0)
   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;vG.vexnum;++v)
  visited[v]=0;
    InitQueue(Q);
    for(v=0;vG.vexnum;++v)
 if(visited[v]==0)
 { 
   visited[v]=1;
   coutG.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;
      coutG.vertices[w].data" ";
      EnQueue(Q,w);  
     }
   }
     }
}
void DFS(ALGraph G,int v,int *visited)
{ 
 int w;
 visited[v]=1;
 coutG.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;vG.vexnum;++v)
  visited[v]=0;
    for(v=0;vG.vexnum;++v)
  if(visited[v]==0)
  DFS(G,v,visited);
}

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

「经管之家」APP：经管人学习、答疑、交友，就上经管之家！
免流量费下载资料----在经管之家app可以下载论坛上的所有资源，并且不额外收取下载高峰期的论坛币。
涵盖所有经管领域的优秀内容----覆盖经济、管理、金融投资、计量统计、数据分析、国贸、财会等专业的学习宝库，各类资料应有尽有。
来自五湖四海的经管达人----已经有上千万的经管人来到这里，你可以找到任何学科方向、有共同话题的朋友。
经管之家（原人大经济论坛），跨越高校的围墙，带你走进经管知识的新世界。
扫描下方二维码下载并注册APP