当前位置：文档之家› 图及其遍历

图及其遍历

一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）

（√）（1）图可以没有边，但不能没有顶点。

（ㄨ）（2）在无向图中，（V1，V2）与（V2，V1）是两条不同的边。

（ㄨ）（3）邻接表只能用于有向图的存储。

（√）（4）一个图的邻接矩阵表示是唯一的。

（ㄨ）（5）用邻接矩阵法存储一个图时，所占用的存储空间大小与图中顶点个数无关，而只与图的边数有关。

（ㄨ）（6）有向图不能进行广度优先遍历。

（√）（7）若一个无向图的以顶点V1为起点进行深度优先遍历，所得的遍历序列唯一，则可以唯一确定该图。

（√）（8）存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角）部分就可以了。

（ㄨ）（9）用邻接表法存储图时，占用的存储空间大小只与图中的边数有关，而与结点的个数无关。（√）（10）若一个无向图中任一顶点出发，进行一次深度优先遍历，就可以访问图中所有的顶点，则该图一定是连通的。

二．填空题

（1）图常用的存储方式有邻接矩阵和邻接表等。

（2）图的遍历有：深度优先搜和广度优先搜等方法。

（3）有n条边的无向图邻接矩阵中，1的个数是 _2n____。

（4）有向图的边也称为 _ 弧___ 。

（5）图的邻接矩阵表示法是表示 __顶点____之间相邻关系的矩阵。

（6）有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的 __出度____。

（7）n个顶点e条边的图若采用邻接矩阵存储，则空间复杂度为：O（n2）。

（8）n个顶点e条边的图若采用邻接表存储，则空间复杂度为：O（n+e）。

（9）设有一稀疏图G，则G采用 _邻接表____存储比较节省空间。

（10）设有一稠密图G，则G采用 _邻接矩阵____存储比较节省空间。

（11）图的逆邻接表存储结构只适用于 __有向____图。

（12） n个顶点的完全无向图有 n(n-1)/2_ 条边。

（13）有向图的邻接表表示适于求顶点的出度。

（14）有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点V i的入度。

（15）对于具有n个顶点的图，其生成树有且仅有n-1 条边。

（16）对n个顶点，e条弧的有向图，其邻接表表示中，需要n+e 个结点。

（17）从图中某一顶点出发，访遍图中其余顶点，且使每一顶点仅被访问一次，称这一过程为图的遍历。

（18）无向图的邻接矩阵一定是对称矩阵。

（19）一个连通网的最小生成树是该图所有生成树中权最小的生成树。

（20）若要求一个稠密图G的最小生成树，最好用Prim 算法来求解。

三．选择题

（1）在一个图中，所有顶点的度数之和等于图的边数的( C )倍。

A．1/2 B. 1 C. 2 D. 4

（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的( B )倍。

A．1/2 B. 1 C. 2 D. 4

（3）对于一个具有n个顶点的有向图的边数最多有（ B ）。

A．n B．n(n-1) C．n(n-1)/2 D．2n

（4）在一个具有n个顶点的无向图中，要连通全部顶点至少需要（ C ）条边。

A．n B．n+1 C． n-1 D．n/2

（5）有8个结点的有向完全图有( C )条边。

A．14 B. 28 C. 56 D. 112

（6）深度优先遍历类似于二叉树的( A )。

A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历

（7）广度优先遍历类似于二叉树的( D )。

A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历

（8）任何一个无向连通图的最小生成树( A )。

A．只有一棵 B．一棵或多棵 C．一定有多棵 D．可能不存在

（9）无向图顶点v的度是关联于该顶点（ B ）的数目。

A．顶点 B．边 C．序号 D．下标

（10）有n个顶点的无向图的邻接矩阵是用（ B ）数组存储。

A．一维B．n行n列C．任意行n列 D．n行任意列

（11）对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为（ C ）。 A．n-1 B．n+1 C．n D．n+e

（12）在图的表示法中，表示形式唯一的是（ A ）。

A．邻接矩阵表示法 B．邻接表表示法

