当前位置：文档之家› 图遍历的演示实习报告

图遍历的演示实习报告

图遍历的演示

题目:试设计一个程序,演示在连通和非连通的无向图上访问全部结点的操作

班级：***姓名：***学号：*** 完成日期：

一、需求分析

1、以邻接多重表为存储结构；

2、实现连通和非连通的无向图的深度优先和广度优先遍历；

3、要求利用栈实现无向图的广度和深度优先遍历；

4、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和生成树的边集；

5、用凹入表打印生成树；

6、求出从一个结点到另外一个结点，但不经过另外一个指定结点的所有简单路径；6、本程序用C++语言编写，在TURBO C++ 3.0环境下通过。

二、概要设计

1、设定图的抽象数据类型:

ADT Graph{

数据对象V:V是具有相同特性的数据元素的集合,称为点集.

数据关系R:

R={VR}

VR={(v,w)|v,w属于V,(v,w)表示v和w之间存在的路径} 基本操作P:

CreatGraph(&G,V,VR)

初始条件:V是图的顶点集,VR是图中弧的集合.

操作结果:按V和VR是定义构造图G.

DestroyGraph(&G)

初始条件:图G存在

操作结果:销毁图G

LocateVex(G,u)

初始条件: 图G存在,u和G中顶点有相同的特征

操作结果:若图G中存在顶点u,则返回该顶点在图中的位置;否则返回其他信息GetVex(G,v)

初始条件: 图G存在,v是G中顶点

操作结果:返回v的值

FirstAjvex(G,v)

初始条件: 图G存在,v是G中顶点

操作结果:返回v的第一个邻接顶点,若顶在图中没有邻接顶点,则返回为空NextAjvex(G,v,w)

初始条件: 图G存在,v是G中顶点,w是v的邻接顶点

操作结果:返回v的下一个邻接顶点,若w是v的最后一个邻接顶点,则返回空DeleteVexx(&G,v)

初始条件: 图G存在,v是G中顶点

操作结果:删除顶点v已经其相关的弧

DFSTraverse(G,visit())

初始条件: 图G存在,visit的顶点的应用函数

操作结果: 对图进行深度优先遍历,在遍历过程中对每个结点调用visit函数一次,一旦visit失败,则操作失败

BFSTraverse(G,visit())

初始条件: 图G存在,visit的顶点的应用函数

操作结果:对图进行广度优先遍历,在遍历过程中对每个结点调用visit函数一次,一旦visit失败,则操作失败

}ADT Graph

2、设定栈的抽象数据类型：

ADT Stack{

数据对象：D={ai | ai∈CharSet，i=1，2，……，n，n≥0}

数据关系：R1={ | ai-1,ai∈D,i=2，……，n}

基本操作：

InitStack(&S)

操作结果：构造一个空栈S。

DestroyStack(&S)

初始条件：栈S已存在。

操作结果：栈S被销毁。

Push(&S,e);

初始条件：栈S已存在。

操作结果：在栈S的栈顶插入新的栈顶元素e。

Pop(&S,e);

初始条件：栈S已存在。

操作结果：删除S的栈顶元素，并以e返回其值。

StackEmpty(S)

初始条件：栈S已存在。

操作结果：若S为空栈，则返回TRUE，否则返回FALSE。

}ADT Stack

3、设定队列的抽象数据类型：

ADT Queue{

数据对象:D={ai|ai属于Elemset,i=1,2….,n,n>=0}

数据关系:R1={|ai-1,ai属于D,i=1,2,…,n}

约定ai为端为队列头,an为队列尾

基本操作:

InitQueue(&Q)

操作结果:构造一个空队列Q

DestryoQueue(&Q)

初始条件：队列Q已存在。

操作结果：队列Q被销毁，不再存在。

EnQueue(&Q,e)

初始条件:队列Q已经存在

操作结果:插入元素e为Q的新的队尾元素

DeQueue(&Q,&E)

初始条件:Q为非空队列

操作结果:删除Q的队尾元素,并用e返回其值

QueueEmpty(Q)

初始条件:队列已经存在

操作结果:若队列为空,则返回TRUE,否则返回FLASE

}ADT Queue

4、本程序包含九个模块：

1）主程序模块

void main ()

{

手动构造一个图；

从文件导入一个图；

显示图的信息；

进行深度优先遍历图；

进行广度优先遍历图；

保存图到一个文件；

寻找路径；

销毁一个图；

}；

2）手动构造一个图-自己输入图的顶点和边生成一个图；

3）从文件导入一个图；

4）显示图的信息-打印图的所有顶点和边；

5）进行深度优先遍历图-打出遍历的结点序列和边集；

6）进行广度优先遍历图-打出遍历的结点序列和边集；

7）保存图到一个文件；

8）寻找从起点到终点，但中间不经过某点的所有简单路径；

9）销毁图。

三、详细设计

1、顶点,边和图类型

#define MAX_INFO 10 /* 相关信息字符串的最大长度+1 */

#define MAX_VERTEX_NUM 20 /* 图中顶点数的最大值*/

typedef char InfoType; /*相关信息类型*/

