当前位置：文档库 › 数据结构图演示(2)

数据结构图演示(2)

第七章图

7.4 有向无环图及应用

一AOV网、AOE网

二AOV网与拓扑排序

三AOE网与关键路径

一AOV 网、AOE 网

有向无环图：没有回路的有向图

许多应用问题可用有向无环图来表示和求解。例如：各种流程：工程流程、生产过程中各道工序的流程、程序流程、课程的流程

常用的两种有向图是：AOV 网，AOE 网

1 AOV 网( activity on vertex net )

用顶点表示活动，边表示活动的顺序关系的有向图称为AOV 网

例1 某工程可分为V0、V1、V2、V3、V4、V5、V6 7个子工程，工程流程可用如下AOV 网表示。其中顶点：表示子工程（也称活动），孤：表示子工程间的顺序关系。V0V3V2

2 AOE 网( activity on edge net )

用边表示活动，顶点表示事件的有向图称为AOE 网。事件发生表示以该事件为起点的活动可以开始，以该事件为终点的活动已经结束。

例1中的工程流程用AOE 网表示，如下图所示。其中a 0 a 1 a 2 a 3 a 4

a 5 a 6分别表示例1中的7个子工程V0、V1、V2、V3、V4、V5、V6。a 7 a 8

是为能正确的表示子工程的流程人为添加的两个工期为0（天）的子工程

。按AOE 网表示的子工程的流程，

a 0结束，a 2可以开始，a 0 a 1

结束，a 3 a 4

可以开始…，与用AOV 网所表示的流程是一样的。

V 6

V 5

V 1V 4

V 3

V 2V 7V 8a 0

a 2a 5

a 1

a 4

a 3

a 6a 7

a 8

V0V3V6

V5V4

AOV 网AOE 网

二AOV 网与拓扑排序

对工程问题，人们至少关心如下两类问题：

1）工程能否顺序进行，即工程流程是否“合理”

2）完成整项工程至少需要多少时间，哪些子工程是影响工程进度的关键子工程？

为求解工程流程是否“合理”，通常用AOV 网的有向图表示工程流程

例1 某工程可分为V0、V1、V2、V3、V4、V5、V6 7个子工程，工程流程可用如下AOV 网表示。其中顶点：表示子工程（也称活动），孤：表示子工程间的顺序关系。

V0V3V6

V5V4

例2 课程流程图

某校计算机专业课程流程可AOV网表示。其中顶点：表示课程（也称活动），孤：表示课程间的先修关系；（见课本p181 图7.27)

1拓扑排序

问题：

若某工程只有一个施工队，一次只能干一件子工程，工程负责人应如何安排施工计划？

若某在职学生一学期只能修一门课，他怎样为自己安排学习计划？

如何安排施工计划？

如何安排学习计划？

7.4 有向无环图的应用

一个可行的施工计划为：V0,V1,V2, V4,V3,V5,V6,

一个可行的学习计划为：C1,C9,C4,C2,C10,C11,C12,C3,C6,C5,C7,C8可行的计划的特点：若在流程图中顶点v 是顶点u 的前趋，则在计划序列中顶点v 也是u 的前趋。

V4V1

拓扑排序

顶点活动的网：用顶点表示活动，用弧表示活动优先关系的有向图。在网中，如果从顶点i到顶点j有一条有向路径，则称i是j的前趋，j是i的后继。若是网中的一条弧，则i是j的直接前趋，j是i的直接后继。

在AOV-网中，不应存在环，因为某项活动不应以它自己为先决条件，因此对于给定的AOV-网，应先判断它是否存在环，检测的办法是对有向图构造其顶点的拓扑有序序列。

拓扑有序序列：假设AOV-网G中的顶点所构成的有序序列T= ( 1,… i，…，n)满足以下条件：

1、AOV-网的优先关系与序列所反映的先后关系一致；

2、AOV-网中无优先关系的顶点也赋予了一定的先后关系。

7.4 有向无环图的应用

拓扑序列：有向图D的一个顶点序列称作一个拓扑序列，如果该序列中任两顶点v 、u ，若在D中v是u前趋，则在序列中v也是u前趋。