C．逆邻接表表示法 D．邻接表和逆邻接表表示法

（13）在一个具有n个顶点e条边的图中，所有顶点的度数之和等于（ C ）。

A．n B．e C． 2n D．2e

（14）下列图中，度为3的结点是（ B ）。

A ．V 1 B. V 2 C. V 3 D. V 4 （15）下列图是（ A ）。

A ．连通图 B. 强连通图 C. 生成树 D. 无环图

（16）如下图所示，从顶点a 出发，按深度优先进行遍历，则可能得到的一种顶点序列为（ D ）。

A ． a ，b ，e ，c ，d ，f

B ． a ，c ，f ，e ，b ，d C. a ，e ，b ，c ，f ，d D. a ，e ，d ，f ，c ，b

（17）如下图所示，从顶点a 出发，按广度优先进行遍历，则可能得到的一种顶点序列为（ A ）。

A. a ，b ，e ，c ，d ，f

B. a ，b ，e ，c ，f ，d

C. a ，e ，b ，c ，f ，d

D. a ，e ，d ，f ，c ，b

（18）最小生成树的构造可使用（ A ）算法。 A ．prim 算法

B ．卡尔算法

C ．哈夫曼算法

D ．迪杰斯特拉算法

（19）下面关于图的存储结构的叙述中正确的是（ A ）。

A ．用邻接矩阵存储图，占用空间大小只与图中顶点数有关，而与边数无关

B ．用邻接矩阵存储图，占用空间大小只与图中边数有关，而与顶点数无关

C ．用邻接表存储图，占用空间大小只与图中顶点数有关，而与边数无关

D ．用邻接表存储图，占用空间大小只与图中边数有关，而与顶点数无关（20）连通分量是（ C ）的极大连通子图。 A ．树

B ．图

C ．无向图

D ．有向图

四．应用题（30分）

1．有向图如下图所示，画出邻接矩阵和邻接表

解：

（1）邻接矩阵

1 2 3 4 5

???

??010000000110000010001011054321

2．已知一个无向图有6个结点，9条边，这9条边依次为（0，1）,（0，2）,（0，4）,（0，5），（1，2），（2，3），（2，4），（3，4），（4，5）。试画出该无向图，并从顶点0出发，分别写出按深度优先搜索和按广度优先搜索进行遍历的结点序列。（5分）解：

从顶点0出发的深度优先搜索遍历的结点序列：0 1 2 3 4 5（答案不唯一）从顶点0出发的广度优先搜索遍历的结点序列：0 1 2 4 5 3（答案不唯一）

3．已知一个无向图的顶点集为：{a ，b ，c ，d ，e}，其邻接矩阵如下，画出草图，写出顶点a 出

①

②③

④⑤

发按深度优先搜索进行遍历的结点序列。（5分）

解：

（1）

（2）深度优先搜索：

a b d c e （答案不唯一）

广度优先搜索：

a b e d c （答案不唯一）

4．网G 的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。

解：

5. 已知某图G 的邻接矩阵如图，

（1）画出相应的图；

（2）要使此图为完全图需要增加几条边。

解：（1）

（2）完全无向图应具有的边数为：n*(n-1)1/2=4*(4-1)/2=6，所以还要增加2条边（如右图）。

???

????

????????0110110110110000100110010?

??????0101101001011010???

??????????

???0701307040

110403101303080111080

6．已知如图所示的有向图，请给出该图的:

（1）每个顶点的入/出度；（2）邻接表；（3）邻接矩阵。

解：

（1）（2）

（3）

7．如图，请完成以下操作：

（2）写出无向带权图的邻接矩阵；（3）设起点为a ，求其最小生成树。

解：

（1）邻接矩阵为：（2）起点为a ，可以直接由原

始图画出最小生成树

????????

??????????∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞064560252036307945670555505395504340

8．给定下列网G:

（1）画出网G 的邻接矩阵；

（2）画出网G 的最小生成树。解：

（1）邻接矩阵（2）最小生成树

??????????

????????????∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞1012696841015121520982012412

五．程序题填空题