typedef char VertexType; /* 字符类型 */

typedef enum{unvisited,visited}VisitIf;

typedef struct EBox{

VisitIf mark; /* 访问标记 */

int ivex,jvex; /* 该边依附的两个顶点的位置 */

struct EBox *ilink,*jlink; /* 分别指向依附这两个顶点的下一条边 */ InfoType *info; /* 该边信息指针 */

}EBox;

typedef struct{

VertexType data;

EBox *firstedge; /* 指向第一条依附该顶点的边 */

}VexBox;

typedef struct{

VexBox adjmulist[MAX_VERTEX_NUM];

int vexnum,edgenum; /* 无向图的当前顶点数和边数 */

}AMLGraph;

图的基本操作如下：

int LocateVex(AMLGraph G,VertexType u)；

//查G和u有相同特征的顶点，若存在则返回该顶点在无向图中位置;否则返回-1。VertexType& GetVex(AMLGraph G,int v)；

//以v返回邻接多重表中序号为i的顶点。

int FirstAdjVex(AMLGraph G,VertexType v)；

//返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1。

int NextAdjVex(AMLGraph G,VertexType v,VertexType w)；

//返回v的(相对于w的)下一个邻接顶点的序号若w是v的最后一个邻接点,则返回-1。void CreateGraph(AMLGraph &G)；

//采用邻接多重表存储结构,构造无向图G。

Status DeleteArc(AMLGraph &G,VertexType v,VertexType w)；

//在G中删除边。

Status DeleteVex(AMLGraph &G,VertexType v)；

//在G中删除顶点v及其相关的边。

void DestroyGraph(AMLGraph &G)；

//销毁一个图

void Display(AMLGraph G)；

//输出无向图的邻接多重表G。

void DFSTraverse(AMLGraph G,VertexType start,int(*visit)(VertexType))；

//从start顶点起,（利用栈非递归）深度优先遍历图G。

void BFSTraverse(AMLGraph G,VertexType start,int(*Visit)(VertexType))；

//从start顶点起,广度优先遍历图G。

void MarkUnvizited(AMLGraph G)；

//置边的访问标记为未被访问。

其中部分操作的伪码算法如下：

void CreateGraph(AMLGraph &G)

