数据结构 用邻接表来简化图的计算 课程设计
数 据 结 构 课 程 设 计
设计
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
目: 用邻接表来简化图的计算
课题名称 用邻接表来简化图的计算
院 系 年级专业
学 号 姓 名 成 绩
1、课题设计目的:
1熟练掌握图的概念和性质和图的存储
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
;2连接邻接表的建立步
骤和代码的书写;3两种对图的遍历的具体操作4理解邻接表对图的
操作的意义。
2、课题设计意义:通过课程设计的方式,可以使我们更加全面的理 课题设计
解邻接表的建立和两种不同方法的遍历的优缺点,使我们更加全面 目的与
深刻的理解图的概念和有向无向图表的应用及其代码的书写和这其 设计意义
中要注意的问题,培养我们更加全面的思考问题。
指导教师:
年 月 日
目 录
第一章图的概念和邻接表的表示方法........................................................................ 2
1.1图的概念......................................................................................................... 2
1.2邻接表表示法.................................................................................................. 2 第二章邻接表在图中的应用........................................................................................ 3
2.1连接表的建立.................................................................................................. 3
2.2.1连通图的深度优先搜素遍历............................................................... 4
............................... 5 2.2.2连通图的广度优先搜索遍历................................
2.3对上述操作进行的代码书写及运行结果...................................................... 6
2.3.1上述的全部代码................................................................................... 6
2.3.2运行结果............................................................................................. 14 第三章 总结................................................................................................................ 17
................................................................................ 17 3.1后语................................
3.2参考文献:.................................................................................................... 17
简 介
图(Graph)是一种较线性表和树更为复杂的数据结构。在线性表中,数据元素之间仅有线性关系,即每个数据元素只有一个直接前驱和一个直接后继;在树形结构中,数据元素之间有着明显的层次关系,虽然每一层上的数据元素可能和下一层中多个元素(孩子) 相关,但只能和上一层中一个元素(双亲)相关;而在图形结构中,结点之间的关系可以是任意的,任意两个数据元素之间都关。 图在各个领域都有着广泛的应用,如电路网络分析、交通运输、管理与线路的铺设、印刷电路板与集成电路的布线等众多直接与图有关的问题,它们必须用图的有关方法进行处理;另外像工作的分配、工程进度的安排、课程表的制订、关系数据库的设计等许多实际问题,如果间接地用图来表示,处理起来比较方便。这些技术领域都是把图作为解决问题的主要
数学
数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划
手段来使用,因此,如何在计算机中表示和处理图结构,就是计算机科学需研究的一项重要课题。本章主要讨论图
的逻辑表示、在计算机中的存储方法及一些有关图的算法和应用。 学习重点
1、理解图的基本概念,熟悉图的各种存储结构及其构造算法
2、熟练掌握图的两种搜索路径的遍历;
、掌握构造最小生成树的方法,并理解算法; 3
4、理解用Dijkstra方法求解单源最短路径问题;
5、掌握求活动网络的拓扑排序的方法,并理解算法;
6、掌握求解关键路径的方法。
图的二元组定义
图G由两个集合V和E组成,记为:
G=(V,E)
其中:
V是顶点的有穷非空集合,
E是V中顶点偶对(称为边)的有穷集。
通常,也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集。若E(G)为空,则图G只有顶点而没有边。
1
第一章图的概念和邻接表的表示方法 1.1图的概念.
图G是由两个集合和E组成,记为G=(V,E),其中V是顶点的有穷非
空集合,E是V中顶点偶对(对称边)的有穷集。通常,也将图G的顶点集
和边集分别记为V(G)和E(G)。E(G)可以使空集,若,(,)为空,则图,
只有顶点而没有边。
若图,中的每一条边都有方向的,则称,为有向图。有向边也称为弧,
边的始点称为弧尾,终点称为弧头。
若图,中的每一条边都是没有方向的,则称,为无向图。
若图,的顶点数,和边数,满足:若,为无向图,恰好有,(,,,)
,,条边的无向图则称为无向完全图,恰好有,(,,,)条边的有向图称
为有向完全图。
无向图中顶点,的度是关联于该点的边的数目,记为,(,)(若,为
有向图,则把以顶点,为终点的边的数目,称为,的入度,记为,,(,);
把以顶点,为始点的边的数目,称为,的出度,记为,,(,)。
若将图的每一条都赋上一个权,则称这种带权图为网络。 连通图和连通分量
1(顶点间的连通性
在无向图G中,若从顶点v到顶点v有路径(当然从v到v也一定有路径),ijji则称v和v是连通的。 ij
2(连通图
若V(G)中任意两个不同的顶点v和v都连通(即有路径),则称G为连通ij
图。
3(连通分量
无向图G的极大连通子图称为G的连通分量。
强连通图和强连通分量
1(强连通图
有向图G中,若对于V(G)中任意两个不同的顶点v和v,都存在从v到vijij以及从v到v的路径,则称G是强连通图。 ji
2(强连通分量
有向图的极大强连通子图称为G的强连通分量。
注意:
? 强连通图只有一个强连通分量,即是其自身。
? 非强连通的有向图有多个强连分量。
1.2邻接表表示法
这种表示法类似树的孩子链表表示法。
对于图,中每一个顶点,,,该方法把 所有邻接与,,的顶点,,链成一个单链表,这个单链表就称为顶点,,的邻接表。
2
邻接表中每个表节点均有两个域,其一是邻接点域,用以存放与,,相邻的顶点,,的序号,;其二是链域,用来将邻接表的所有表结点链在一起。并且为每个顶点,,的邻接表设置一个具有两个域的表头结点:一个是顶点域,用来存放顶点,,的信息;另一个是指针域,用于存放指向,,的连接表中的第一个表结点的头指针。
邻接表的结点结构:
(1)表结点结构
adjvex next
邻接表中每个表结点均有两个域:
? 邻接点域adjvex
存放与vi相邻接的顶点vj的序号j。
? 链域next
将邻接表的所有表结点链在一起。
注意:
若要表示边上的信息(如权值),则在表结点中还应增加一个数据域。
第二章邻接表在图中的应用
2.1连接表的建立
对于无向图而言,Vi的邻接表中的每一个表结点都对应与于Vi相关联的一条边;对于有向图来说,Vi的连接表中的每一个表结点都对应与以Vi为始点射出的一条边。因此,我们将无向图的连接表称链表,将有向图的邻接表称为出边表,将邻接表的表头向量称为顶点表。
邻接表的结点结构:
(2)头结点结
vertex firstedge
顶点vi邻接表的头结点包含两个域:
? 顶点域vertex
存放顶点vi的信息
? 指针域firstedge
vi的邻接表的头指针。
注意:
? 为了便于随机访问任一顶点的邻接表,将所有头结点顺序存储在一个向量中就构成了图的邻接表表示。
? 有时希望增加对图的顶点数及边数等属性的描述,可将邻接表和这些属
3
性放在一起来描述图的存储结构。
2(无向图的邻接表
对于无向图,vi的邻接表中每个表结点都对应于与vi相关联的一条边。因此,将邻接表的表头向量称为顶点表。将无向图的邻接表称为边表。 【例】对于无向图G5,其邻接表表示如下面所示,其中顶点v0的边表上三个表结点中的顶点序号分别为1、2和3,它们分别表示关联于v0的三条边(v0,v1),(v0,v2)和(v0,v3)。
注意:
? 为了便于随机访问任一顶点的邻接表,将所有头结点顺序存储在一个向量中就构成了图的邻接表表示。
? 有时希望增加对图的顶点数及边数等属性的描述,可将邻接表和这些属性放在一起来描述图的存储结构。
邻接表的形式说明及其建表算法
(1)邻接表的形式说明
typedef struct node{//边表结点
int adjvex; //邻接点域
struct node *next; //链域
//若要表示边上的权,则应增加一个数据域
}EdgeNode;
typedef struct vnode{ //顶点表结点
VertexType vertex; //顶点域
EdgeNode *firstedge;//边表头指针
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum];//AdjList是邻接表类型 typedef struct{
AdjList adjlist;//邻接表
int n,e; 图中当前顶点数和边数
}ALGraph; //对于简单的应用,无须定义此类型,可直接使用AdjList类型。
2.2用连接表对图的遍历
和树的遍历类似,图的遍历也是从某个顶点出发,沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础.深度优先遍历和
广度优先遍历是最为重要的两种遍历图的方法。它对无向图和有向用。 2.2.1连通图的深度优先搜素遍历
深度优先搜索遍历类似于树的前序遍历。假设给定图G的初态是所有均未曾访问过,在G中任选一顶点Vi为初始出发点,则深度优先搜索可定义如下:
4
首先,访问出发点Vi,并将其标记为已访问,然后,依次从vi出发搜索vi的每一个邻接点Vj,若Vj未被访问过,则以Vj为新的出发点继续进行深度优先搜索。特点为尽可能先对纵深方向进行搜索,故称之为深度优先搜索。 图的深度优先遍历的递归定义
假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未访问的顶点作为新的源点重复上述过程,直至图中所有顶点均已被访问为止。
图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地,用此方法遍历图就很自然地称之为图的深度优先遍历。 深度优先搜索的过程
设x是当前被访问顶点,在对x做过访问标记后,选择一条从x出发的未检测过的边(x,y)。若发现顶点y已访问过,则重新选择另一条从x出发的未检测过的边,否则沿边(x,y)到达未曾访问过的y,对y访问并将其标记为已访问过;然后从y开始搜索,直到搜索完从y出发的所有路径,即访问完所有从y出发可达的顶点之后,才回溯到顶点x,并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时,若x不是源点,则回溯到在x之前被访问过的顶点;否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过,若图G是连通图,则遍历过程结束,否则继续选择一个尚未被访问的顶点作为新源点,进行新的搜索过程。
注意:
遍历操作不会修改图G的内容,故上述算法中可将G定义为ALGraph或MGraph类型的参数,而不一定要定义为ALGraph和MGraph的指针类型。但基于效率上的考虑,选择指针类型的参数为宜。
2.2.2连通图的广度优先搜索遍历
广度优先搜索遍历列斯于树的按层遍历。设图G的初态是所有顶点均未被访问过,在G中任选一顶点Vi为初始出发点,则广度优先搜索的基本思想是:首先访问出发点Vi,接着依次访问Vi的所有邻接点W1,W2,,,,,Wt,然后,再依次访问与W1,W2,,,,wt邻接点的所有未曾访问过的顶点,依此类推,直至图中所有和初始出发点Vi有路径相通的顶点都已经访问到为止。 算法分析
对于具有n个顶点和e条边的无向图或有向图,遍历算法DFSTraverse对图
5
中每顶点至多调用一次DFS或DFSM。从DFSTraverse中调用DFS(或DFSM)
及DFS(或DFSM)内部递归调用自己的总次数为n。 当访问某顶点vi时,DFS(或DFSM)的时间主要耗费在从该顶点出发搜索它的所有邻接点上。用邻接矩阵表示图时,其搜索时间为O(n);用邻接表表示图时,需搜索第i个边表上的所有结点。因此,对所有n个顶点访问,在邻接矩阵上共需检查n2个矩阵元素,在邻接表上需将边表中所有O(e)个结点检查一遍。
所以,DFSTraverse的时间复杂度为O(n2) (调用DFSM)或0(n+e)(调用DFS)。
2.3对上述操作进行的代码书写及运行结果
2.3.1上述的全部代码:
#include
#include
#define m 20
typedef char vextype;
typedef int adjtype;
typedef char rextype;
typedef struct node
{
int adjvex;
struct node *next;
}edgenode;
typedef struct
{
vextype vertex;
edgenode * link;
}vexnode;
vexnode ga[m];
vexnode gl[m];
typedef struct
{
vextype vexs[m];
adjtype arcs[m][m];
}graph;
typedef int datatype;
typedef struct
6
{
datatype data[m];
int fromt, rear; }sequeue;
sequeue *Q;
int n,e;
creat_graph(graph * ga)//无向图的建立// {
int i,j,k;
getchar();
printf("请输入顶点信息\n");
for(i=0;ivexs[i]);
}
for(i=0;iarcs[i][j]=0; for(k=0;karcs[i][j]=1; ga->arcs[j][i]=1;
}
for(i=0;ivexs[i],ga->arcs[i][j]);
printf("\n");
}
void creatadjlist(ga)//无向图的邻接表// vexnode ga[];
{
int i,j,k;
7
edgenode *s;
printf("请输入顶点信息\n");
getchar();
for(i=0;iadjvex=j;
s->next=ga[i].link; ga[i].link=s;
s=(edgenode *)malloc(sizeof(edgenode));
s->adjvex=i;
s->next=ga[j].link; ga[j].link=s;
}
}
int visited[m];
graph g;
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;
8
}
}
void bfsl(k)//广度遍历无向连接表// {
int i;
edgenode *p;
sequeue *Q;
SETNNULL(Q);
printf("%c\n",ga[k].vertex);
visited[k]=1;
ENQUEUE(Q,k);
while(!EMPTY(Q))
{
i=DEQUEUE(Q);
p=ga[i].link;
while(p!=NULL)
{
if(!visited[p->adjvex]) {
printf("%c\n",ga[p->adjvex].vertex);
visited[p->adjvex]=1; ENQUEUE(Q,p->adjvex); }
p=p->next;
}
}
youxiangwang(graph * gl)//有向网的建立和输出// {
int i,j,k;
getchar();
printf("请输入顶点信息:\n");
for(i=0;ivexs[i]); }for(i=0;iarcs[i][j]=0; for(k=0;karcs[i][j]=1;
}
for(i=0;ivexs[i],gl->arcs[i][j]);
printf("\n");
}
}
void youbiao(gl)//有向连接表的建立// vexnode gl[];
{
int i,j,k;
edgenode *s;
printf("请输入顶点信息\n");
getchar();
for(i=0;iadjvex=j;
s->next=gl[i].link;
gl[i].link=s;
}
10
}
void dfsla(int r)//深度遍历连接表// {
edgenode *p;
printf("node:%c\n",gl[r].vertex);
visited[r]=1;
p=gl[r].link;
while(p!=NULL)
{
if(! visited[p->adjvex])
dfsla(p->adjvex);
p=p->next;
}
}
void bfsla(int t)//广度遍历连接表// {
int i;
edgenode *p;
SETNNULL(Q);
printf("%c\n",gl[t].vertex);
visited[t]=1;
ENQUEUE(Q,t);
while(!EMPTY(Q)) {
i=DEQUEUE(Q);
p=gl[i].link;
while(p!=NULL)
{
if(!visited[p->adjvex]); {
printf("%c\n",gl[p->adjvex].vertex);
visited[p->adjvex]=1; ENQUEUE(Q,p->adjvex) }
p=p->next;
}
11
}
}
SETNNULL(sequeue * Q) {
Q->fromt=-1;
Q->rear=-1;
}
EMPTY(sequeue * Q) {
if(Q->fromt==Q->rear
return 1;
else
return 0;
}
datatype DEQUEUE(sequeue * Q)
{
if(EMPTY(Q))
printf("队空\n");
else
>data[(Q->fromt+1)%m]; return Q-
}
ENQUEUE(sequeue * Q,datatype x)
{
if(Q->fromt==(Q->rear+1)%m)
printf("队满~\n");
else
{
Q->data[Q->rear]=x; Q->rear=(Q->rear+1)%m;
}
}
void main()
{
int c,i,k,r,t,w=1,y=1;
graph ga,gl;
12
for(c=1;c<250;c++) {
printf("请输入你想进行的操作代号:\n");
printf("\t\t1为无向图的建立和输出\n");
printf("\t\t2为无相连接表的建立\n");
printf("\t\t3为无向图的深度优先遍历\n");
printf("\t\t4为无向图的广度优先遍历\n");
printf("\t\t5为有向网的建立和输出\n");
printf("\t\t6为有向连接表的建立\n");
printf("\t\t7为深度优先遍历有向连接表\n");
printf("\t\t8为广度优先遍历有向连接表\n");
printf("\t\t9为结束操作\n");
scanf("%d",&c);
switch(c)
{
case 1:
printf("请输入网的定点数和边数\n");
scanf("%d%d",&n,&e);
creat_graph(&ga);break;
case 2:
creatadjlist(&ga);break; case 3:
printf("请输入遍历的初时代码\n");
scanf("%d",&i);
dfsl(i);break;
case 4:
printf("请输入遍历的初时代码\n");
scanf("%d",&k);
bfsl(k);break;
case 5:
printf("请输入网的定点数和边数\n");
scanf("%d%d",&n,&e);
youxiangwang(&gl);break; case 6:
13
youbiao(&ga);break; case 7:
printf("请输入遍历的初时代码\n");
scanf("%d",&r);
dfsla(r);break; case 8:
printf("请输入遍历的初时代码\n");
scanf("%d",&t);
bfsla(t);break; case 9:break;
}
}
}
2.3.2运行结果
1无向图的建立与输出:
图1无向图的建立与输出
14
2为无向邻接表的深度遍历:
图2无向邻接表的深度遍历 3为无向邻接表的广度遍历:
图3无向邻接表的广度遍历
15
4无向图的建立与输出:
图4无向图的建立与输出 5为有向邻接表的深度遍历:
图5有向邻接表的深度遍历
16
6为有向邻接表的广度遍历:
图6有向邻接表的广度遍历
第三章 总结
3.1后语
经过这次对邻接表的课程设计,是我明白了,动手远比说的复杂,对于知识的掌握要更加全面,要求我们更加全面仔细的思考每一个问题,培养了我们独立思考,解决问题的能力使我受益良多。
3.2参考文献:
[1]徐孝凯,贺桂英.数据结构(c语言描述).北京:清华大学出版社.2004 [2]严蔚敏,吴伟民.数据结构(c语言版).北京:清华大学出版社.2007 [3]谭浩强.c语言程序设计教程.北京:高等教育出版社.2007
17