图G 为有向无权图，试在邻接矩阵存储结构上实现删除一条边(v,w)的操作：DeleteArc(G,v,w)。若无顶点v 或w ，返回“ERROR ”；若成功删除，则边数减1，并返回“OK ”。（提示：删除一条边的操作，可以将邻接矩阵的第i 行全部置0 ）解：

Status DeleteArc(MGraph &G,char v,char w) //在邻接矩阵表示的图G 上删除边(v,w) { if ((i=LocateVex(G,v))<0) return ERROR ; if ((j=LocateVex(G,w))<0) return ERROR ; if (G.arcs[i][j].adj) { G.arcs[i][j].adj= 0 ;

G.arcnum -- ; （或 G.arcnum=G.arcnum-1 ） }

return OK ; }

六．算法题

1．编写一个无向图的邻接矩阵转换成邻接表的算法。

2．以知有n 个顶点的有向图邻接表，设计算法分别实现以下功能：（1）求出图G 中每个顶点的出度、入度。

（2）求出G 中出度最大的一个顶点，输出其顶点序号。

（3）计算图中度为0的顶点数。

1．解：本题思想是逐个扫描邻接矩阵的各个元素，若第i行第j列的元素为1，则相应的邻接表的第i个单链表上增加一个j结点。

void trans(int edges[n][n],Adjlist adj)