{ /* 采用邻接多重表存储结构,构造无向图G */

DestroyGraph(G); /*如果图不空,先销毁它*/

输入无向图的顶点数G.vexnum；

输入无向图的边数G.edgenum；

输入顶点的信息IncInfo；

依次输入无向图的所有顶点；

for(k=0;k

{

读入两个顶点va、vb；

i=LocateVex(G,va); /* 一端 */

j=LocateVex(G,vb); /* 另一端 */

p=(EBox*)malloc(sizeof(EBox));

p->mark=unvisited; /* 设初值 */

p->ivex=i;

p->jvex=j;

p->info=NULL;

p->ilink=G.adjmulist[i].firstedge; /* 插在表头 */

G.adjmulist[i].firstedge=p;

p->jlink=G.adjmulist[j].firstedge; /* 插在表头 */

G.adjmulist[j].firstedge=p;

}

void Display(AMLGraph G)

{ /* 输出无向图的邻接多重表G */

MarkUnvizited(G);

输出无向图的所有顶点；

for(i=0;i

{

p=G.adjmulist[i].firstedge;

while(p)

if(p->ivex==i) /* 边的i端与该顶点有关 */

{

if(!p->mark) /* 只输出一次 */

{

cout<jvex].data<

p->mark=visited;

}

p=p->ilink;

}

else /* 边的j端与该顶点有关 */

{

if(!p->mark) /* 只输出一次 */

{

cout<ivex].data<<'-'<

p->mark=visited;

}

p=p->jlink;

}

cout<

}

void DFSTraverse(AMLGraph G,VertexType start,int(*visit)(VertexType))

{ /*从start顶点起,深度优先遍历图G(非递归算法)*/

InitStack(S);

w=LocateVex(G,start); /*先确定起点start在无向图中的位置*/

for(v=0;v

Visited[v]=0; /*置初值 */

for(v=0;v

if(!Visited[(v+w)%G.vexnum])

{

Push(S,(v+w)%G.vexnum); /*未访问，就进栈*/

while(!StackEmpty(S))

{

Pop(S,u);

if(!Visited[u])

{

Visited[u]=1; /*未访问的标志设为访问状态，并输出它的值*/ visit(G.adjmulist[u].data);

for(w=FirstAdjVex(G,G.adjmulist[u].data);w>=0;

w=NextAdjVex(G,G.adjmulist[u].data,G.adjmulist[w].data)) if(!Visited[w])

Push(S,w);

}

DestroyStack(S); /*销毁栈,释放其空间*/

}

void BFSTraverse(AMLGraph G,VertexType start,int(*Visit)(VertexType)) { /*从start顶点起,广度优先遍历图G*/

for(v=0;v

Visited[v]=0; /* 置初值 */

InitQueue(Q);

z=LocateVex(G,start); /*先确定起点start在无向图中的位置*/

for(v=0;v

if(!Visited[(v+z)%G.vexnum]) /* v尚未访问 */

{

Visited[(v+z)%G.vexnum]=1; /* 设置访问标志为TRUE(已访问) */ Visit(G.adjmulist[(v+z)%G.vexnum].data);

EnQueue(Q,(v+z)%G.vexnum);

while(!QueueEmpty(Q)) /* 队列不空 */

{

DeQueue(Q,u);

for(w=FirstAdjVex(G,G.adjmulist[u].data);w>=0;

w=NextAdjVex(G,G.adjmulist[u].data,G.adjmulist[w].data)) if(!Visited[w])

{

Visited[w]=1;

Visit(G.adjmulist[w].data);

EnQueue(Q,w);

}

DestroyQueue(Q); /*销毁队列,释放其占用空间*/

}

2、栈类型

#define STACK_INIT_SIZE 100 /* 存储空间初始分量*/ #define STACKINCREMENT 10 /* 存储空间分配增量*/ typedef int SElemType;

typedef struct{

SElemType *base;

SElemType *top; /*栈顶指针*/

int stacksize;

}SqStack;

栈的基本操作如下：

Status InitStack(SqStack &S)；

//构造一个空栈S。

Status DestroyStack(SqStack &S)；

//销毁栈S(无论空否均可)。

Status Push(SqStack &S,SElemType e)；

//在S的栈顶插入新的栈顶元素e。

Status Pop(SqStack &S,SElemType &e)；

//删除S的栈顶元素并以e带回其值。

Status StackEmpty(SqStack S)；

//若S为空栈，则返回TRUE，否则返回FALSE。

3、队列类型

typedef int QelemType；

typedef struct QNode{

QElemType data;

struct QNode *next;

}QNode,*QueuePtr;

typedef struct{

QueuePtr front;

QueuePtr rear; /* 队头、队尾指针 */

}LinkQueue;

队列的基本操作如下：

Status InitQueue(LinkQueue &Q)；

//构造一个空队列Q。

Status DestroyQueue(LinkQueue &Q)；

//销毁队列Q(无论空否均可)。

Status QueueEmpty(LinkQueue Q)；

//若Q为空队列,则返回1,否则返回-1。

Status EnQueue(LinkQueue &Q,QElemType e)；

//插入元素e为Q的新的队尾元素。

Status DeQueue(LinkQueue &Q,QElemType &e)；

//若队列不空,删除Q的队头元素,用e返回其值,并返回1,否则返回-1。

4、生成树类型:

typedef struct CSNode{

VertexType data;

struct CSNode *firstchild,*nextsibling;

}CSNode,*CSTree; /*树的二叉链表(孩子-兄弟)存储结构*/

生成树的操作：

void DFSTree(AMLGraph G,int v,CSTree &DT)；

//从第v个顶点出发深度遍历图G,建立以DT为根的生成树。

void DFSForest(AMLGraph G,VertexType start,CSTree &DT)；

//建立图G的深度优先生成森林的(最左)孩子(右)兄弟链表DT。

void PrintTraverse(CSTree T)；

//打印图G的遍历生成树的边。

void PrintAllTraverse(CSTree T)

//打印图G的遍历生成森林的边。

void BFSTree(AMLGraph G,int v,CSTree &BT)；

//从第v个顶点出发广度遍历图G,建立以BT为根的生成树。

void BFSForest(AMLGraph G,VertexType start,CSTree &BT)；

//建立图G的广度优先生成森林的(最左)孩子(右)兄弟链表BT。

void PrintCSTree(CSTree T,int i)；

//用凹入表方式打印一棵以孩子-兄弟链表为存储结构的树。

void PrintCSForest(CSTree T)；

//用凹入表方式打印一棵以孩子-兄弟链表为存储结构的森林。

其中部分操作的伪码算法如下：

void DFSTree(AMLGraph G,int v,CSTree &DT)

{ /*从第v个顶点出发深度遍历图G,建立以DT为根的生成树*/

first=1;

Visited[v]=1;

for(w=FirstAdjVex(G,G.adjmulist[v].data);w>=0;

w=NextAdjVex(G,G.adjmulist[v].data,G.adjmulist[w].data))

if(!Visited[w])

{

p=(CSTree)malloc(sizeof(CSNode)); /*分配孩子结点*/

strcpy(p->data,G.adjmulist[w].data);

p->firstchild=NULL;

p->nextsibling=NULL;

if(first) /*w是v的第一个未被访问的邻接顶点是根的左孩子结点*/ {

DT->firstchild=p;

first=0;

}

else /*w是v的其他未被访问的邻接顶点是上一邻接顶点的右兄弟结点*/ q->nextsibling=p;

q=p;

DFSTree(G,w,q); /*从第w个顶点出发深度优先遍历图G,建立子生成树q*/

}

void BFSTree(AMLGraph G,int v,CSTree &BT)

{ /*从第v个顶点出发广度遍历图G,建立以BT为根的生成树*/

r=BT;

i=j=0;

Visited[v]=1;

InitQueue(Q);

EnQueue(Q,v); /*先把第一个顶点入队列*/

while(!QueueEmpty(Q))

{

first=1;

DeQueue(Q,u);

for(w=FirstAdjVex(G,G.adjmulist[u].data);w>=0;

w=NextAdjVex(G,G.adjmulist[u].data,G.adjmulist[w].data))

if(!Visited[w])

{

Visited[w]=1;

p=(CSTree)malloc(sizeof(CSNode));

strcpy(p->data,G.adjmulist[w].data);

p->firstchild=NULL;

p->nextsibling=NULL;

if(first) /*w是v的第一个未被访问的邻接顶点是根的左孩子结点*/ {

r->firstchild=p;

first=0;

}

else /*w是v的其他未被访问的邻接顶点是上一邻接顶点的右兄弟结点*/ q->nextsibling=p;

cur[i++]=p; /*用一个数组指针保存生成树的根*/

q=p;

EnQueue(Q,w);

}

r=cur[j++]; /*回朔到上一棵生成树的根*/

}

DestroyQueue(Q);

}

void PrintCSTree(CSTree T,int i)

{ /*用凹入表方式打印一棵以孩子-兄弟链表为存储结构的树*/

for(j=1;j<=i;j++)

cout<

cout<data<

for(p=T->firstchild;p;p=p->nextsibling)

PrintCSTree(p,i+1); /*打印子树*/

}

void PrintCSForest(CSTree T)

{ /*用凹入表方式打印一棵以孩子-兄弟链表为存储结构的森树*/

for(p=T;p;p=p->nextsibling)

{

cout<<"第 "<

PrintCSTree(p,0);

}

5、主程序和其他伪码算法

void main ()

{

显示菜单；

输入功能选择键；

switch(flag)

{

case 1:手动构造一个图；

case 2:从文件导入一个图；

case 3:显示图的信息；

case 4:进行深度优先遍历图；

case 5:进行广度优先遍历图；

case 6:保存图到一个文件；

case 7:寻找路径；

case 8:销毁图；

case 9:退出程序；

}

销毁图；

}

int Visited[MAX_VERTEX_NUM]; /*访问标志数组(全局量) */

void AllPath(AMLGraph G,VertexType start,VertexType nopass,VertexType end,int k) { /*寻找路径*/

Path[k]=start; /*加入当前路径中*/

l=LocateVex(G,nopass);

u=LocateVex(G,start);

Visited[u]=1;

if(start==end) /*找到了一条简单路径*/

{

cout<

for(i=1;Path[i];i++)

cout<<"->"<

cout<

}

else

for(w=FirstAdjVex(G,G.adjmulist[u].data);w>=0;

w=NextAdjVex(G,G.adjmulist[u].data,G.adjmulist[w].data))

{

if(w==l)

continue; /*如果找到那个不想经过的点,就绕过它,相当不执行后面的语句*/ if(!Visited[w])

{

temp=G.adjmulist[w].data;

AllPath(G,temp,nopass,end,k+1); /*继续寻找*/

}

Visited[u]=0;

Path[k]=0; /*回溯*/

}

void SaveGraph(AMLGraph G) /*保存图的信息*/

{

建立输出文件流对象outgraph；

输入文件名fileName；

outgraph.open(fileName,ios::out);连接文件,指定打开方式

if(!outgraph) /*调用重载算符函数测试流*/

{

cerr<<"文件不能打开."<

abort();

}

向流插入数据；

outgraph.close(); /*关闭文件*/

}

void LoadGraph(AMLGraph &G)

{

建立输入文件流对象ingraph；

输入文件名fileName；

if(!ingraph)

{

cerr<<"文件不能打开."<

abort();

}

向流输出数据；

ingraph.close(); /*关闭文件*/

}

visit(VertexType v)

{ /*输出结点*/

cout<

return OK;

}

void message() /*菜单显示*/

{

cout<<"\n\t\t* * * * * * * * * * * * * * * * * * * *\n";

cout<<"\t\t*\t1:手动构造一个图\t *\n";

cout<<"\t\t*\t2:从文件导入一个图\t *\n";

cout<<"\t\t*\t3:显示图的信息\t *\n";

cout<<"\t\t*\t4:进行深度优先遍历图\t *\n";

cout<<"\t\t*\t5:进行广度优先遍历图\t *\n";

cout<<"\t\t*\t6:保存图到一个文件\t *\n";

cout<<"\t\t*\t7:寻找路径\t *\n";

cout<<"\t\t*\t8:销毁图\t *\n";

cout<<"\t\t*\t9:退出程序\t\t *\n";

cout<<"\t\t* * * * * * * * * * * * * * * * * * * *\n";

}

四、调试分析

1、本程序以邻接多重表为存储结构。这个程序涉及到图的生成和图的深度以及广度遍历,

文件的保存和读取，还有栈和队列的操作，另外还有森林的生成和打印，路径的寻找。

2、本程序不仅可以进行连通无向图的遍历，还可以进行非连通图的遍历。为了方便显示和

理解，现在暂且用一个大写字母表示一个顶点。边还可以附加信息，但为了方便操作，暂且不输入信息。已经先把图的相关信息保存在了文本文档里，所以要测试时直接从文件导入，可以减少用手输入的麻烦，同时也可以减少输入的错误。

3、由于构造图时，后输入的边是插在先输入的边的前面。所以在输入边时，可以按字母从

大到小的顺序输入。那么显示图的时候就可以按字母从小到大的顺序显示。

4、程序定义了一个二倍顶点长的数组存放输入的边，以便程序可以把它保存到文件里。故

耗费了一定的内存空间。

五、用户手册

1、本程序的运行环境DOS操作系统，GTraverse.exe

2、进入演示程序后即显示一个有功能选择的界面，如下：

3、选择操作1：程序就提示分别输入无向图的顶点数，边数，边的信息，顶点和边的值：

输入完成后，程序提示按任一键返回菜单：

4、选择操作2：程序提示输入一个存有图信息文件的路径去导入一个图：

如果导入成功，它会显示导入成功，并提示按任一键返回。

5、选择操作3：程序显示图的顶点和边的信息。

6、选择操作4：系统提示输入遍历图的起始点，程序运行后，首先显示深度优先遍历的访

问结点序列和生成树的边集。然后再提示按任一键继续显示深度优先遍历

的生成森林。

7、选择操作5：系统提示输入遍历图的起始点，程序运行后，首先显示广度优先遍历的访

问结点序列和生成树的边集。然后再提示按任一键继续显示广度优先遍历

的生成森林。

8、选择操作6：程序会提示输入要存放图信息的文件的路径：

9、选择操作7：程序会提示输入路径遍历的起点start，终点end，不想经过的点nopass。

10、选择操作8：销毁一个图。

11、选择操作9：退出程序。

六、测试结果

1、数据可以任意输入,但是顶点数不要太多，不然占用太多内存，会导致死机。

2、遍历一个连通的无向图，如遍历以下这个连通无向图：

○A

○B○C

○D○E○F○G

○H

1）选择操作1，分别进行以下操作：

请输入图的节点数 (EG. G.vexnum=10): 8

请输入图的边数 (EG. G.edgenum=4): 9

请输入8 个节点的表示值:

请输入有序的边(用空格作间隔):

F G

E H

D H

C G

C F

B E

B D

A C

A B

2) 选择操作3，输出图的信息如下：

这个图有 8 叶子:

A B C D E F G H

这个图有 9 边:

A-B A-C

B-D B-E

C-F C-G

D-H

E-H

F-G

3）选择操作4，输入遍历起点，如A（也可以输入B，C……） *****深度优先遍历图的结果***** 深度优先遍历的访问结点序列:

A C G F

B E H D

深度优先遍历生成树的边集:

A-B B-D D-H H-E A-C C-F F-G

深度优先遍历的生成森林:

第1个树:

4）选择操作5，输入遍历起点，如A（也可以输入B，C……） *****广度优先遍历图的结果***** 广度优先遍历的访问结点序列:

A B C D E F G H

广度优先遍历生成树的边集:

A-B B-D D-H B-E A-C C-F C-G

广度优先遍历的生成森林:

第1个树:

5) 选择操作7，输入以下信息：

请输入第一个结点: A

请输入最后一个结点: H

请输入您不想通过的结点: D

所有的路径从 A 结点到 H 结点和不想通过 D 结点的是:

A->B->E->H

3、选择操作8销毁图，好继续下一个测试。

4、遍历一个非连通的无向图，如遍历以下这个非连通无向图：

○A○C○D

○B○G○E○F○H

○I

1）选择操作1，分别进行以下操作：

请输入图的节点数 (EG. G.vexnum=10): 9

请输入图的边数 (EG. G.edgenum=4):8

请输入9 个节点的表示值:

请输入有序的边(用空格作间隔):

F I

D H

D F

C G

C E

A B

2）选择操作3，输出图的信息如下：

这个图有 9 叶子:

A B C D E F G H I

这个图有 7 边:

A-B

C-E C-G

D-F D-H

E-G

F-I

3）选择操作4，输入遍历起点，如A（也可以输入B，C……）

*****深度优先遍历图的结果***** 深度优先遍历的访问结点序列:

A B C G E D H F I

深度优先遍历生成树的边集:

A-B C-E E-G D-F F-I D-H

深度优先遍历的生成森林:

第1个树:

第2个树:

第3个树:

4) 选择操作5，输入遍历起点，如A（也可以输入B，C……） *****广度优先遍历图的结果***** 广度优先遍历的访问结点序列:

A B C E G D F H I

广度优先遍历生成树的边集:

A-B C-E C-G D-F F-I D-H

广度优先遍历的生成森林:

第1个树:

第2个树:

第3个树:

5) 选择操作7，输入以下信息：

请输入第一个结点:C

请输入最后一个结点: E

请输入您不想通过的结点: G

所有的路径从 C 结点到 E 结点和不想通过 G 结点的是: C->E

七、附录

源程序文件名清单：

GTraverse.cpp //主程序

GTraverse.exe //可执行文件

GTraverse.OBJ //目标源文件

1.txt //存有连通图信息的文本文档

2.txt //存有非连通图信息的文本文档

八、心得体会

这道题的完成逐步地增加了许多功能。把本来只能遍历连通图的功能上，改进为可以遍历非连通图，接着再改造为可以输出边集，后来又增加了打印生成树的功能，最后还增加了文件的保存和读取，路径的遍历。最难得是，把原来用C语言编写的程序改为用C++语言编写，虽然编写C++语言水平有限，但这个程序只是用到C++那些比较基础和简单的知识，所以对我来说，困难还不是很大。

通过这道设计题,使我更深刻的理解数据结构及其重要作用,对数据结构有了一个新的认识,深刻的认识到数据结构对于我们学习计算机的重要性和其深远但是意义.同时,通过这次课程设计,也加强我的动手能力和思维能力,可以将自己所学的知识用于实践,这不仅对自己是一次锻炼机会,而且让自己有一种成就感和自豪感,觉得自己终于可以做出一点有用的东西了。说来也奇怪，虽然连续两个通宵，但自己在设计这个程序时，却不会觉得累，也不会觉得困，这几天平均每天是睡不到六个小时，想必是自己对编写程序的兴趣和投入，使得自己顿时间觉得非常有力量。

不过,我觉得自己编写程序的一些思路算法和水平还非常有限。所以以后自己还得在C 语言和其他语言上下苦功夫。

图的深度广度优先遍历操作代码

一、实验目的 1．掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构； 2．遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和宽度优先遍历算法，复习栈和队列的应用； 3．掌握图的各种应用的算法：图的连通性、连通分量和最小生成树、拓扑排序、关键路径。二、实验内容实验内容1**图的遍历 [问题描述] 许多涉及图上操作的算法都是以图的遍历为基础的。写一个程序，演示在连通无向图上遍历全部顶点。 [基本要求] 建立图的邻接表的存储结构，实现无向图的深度优先遍历和广度优先遍历。以用户指定的顶点为起点，分别输出每种遍历下的顶点访问序列。 [实现提示] 设图的顶点不超过30个，每个顶点用一个编号表示（如果一个图有N个顶点，则它们的编号分别为1，2，…，N）。通过输入图的全部边输入一个图，每条边是两个顶点编号对，可以对边依附顶点编号的输入顺序作出限制（例如从小到大）。 [编程思路] 首先图的创建，采用邻接表建立，逆向插入到单链表中，特别注意无向是对称插入结点，且要把输入的字符在顶点数组中定位（LocateVex(Graph G,char *name)，以便后来的遍历操作，深度遍历算法采用递归调用，其中最主要的是NextAdjVex(Graph G, int v, int w)；FirstAdjVex （）函数的书写，依次递归下去，广度遍历用队列的辅助。 [程序代码] 头文件： #include #include #define MAX_VERTEX_NUM 30 #define MAX_QUEUE_NUMBER 30 #define OK 1 #define ERROR 0 #define INFEASIBLE -1

数据结构课程设计图的遍历和生成树求解

数学与计算机学院课程设计说明书课程名称: 数据结构与算法课程设计课程代码: 6014389 题目: 图的遍历和生成树求解实现年级/专业/班: 学生姓名: 学号: 开始时间: 2012 年 12 月 09 日完成时间: 2012 年 12 月 26 日课程设计成绩：指导教师签名：年月日

目录摘要 (3) 引言 (4) 1 需求分析 (5) 1.1任务与分析 (5) 1.2测试数据 (5) 2 概要设计 (5) 2.1 ADT描述 (5) 2.2程序模块结构 (7) 软件结构设计： (7) 2.3各功能模块 (7) 3 详细设计 (8) 3.1结构体定义 (19) 3.2 初始化 (22) 3.3 插入操作（四号黑体） (22) 4 调试分析 (22) 5 用户使用说明 (23) 6 测试结果 (24) 结论 (26)

摘要《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的： ?了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； ?初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； ?提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。关键词：计算机；图；算法。

图的遍历实现课程设计-数据结构-程序-图

数据结构课程设计设计说明书图的遍历的实现学生姓名英茜学号1１18064０33 班级网络1101班成绩指导教师申静数学与计算机科学学院 2０14年1 月4日

课程设计任务书 2013—２０14学年第一学期课程设计名称:数据结构课程设计课程设计题目:图的遍历实现完成期限：自2013年1２月23日至2014年１月4日共 2 周设计内容： 1. 任务说明 (1）采用邻接表存储结构创建一个图； (２）编程实现图的深度优先搜索(或广度优先搜索)遍历算法; (3) 输出遍历结果； (4) 给定具体数据调试程序。２．要求１）问题分析和任务定义：根据设计题目的要求,充分地分析和理解问题，明确问题要求做什么? 2)逻辑设计：写出抽象数据类型的定义，各个主要模块的算法,并画出模块之间的调用关系图； 3）详细设计：定义相应的存储结构并写出各函数的伪码算法。 4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。 5）程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。 6)结果分析:程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析; 7)编写课程设计报告。 3. 参考资料指导教师:申静教研室负责人：余冬梅课程设计评阅

摘要针对图问题中如何更好地实现图的遍历问题，以无向图为例,分别采用广度优先遍历和深度优先遍历的算法实现对各节点的遍历，以ＶＣ++为开发环境进行系统的设计和实现,其运行结果表明，系统能很好地完成遍历后节点的输出,实现了遍历的目的，系统界面友好,可操作性强。关键词：数据结构;存储结构；邻接矩阵

数据结构实验报告-图的遍历

数据结构实验报告实验：图的遍历一、实验目的： 1、理解并掌握图的逻辑结构和物理结构——邻接矩阵、邻接表 2、掌握图的构造方法 3、掌握图的邻接矩阵、邻接表存储方式下基本操作的实现算法 4、掌握图的深度优先遍历和广度优先原理二、实验内容： 1、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接矩阵存储改图。 2、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接表存储该图 3、深度优先遍历第一步中构造的图G，输出得到的节点序列 4、广度优先遍历第一部中构造的图G，输出得到的节点序列三、实验要求： 1、无向图中的相关信息要从终端以正确的方式输入； 2、具体的输入和输出格式不限； 3、算法要具有较好的健壮性，对错误操作要做适当处理； 4、程序算法作简短的文字注释。四、程序实现及结果： 1、邻接矩阵： #include #include #define VERTEX_MAX 30 #define MAXSIZE 20 typedef struct { int arcs[VERTEX_MAX][VERTEX_MAX] ; int vexnum,arcnum; } MGraph; void creat_MGraph1(MGraph *g) { int i,j,k; int n,m; printf("请输入顶点数和边数:"); scanf("%d%d",&n,&m); g->vexnum=n; g->arcnum=m; for (i=0;iarcs[i][j]=0;

图的遍历实验报告

实验四：图的遍历题目：图及其应用——图的遍历班级：姓名：学号：完成日期：一.需求分析 1.问题描述：很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。 2.基本要求：以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。 3.测试数据：教科书图7.33。暂时忽略里程，起点为北京。 4.实现提示：设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1,2,…,n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制，注意，生成树的边是有向边，端点顺序不能颠倒。 5.选作内容：（1）.借助于栈类型（自己定义和实现），用非递归算法实现深度优先遍历。（2）.以邻接表为存储结构，建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。二.概要设计 1.为实现上述功能，需要有一个图的抽象数据类型。该抽象数据类型的定义为： ADT Graph { 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R： R={VR} VR={ | v，w v且P(v，w)，表示从v到w得弧，谓词P(v，w)定义了弧的意义或信息} } ADT Graph 2.此抽象数据类型中的一些常量如下： #define TRUE 1 #define FALSE 0 #define OK 1 #define max_n 20 //最大顶点数 typedef char VertexType[20]; typedef enum{DG, DN, AG, AN} GraphKind; enum BOOL{False,True}; 3.树的结构体类型如下所示：

数据结构实验---图的储存与遍历

学号：姓名：实验日期： 2016.1.7 实验名称：图的存贮与遍历一、实验目的掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。二、实验内容与实验步骤题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。测试数据：如图所示题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。测试数据：如图所示 V0 V1 V2 V3 V4 三、附录：在此贴上调试好的程序。 #include #include #include V0 V1 V4 V3 V2 ??? ? ??? ? ????????=010000000101010 1000100010A 1 0 1 0 3 3 4

#define M 100 typedef struct node { char vex[M][2]; int edge[M ][ M ]; int n,e; }Graph; int visited[M]; Graph *Create_Graph() { Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph)); printf ("请输入矩阵的顶点数和边数(用逗号隔开)：\n"); scanf("%d,%d",&GA->n,&GA->e); printf ("请输入矩阵顶点信息：\n"); for(i = 0;in;i++) scanf("%s",&(GA->vex[i][0]),&(GA->vex[i][1])); for (i = 0;in;i++) for (j = 0;jn;j++) GA->edge[i][j] = 0; for (k = 0;ke;k++) { printf ("请输入第%d条边的顶点位置(i,j)和权值(用逗号隔开)：",k+1); scanf ("%d,%d,%d",&i,&j,&w); GA->edge[i][j] = w; } return(GA); } void dfs(Graph *GA, int v) { int i; printf("%c%c\n",GA->vex[v][0],GA->vex[v][1]); visited[v]=1;

数据结构图的遍历

#include"stdlib.h" #include"stdio.h" #include"malloc.h" #define INFINITY 32767 #define MAX_VERTEX_NUM 20 typedef enum{FALSE,TRUE}visited_hc; typedef enum{DG,DN,UDG,UDN}graphkind_hc; typedef struct arccell_hc {int adj; int*info; }arccell_hc,adjmatrix_hc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct {char vexs[MAX_VERTEX_NUM]; adjmatrix_hc arcs; int vexnum,arcnum; graphkind_hc kind; }mgraph_hc; typedef struct arcnode_hc {int adjvex; struct arcnode_hc *nextarc; int*info; }arcnode_hc; typedef struct vnode_hc {char data; arcnode_hc *firstarc; }vnode_hc,adjlist_hc[MAX_VERTEX_NUM]; typedef struct {adjlist_hc vertices; int vexnum,arcnum; graphkind_hc kind; }algraph_hc; int locatevex_hc(mgraph_hc*g,char v) {int i,k=0; for(i=0;ivexnum;i++) if(g->vexs[i]==v){k=i;i=g->vexnum;} return(k);}

数据结构课程设计-图的遍历和构建

图（Graph）是一种复杂的非线性结构。图可以分为无向图、有向图。若将图的每条边都赋上一个权，则称这种带权图网络。在人工智能、工程、数学、物理、化学、计算机科学等领域中，图结构有着广泛的应用。在图结构中，对结点（图中常称为顶点）的前趋和后继个数都是不加以限制的，即结点之间的关系是任意的。图中任意两个结点之间都可能相关。图有两种常用的存储表示方法：邻接矩阵表示法和邻接表表示法。在一个图中，邻接矩阵表示是唯一的，但邻接表表示不唯一。在表示的过程中还可以实现图的遍历（深度优先遍历和广度优先遍历）及求图中顶点的度。当然对于图的广度优先遍历还利用了队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）来实现。这不仅让我们巩固了之前学的队列的基本操作，还懂得了将算法相互融合和运用。

第一章课程设计目的 (3) 第二章课程设计内容和要求 (3) 2.1课程设计内容 (3) 2.1.1图的邻接矩阵的建立与输出 (3) 2.1.2图的邻接表的建立与输出 (3) 2.1.3图的遍历的实现 (4) 2.1.4 图的顶点的度 (4) 2.2 运行环境 (4) 第三章课程设计分析 (4) 3.1图的存储 (4) 3.1.1 图的邻接矩阵存储表示 (4) 3.1.2 图的邻接表存储表示 (5) 3.2 图的遍历 (5) 3.2.1 图的深度优先遍历 (5) 3.2.2 图的广度优先遍历 (6) 3.3图的顶点的度 (7) 第四章算法（数据结构）描述 (7) 4.1 图的存储结构的建立。 (7) 4.1.1 定义邻接矩阵的定义类型 (7) 4.1.2定义邻接表的边结点类型以及邻接表类型 (7) 4.1.3初始化图的邻接矩阵 (8) 4.1.4 初始化图的邻接表 (8) 4.2 图的遍历 (8) 4.2.1 深度优先遍历图 (8) 4.2.2 广度优先遍历图 (9) 4.3 main函数 (9) 4.4 图的大致流程表 (10) 第五章源代码 (10) 第六章测试结果 (20) 第七章思想总结 (21) 第八章参考文献 (22)

数据结构课程设计之图的遍历和生成树求解

##大学数据结构课程设计报告题目：图的遍历和生成树求解院（系）：计算机工程学院学生: 班级：学号: 起迄日期: 2011.6.20 指导教师:

2010—2011年度第 2 学期一、需求分析 1.问题描述：图的遍历和生成树求解实现图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（及其孩子结点）相关但只能和上一层中一个元素（即双亲结点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。生成树求解主要利用普利姆和克雷斯特算法求解最小生成树，只有强连通图才有生成树。 2.基本功能 1) 先任意创建一个图； 2) 图的DFS,BFS的递归和非递归算法的实现 3) 最小生成树（两个算法）的实现，求连通分量的实现 4) 要求用邻接矩阵、邻接表等多种结构存储实现 3.输入输出

输入数据类型为整型和字符型，输出为整型和字符二、概要设计 1.设计思路： a.图的邻接矩阵存储：根据所建无向图的结点数n,建立n*n的矩阵，其中元素全是无穷大（int_max），再将边的信息存到数组中。其中无权图的边用1表示，无边用0表示；有全图的边为权值表示，无边用∞表示。 b.图的邻接表存储：将信息通过邻接矩阵转换到邻接表中，即将邻接矩阵的每一行都转成链表的形式将有边的结点进行存储。 c.图的广度优先遍历：假设从图中的某个顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后再访问此邻接点的未被访问的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有未被访问的，则另选未被访问的重复以上步骤，是一个非递归过程。 d.图的深度优先遍历：假设从图中某顶点v出发，依依次访问v的邻接顶点，然后再继续访问这个邻接点的系一个邻接点，如此重复，直至所有的点都被访问，这是个递归的过程。 e.图的连通分量：这是对一个非强连通图的遍历，从多个结点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其连通分量的顶点集。本程序利用的图的深度优先遍历算法。 2.数据结构设计： ADT Queue{ 数据对象：D={a i | a i ∈ElemSet,i=1,2,3……，n,n≥0} 数据关系：R1={| a i-1 ,a i ∈D,i=1,2,3,……，n} 基本操作： InitQueue(&Q) 操作结果：构造一个空队列Q。 QueueEmpty(Q) 初始条件：Q为非空队列。操作结果：若Q为空队列，则返回真，否则为假。 EnQueue(&Q,e) 初始条件：Q为非空队列。操作结果：插入元素e为Q的新的队尾元素。 DeQueue(&Q,e) 初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。}ADT Queue