拓扑排序：就是将有向图中顶点排成拓扑序列。

拓扑排序的应用

例1 安排施工计划（如上）

例2 判断工程流程的是否合理

工程流程是否合理？至少要看表示工程流程AOV网是否存在“死循环”，用图论的术语就是AOV网（有向图）是否存在有向回路。若存在有向回路，显然工程流程不合理。

如何判断AOV网（有向图）是否存在有向回路？

有这样的结论：AOV网（有向图）不存在有向回路当且仅当能对AOV网进行拓扑排序。

何谓“拓扑排序”？

对有向图进行如下操作:

按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。

例如：对于下列有向图

可求得拓扑有序序列：

A B C D 或 A C B D

由此所得顶点的线性序列称之为拓扑有序序列

反之，对于下列有向图

不能求得它的拓扑有序序列。因为图中存在一个回路{B, C, D}

如何进行拓扑排序？

一、从有向图中选取一个没有前驱

的顶点，并输出之;

二、从有向图中删去此顶点以及所

有以它为尾的弧;

重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。

7.4 有向无环图的应用

2 拓扑排序方法：

1）在有向图选一无前趋的顶点v ，输出；2）从有向图中删除v 及以v 为尾的孤；

3）重复1、2、直接全部输出全部顶点或有向图中不存在无前趋顶点；例：V0,V1,V2,V3,V4,V5,V6

V0V3V6

V5V4

如何计算机上实现

对有向图的拓扑排序？

a b c

a b h c d g f e

在算法中需要用定量的描述替代定性的概念没有前驱的顶点≡≡入度为零的顶点

删除顶点及以它为尾的弧≡≡弧头顶点的入度减1

3 拓扑排序算法

1）为实现有向图的拓扑排序，我们给出拓扑排序方法的另一种描述：拓扑排序方法（的等价描述）

（1）选择一入度为0顶点v，输出；

（2）将v邻接到的顶点的入度减1；

（3）重复1、2 直到输出全部顶点或有向图没有入度为0的顶点；2）拓扑排序过程中涉及的数据和操作：

数据：有向图，顶点的入度；

操作：（1）选择一入度为0顶点v，输出；

（2）将v邻接到的顶点u 的入度减1；

3）为算法的有关数据选择设计存储结构(1)ALGraph G 邻接表：存储有向图

V1V4V7

V6V5

D.vertices D.vexnum D.arcnu D.kind

V1V2V3V4V5V6V7n e

5633455

V0V3V6

V5V4V10123456indegree 0012232S.base 6

5432101

S.top (2) Int indegree[ ] 整型数组：存储顶点的入度：

(3) Int S[ ] 整数栈：用于存储入度为0的顶点的编号（也是顶点在邻接表顶点数组中的位置）

存储顶点的入度的

数组

存储入度为0的顶

点的栈

初始时，只有v0,v1

两顶点的入度为0

4）拓扑排序算法