{ int i,j;

edgenode *p;

for (i=0;i

{ adj[i].data=i;

adj[i].link=NULL;

}

for (i=0;i

for (j=0;j

{ if(edges[i][j]==1)

{ p=(edgenode *) malloc (sizeof(edgenode));

p->adjvex=j;

p->next=adj[i].link;

adj[i].link=p;

}

2．

（1）求出度的思想：计算出邻接表中第i个单链表的结点数即可。

int outdegree(adjlist adj,int v)

{ int degree=0;

edgenode *p;

p=adj[v].link;

while (p!=NULL)

{ degree++;

p=p->next;

}

return degree;

}

void printout(adjlist adj,int n)

{ int i,degree;

printf("The Outdegree are:\n");

for(i=0;i

{ degree=outdegree(adj,i);

printf("(%d,%d)",i,degree);

}

求入度的思想：计算出邻接表中结点i的结点数即可。

int indegree(adjlist adj,int n,int v)

{ int i,j,degree=0;

edgenode *p;

for (i=0;i

{ p=adj[i].link;

while (p!=NULL)

{ if (p->adjvex==v)

degree++;

p=p->next;

}

return degree;

}

void printin(adjlist adj,int n)

{ int i,degree;

printf("The Indegree are:\n");

for (i=0;i

{ degree=Indegree(adj,n,i);

printf("(%d,%d)",i,degree);

}

（2）求最大度的算法

void maxoutdegree(adjlist adj,int n)

{ int maxdegree=0,maxv=0,degree,i;

for (i=0;i

{ degree=outdegree(adj,i);

if (degree>maxdegree)

{ maxdegree=degree;

maxv=i;

}

printf("maxoutdegree %d,maxvertex=%d",maxdegree,maxv);

}

（3）求度为0的顶点数的算法

int outzero(adjlist adj,int n)

{ int num=0,i;

for (i=0;i

{ if (outdegree(adj,i)==0)

num++;

}

return num;

}

模拟考题

1．已知如图所示的有向图，请给出该图的:

（1）每个顶点的入度和出度；（2）逆邻接表。

解：

（1）（2）

2．给定下列网G:

（1）写出网G 以B 为顶点的广度优先遍历的序列；（2）画出网G 的最小生成树。解：（1）以B 为顶点的广度优先遍历的序列：（2）最小生成树 B A E F C G D

3．无向图G 如图所示，（1）试画出邻接矩阵；（2）写出从A 出发的深度优先遍历的序列。

解：（1）邻接矩阵（2）从A 出发的深度优先遍历的序列： A B D C E G F （不唯一）

3．已知图G 的邻接表如下，以顶点1为出发点，完成下列问题：

（1）写出以顶点1为出发点的广度优先遍历序列；

（2）画出以顶点1为出发点的深度优先搜索得到的一棵二叉树。解：（1）广度优先遍历序列：1，2，5，4，3 （2）深度优先搜索得到的一棵二叉树：

5．试填空完成深度优先搜索的递归函数。

#define MAXVEX 100 // 定义图的最大顶点数 struct vertex

{ int num; // 顶点编号 char data; // 顶点的信息 };

typedef struct graph

{ struct vertex vexs[MAXVEX]; // 顶点集合 int edges[MAXVEX][ MAXVEX]; // 边的集合 }sdjmax;

int visited[MAXVEX];

???

????????????0110000100100010010000110110000100100010010000110

void dfs(adjlist adj,int v) // 深度优先搜索的递归函数

{ int i;

struct edgenode *p;

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

visited[i]=0; // 给visited数组赋初值0

visited[v]=1;

cin v; // 取v的边的表头指针

p= adj[v]->link ;

while ( p!=NULL )

{ if (visited[p->adjvex]== 0 ) // 从v的未访问过的邻接点出发进行深度优先搜索 dfs(adjlist, p->adjvex );

p= p->next ; // 找v的下一个邻接点

}

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

一、实验目的 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)

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

图遍历操作

图的遍历操作实验日志实验题目：图的遍历操作实验目的：掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS 及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。实验要求：采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。实验主要步骤： 1分析、理解程序 2 编译和调试程序，以邻接矩阵作为存储结构 3输入顶点数，和边数，建立无向图G1 ４输入顶点数，边数，建立有向图Ｇ２ Print Graph DFS: 01374256 Print Graph BFS: 31704256 6 有向图G2遍历结果： Print Graph DFS: 01374256 Print Graph BFS: 37401256 实验结果：无向图G1的遍历结果：

有向图Ｇ２的遍历结果：心得体会：本次实验中对于图的存储问题可以使用两种不同的方法，有邻接矩阵存储和邻接表存储。这两种方法各有优缺点，可以根据程序的具体要求选择者两种方法的其中一种。在对无向图和有向图进行深度优先遍历和广度优先遍历的时候，深刻的理解了程序的实现过程，，对G1图，G2图进行不同遍历方法，它们的深度优先遍历相同，但是广度优先遍历有所不同，那是因为有向图是单向指向的，二个顶点间一般不会相互到达。

实验程序： #include"stdio.h" #include"stdlib.h" #define MaxVertexNum 100 //定义最大顶点数 typedef struct{ char vexs[MaxVertexNum]; //顶点表 int edges[MaxV ertexNum][MaxVertexNum]; //邻接矩阵，可看作边表 int n,e; //图中的顶点数n和边数e }MGraph; //用邻接矩阵表示的图的类型 //=========建立邻接矩阵======= void CreatMGraph(MGraph *G) { int i,j,k; char a; printf("Input VertexNum(n) and EdgesNum(e): "); scanf("%d,%d",&G->n,&G->e); //输入顶点数和边数 scanf("%c",&a); printf("Input Vertex string:"); for(i=0;in;i++) { scanf("%c",&a); G->vexs[i]=a; //读入顶点信息，建立顶点表 } for(i=0;in;i++) for(j=0;jn;j++) G->edges[i][j]=0; //初始化邻接矩阵 printf("Input edges,Creat Adjacency Matrix\n"); for(k=0;ke;k++) { //读入e条边，建立邻接矩阵 scanf("%d%d",&i,&j); //输入边（Vi，Vj）的顶点序号 G->edges[i][j]=1; G->edges[j][i]=1; //若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句} } //=========定义标志向量，为全局变量======= typedef enum{FALSE,TRUE} Boolean; Boolean visited[MaxVertexNum]; //========DFS：深度优先遍历的递归算法====== void DFSM(MGraph *G,int i) { //以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵int j; printf("%c",G->vexs[i]); //访问顶点Vi visited[i]=TRUE; //置已访问标志 for(j=0;jn;j++) //依次搜索Vi的邻接点 if(G->edges[i][j]==1 && ! visited[j])

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

数据结构实验报告实验：图的遍历一、实验目的： 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;

图的深度优先遍历算法课程设计报告

合肥学院计算机科学与技术系课程设计报告 2013～2014学年第二学期课程数据结构与算法课程设计名称图的深度优先遍历算法的实现学生姓名陈琳学号1204091022 专业班级软件工程指导教师何立新 2014 年9 月一：问题分析和任务定义涉及到数据结构遍会涉及到对应存储方法的遍历问题。本次程序采用邻接表的存储方法，并且以深度优先实现遍历的过程得到其遍历序列。

深度优先遍历图的方法是，从图中某顶点v 出发：（1）访问顶点v ；（2）依次从v 的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v 有路径相通的顶点都被访问；（3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。二：数据结构的选择和概要设计设计流程如图：图1 设计流程利用一维数组创建邻接表，同时还需要一个一维数组来存储顶点信息。之后利用创建的邻接表来创建图，最后用深度优先的方法来实现遍历。图 2 原始图 1.从0开始，首先找到0的关联顶点3 2.由3出发，找到1；由1出发，没有关联的顶点。 3.回到3，从3出发，找到2；由2出发，没有关联的顶点。 4.回到4，出4出发，找到1，因为1已经被访问过了，所以不访问。

所以最后顺序是0,3,1,2,4 三：详细设计和编码 1.创建邻接表和图 void CreateALGraph (ALGraph* G) //建立邻接表函数. { int i,j,k,s; char y; EdgeNode* p; //工作指针. printf("请输入图的顶点数n与边数e(以逗号做分隔符)：\n"); scanf("%d,%d",&(G->n),&(G->e)); scanf("%c",&y); //用y来接收回车符. for(s=0;sn;s++) { printf("请输入下标为%d的顶点的元素:\n",s); scanf("%c",&(G->adjlist[s].vertex)); scanf("%c",&y); //用y来接收回车符.当后面要输入的是和单个字符有关的数据时候要存贮回车符，以免回车符被误接收。 G->adjlist[s].firstedge=NULL; } printf("请分别输入该图的%d条弧\n",G->e); for(k=0;ke;k++) { printf("请输入第%d条弧的起点和终点（起点下标,终点下标）:\n",(k+1)); scanf("%d,%d",&i,&j); p=(EdgeNode*)malloc(sizeof(EdgeNode)); p->adjvex=j; p->next=G->adjlist[i].firstedge; G->adjlist[i].firstedge=p; } } 2.深度优先遍历 void DFS(ALGraph* G,int v) //深度优先遍历 { EdgeNode* p;

图的遍历实验报告

实验四：图的遍历题目：图及其应用——图的遍历班级：姓名：学号：完成日期：一.需求分析 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 #include #define n 4 //图的顶点数 #define e 5 //图的边数 typedef struct node { int adjvex; struct node *next; } edgenode;//边表节点 typedef struct { char vertex; edgenode *link; }vexnode;//顶点表节点 vexnode ga[n]; int visited[n]; void Creatadjlist(vexnode ga[])//建立无向图的邻接表{ int i,j,k; edgenode *s; printf("请输入各个顶点："); for(i=0;iadjvex=j; s->next=ga[i].link; ga[i].link=s; s=malloc(sizeof(edgenode)); s->adjvex=i; s->next=ga[j].link; ga[j].link=s; } } void Dfsl(int i)//邻接表的深度遍历 {

edgenode *p; printf("node:%c\n",ga[i].vertex); visited[i]=1; p=ga[i].link; while(p!=NULL) { if(!visited[p->adjvex]) { Dfsl(p->adjvex); } p=p->next; } } void main() { int i; Creatadjlist( ga); printf("请输入需要遍历的顶点：\n"); scanf("%d",&i); Dfsl(i); }

数据结构图的遍历

#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);}

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

##大学数据结构课程设计报告题目：图的遍历和生成树求解院（系）：计算机工程学院学生: 班级：学号: 起迄日期: 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