Status TopologicalSort(ALGraph G) {//有向图G 采用邻接表存储结构。

//若G 无回路，则输出G 的顶点的一个拓扑序列并返回OK ，否则ERROR 。FindInDegree(G, indegree); //求各顶点入度indegree[0..vernum-1]InitStack(S);

For(i=0; i

if (! Indegree[i]) Push(S, i); //入度为0顶点的编号进栈

0123456indegree 0

012232S.base 6

101

S.top V1V4V7

V3V6V5V2

count=0; //对输出顶点计数

while(! StackEmpty(S)){

Pop(S, i); //从零入度顶点栈S 栈顶，获得一入度为零的顶点i

printf(i, G. vertices[i].date); ++count; //输出i号顶点的数据，并计数

for (p=G. vertices[i]. firstarc; p; p=p->nextarc) {

k=p->adjvex;

if (!(--indegree[k])) Push(S, k); //对i号顶点邻接到的

//每个顶点入度减1，若入度减为0，则入栈

}//for

}//while

if (count

else return OK;

}//TopologicalSort

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

数学与计算机学院课程设计说明书课程名称: 数据结构与算法课程设计课程代码: 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、理解并掌握图的逻辑结构和物理结构——邻接矩阵、邻接表 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．设完全无向图的顶点个数为n，则该图有( )条边。 A. n-l B. n(n-l)/2 C.n(n+l)/2 D. n(n-l) 2．在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。 A.3 B.2 C.1 D.1/2 3．有向图的一个顶点的度为该顶点的( )。 A.入度 B. 出度 C.入度与出度之和 D.(入度+出度)/2 4．在无向图G (V，E)中，如果图中任意两个顶点vi、vj (vi、vj∈V，vi≠vj)都的，则称该图是( )。 A.强连通图 B.连通图 C.非连通图 D.非强连通图 5．若采用邻接矩阵存储具有n个顶点的一个无向图，则该邻接矩阵是一个( )。 A.上三角矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵 6．若采用邻接矩阵存储具有n个顶点的一个有向图，顶点vi的出度等于邻接矩阵 A.第i列元素之和 B.第i行元素之和减去第i列元素之和 C.第i行元素之和 D.第i行元素之和加上第i列元素之和 7．对于具有e条边的无向图，它的邻接表中有( )个边结点。 A.e-l B.e C.2(e-l) D. 2e 8．对于含有n个顶点和e条边的无向连通图，利用普里姆Prim算法产生最小生成时间复杂性为( )，利用克鲁斯卡尔Kruskal算法产生最小生成树（假设边已经按权的次序排序），其时间复杂性为( )。 A. O(n2) B. O(n*e) C. O(n*logn) D.O(e) 9．对于一个具有n个顶点和e条边的有向图，拓扑排序总的时间花费为O( ) A.n B.n+l C.n-l D.n+e 10．在一个带权连通图G中，权值最小的边一定包含在G的( )生成树中。 A.最小 B.任何 C.广度优先 D.深度优先二、填空题 1．在一个具有n个顶点的无向完全图中，包含有____条边；在一个具有n个有向完全图中，包含有____条边。 2．对于无向图，顶点vi的度等于其邻接矩阵____ 的元素之和。 3．对于一个具有n个顶点和e条边的无向图，在其邻接表中，含有____个边对于一个具有n个顶点和e条边的有向图，在其邻接表中，含有_______个弧结点。 4．十字链表是有向图的另一种链式存储结构，实际上是将_______和_______结合起来的一种链表。 5．在构造最小生成树时，克鲁斯卡尔算法是一种按_______的次序选择合适的边来构造最小生成树的方法；普里姆算法是按逐个将_______的方式来构造最小生成树的另一种方法。 6．对用邻接表表示的图进行深度优先遍历时，其时间复杂度为一；对用邻接表表示的图进行广度优先遍历时，其时间复杂度为_______。 7．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数为_______ ，边数为_______。 8．在执行拓扑排序的过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1。为了避免重复检测顶点的入度是否为零，需要设立一个____来存放入度为零的顶点。

数据结构--图重点

一、定义与术语图：无序数据结构基本构成：1.边集（Edge ）：a. 有向图，有向边，弧，弧头，弧尾，权值 b. 无向图，无向边(v, w)，权值 2.顶点集（Vertices ）：a. 无向图：度(TD(v)) b. 有向图：出度(ID(v))，入度(OD(v))，度(TD(v) = ID(v) + OD(v)) 无向完全图：n 个顶点，(1)2 n n -条边有向完全图：n 个顶点，(1)n n -条边网：带权图连通分量：无向图中的极大连通子图（多个），无向完全图的连通分量就是本身（一个）强连通分量：有向图中的极大连通子图，其中i v 到j v 以及j v 到i v 都有路径生成树：图的极小连通子图，含有图的全部n 个顶点，只有n-1条边，少一条则不能连通，多一条则形成回路生成森林：不完全图中的各个连通分量的生成树，构成图的生成森林二、存储结构顶点：可采用链表或数组存储顶点列表，一般采用链表存储边：1. 邻接矩阵（数组） a. 无向图：对称阵，可采用矩阵压缩存储方式。A[i][j] = 0表示i v 和j v 没有连接； A[i][j] = 1表示i v 和j v 有边连接；第i 行的和表示顶点i v 的度 b. 有向图：不对称阵。,[][]i j A i j w =表示顶点i v 到j v 的有向弧的权值；[][]A i j =∞ 表示表示顶点i v 到j v 没有弧连接或者i = j 2. 邻接表（链表，有向无向都可用）边结点：adjvex （邻接点），nextarc （下一条边），info （权值）顶点结点：data （顶点数据），firstarc （第一条边） 3. 十字链表（Othogonal List ）弧结点：tailvex （弧尾结点），headvex （弧头结点），tlink （弧尾相同的下一条弧），hlink （弧头相同的下一条弧），info （权值）顶点结点：data （顶点数据），firstin （第一条入弧），firstout （第一条出弧）三、图的遍历（每个顶点只被访问一次） 1. 深度优先遍历（类似树的先根遍历）基本思想：假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点v 出发，访问此结点，然后依次从v 的未被访问的邻接点出发深度优先遍历图，直至图中所有和v 有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问（非连通图），则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

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

学号：姓名：实验日期： 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;

数据结构：图子系统

/* *题目：编写按键盘输入的数据建立图的邻接矩阵存储 * 编写图的深度优先遍历程序 * 编写图的广度优先遍历程序 * 设计一个选择式菜单形式如下： * 图子系统 * *********************************** * * 1------更新邻接矩阵* * * 2------深度优先遍历* * * 3------广度优先遍历* * * 0------ 返回* * *********************************** * 请选择菜单号（0--3）： */ #include #include #define GRAPHMAX 30 #define QUEUEMAX 30 typedef struct //图的邻接表的结构体 { char value[GRAPHMAX]; //记录图中的点值 int data[GRAPHMAX][GRAPHMAX]; //记录图中的边的关系int n, e; //记录图中的点的个数及边的个数 }pGraph; typedef struct //队列结构体 { int queueData[QUEUEMAX]; int front, rear, count; //队头，队尾，数目 }grQueue; void createCraph(pGraph *G); void DFSTraverse(pGraph *G); void BFSTraverse(pGraph *G); void DFS(pGraph *G, int i); void BFS(pGraph *G, int i); void initQueue(grQueue *Q); int queueEmpty(grQueue *Q); int queueFull(grQueue *Q); int outQueue(grQueue *Q); void inQueue(grQueue *Q, int i);

数据结构-图习题

第8章图 8-1 画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n 个顶点的无向完全图中，边的条数为n(n-1)/2。【解答】【证明】在有n 个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有 n-1条边与其他n-1个顶点相连，总计n 个顶点有n(n-1)条边。但在无向图中，顶点i 到顶点j 与顶点j 到顶点i 是同一条边，所以总共有n(n-1)/2条边。 8-2 右边的有向图是强连通的吗？请列出所有的简单路径。【解答】点，它不是强连通的有向图。各个顶点自成强连通分量。所谓简单路径是指该路径上没有重复的顶点。从顶点A 出发，到其他的各个顶点的简单路径有A →B ，A →D →B ，A →B →C ，A →D →B →C ，A →D ，A →B →E ，A →D →E ，A →D →B →E ，A →B →C →F →E ，A →D →B →C →F →E ，A →B →C →F ，A 1个顶点的无向完全图 2个顶点的无向完全图 3个顶点的无向完全图 4个顶点的无向完全图 5个顶点的无向完全图 A D

????????? ?????? ?????=01 00000001001010000 010*********Edge →D →B →C →F 。从顶点B 出发，到其他各个顶点的简单路径有B →C ，B →C →F ，B →E ，B →C →F →E 。从顶点C 出发，到其他各个顶点的简单路径有C →F ，C →F →E 。从顶点D 出发，到其他各个顶点的简单路径有D →B ，D →B →C ，D →B →C →F ，D →E ，D →B →E ，D →B →C →F →E 。从顶点E 出发，到其他各个顶点的简单路径无。从顶点F 出发，到其他各个顶点的简单路径有F →E 。 8-3 给出右图的邻接矩阵、邻接表和邻接多重表表示。【解答】 (1) 邻接矩阵 A D

数据结构图的遍历

#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