数据结构课程设计本课程设计已调试通过，请放心使用。请到：道客巴巴或豆丁网充值购买word版，省打字，直接修改即可，价格较便宜，在这里百度较贵！搜索：数据结构__用邻接表来简化图的计算__课程设计
设计题目：用邻接表来简化图的计算
课题名称用邻接表来简化图的计算院系年级专业学号姓名成绩
课题设计目的与设计意义1、课题设计目的：1熟练掌握图的概念和性质和图的存储方法；2连接邻接表的建立步骤和代码的书写；3两种对图的遍历的具体操作4理解邻接表对图的操作的意义。2、课题设计意义：通过课程设计的方式，可以使我们更加全面的理解邻接表的建立和两种不同方法的遍历的优缺点，使我们更加全面深刻的理解图的概念和有向无向图表的应用及其代码的书写和这其中要注意的问题，培养我们更加全面的思考问题。指导教师：
年月日
目录第一章图的概念和邻接表的表示方法........................................................................21.1图的概念.........................................................................................................21.2邻接表表示法..................................................................................................3第二章邻接表在图中的应用........................................................................................32.1连接表的建立..................................................................................................32.2.1连通图的深度优先搜素遍历...............................................................52.2.2连通图的广度优先搜索遍历...............................................................62.3对上述操作进行的代码书写及运行结果......................................................6
2.3.1上述的全部代码...................................................................................62.3.2运行结果.............................................................................................14第三章总结................................................................................................................183.1后语................................................................................................................183.2参考文献：....................................................................................................18
1
简介图（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只有顶点而没有边。
2
第一章图的概念和邻接表的表示方法1.1图的概念.图G是由两个集合和E组成，记为G=（V,E），其中V是顶点的有穷非空集合，E是V中顶点偶对（对称边）的有穷集。通常，也将图G的顶点集和边集分别记为V(G)和E(G)。E（G）可以使空集，若Ｅ（Ｇ）为空，则图Ｇ只有顶点而没有边。若图Ｇ中的每一条边都有方向的，则称Ｇ为有向图。有向边也称为弧，边的始点称为弧尾，终点称为弧头。若图Ｇ中的每一条边都是没有方向的，则称Ｇ为无向图。若图Ｇ的顶点数ｎ和边数ｅ满足：若Ｇ为无向图，恰好有ｎ（ｎ－１）／２条边的无向图则称为无向完全图，恰好有ｎ（ｎ－１）条边的有向图称为有向完全图。
无向图中顶点ｖ的度是关联于该点的边的数目，记为Ｄ（ｖ）．若Ｇ为有向图，则把以顶点Ｖ为终点的边的数目，称为Ｖ的入度，记为ＩＤ（Ｖ）；把以顶点ｖ为始点的边的数目，称为Ｖ的出度，记为ＯＤ（Ｖ）。若将图的每一条都赋上一个权，则称这种带权图为网络。连通图和连通分量1．顶点间的连通性在无向图G中，若从顶点v
i到顶点vj有路径(当然从vj到vi也一定有路径)，则称vi和vj是连通的。2．连通图若V(G)中任意两个不同的顶点vi和vj都连通(即有路径)，则称G为连通图。3．连通分量无向图G的极大连通子图称为G的连通分量。强连通图和强连通分量1．强连通图有向图G中，若对于V(G)中任意两个不同的顶点v
i和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。2．强连通分量有向图的极大强连通子图称为G的强连通分量。注意：①强连通图只有一个强连通分量，即是其自身。②非强连通的有向图有多个强连分量。1.2邻接表表示法这种表示法类似树的孩子链表表示法。对于图Ｇ中每一个顶点Ｖｉ，该方法把所有邻接与Ｖｉ的顶点ｖｊ链成一个单链表，这个单链表就称为顶点Ｖｉ的邻接表。
3
邻接表中每个表节点均有两个域，其一是邻接点域，用以存放与Ｖｉ相邻的顶点Ｖｊ的序号ｊ；其二是链域，用来将邻接表的所有表结点链在一起。并且为每个顶点Ｖｉ的邻接表设置一个具有两个域的表头结点：一个是顶点域，用来存放顶点Ｖｉ的信息；另一个是指针域，用于存放指向Ｖｉ的连接表中的第一个表结点的头指针。邻接表的结点结构：（1）表结点结构邻接表中每个表结点均有两个域:
①邻接点域adjvex存放与vi相邻接的顶点vj的序号j。②链域next将邻接表的所有表结点链在一起。注意：若要表示边上的信息(如权值)，则在表结点中还应增加一个数据域。第二章邻接表在图中的应用2.1连接表的建立对于无向图而言，Vi的邻接表中的每一个表结点都对应与于Vi相关联的一条边；对于有向图来说，Vi的连接表中的每一个表结点都对应与以Vi为始点射出的一条边。因此，我们将无向图的连接表称链表，将有向图的邻接表称为出边表，将邻接表的表头向量称为顶点表。
邻接表的结点结构：（2）头结点结vertexfirstedge顶点vi邻接表的头结点包含两个域：①顶点域vertex存放顶点vi的信息②指针域firstedgevi的邻接表的头指针。注意：①为了便于随机访问任一顶点的邻接表，将所有头结点顺序存储在一个向
量中就构成了图的邻接表表示。
adjvexnext
4
②有时希望增加对图的顶点数及边数等属性的描述，可将邻接表和这些属性放在一起来描述图的存储结构。2．无向图的邻接表对于无向图，vi的邻接表中每个表结点都对应于与vi相关联的一条边。因此，将邻接表的表头向量称为顶点表。将无向图的邻接表称为边表。【例】对于无向图G5，其邻接表表示如下面所示，其中顶点v0的边表上三个表结点中的顶点序号分别为1、2和3，它们分别表示关联于v0的三条边(v0，v1)，(v0，v2)和(v0，v3)。注意：①为了便于随机访问任一顶点的邻接表，将所有头结点顺序存储在一个向量中就构成了图的邻接表表示。②有时希望增加对图的顶点数及边数等属性的描述，可将邻接表和这些属
性放在一起来描述图的存储结构。邻接表的形式说明及其建表算法（1）邻接表的形式说明typedefstructnode{//边表结点intadjvex；//邻接点域structnodenext；//链域//若要表示边上的权，则应增加一个数据域}EdgeNode;typedefstructvnode{//顶点表结点VertexTypevertex；//顶点域EdgeNodefirstedge；//边表头指针}VertexNode；
typedefVertexNodeAdjList[MaxVertexNum]；//AdjList是邻接表类型typedefstruct{AdjListadjlist；//邻接表intn，e；图中当前顶点数和边数}ALGraph；//对于简单的应用，无须定义此类型，可直接使用AdjList类型。2.2用连接表对图的遍历和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础.深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它对无向图和有向用。2.2.1连通图的深度优先搜素遍历深度优先搜索遍历类似于树的前序遍历。假设给定图G的初态是所有均未
5
曾访问过，在G中任选一顶点Vi为初始出发点，则深度优先搜索可定义如下：首先，访问出发点Vi，并将其标记为已访问，然后，依次从vi出发搜索vi的每一个邻接点Vj，若Vj未被访问过，则以Vj为新的出发点继续进行深度优先搜索。特点为尽可能先对纵深方向进行搜索，故称之为深度优先搜索。图的深度优先遍历的递归定义假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-FirstSearch)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。深度优先搜索的过程设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有路径相通的顶点都已经访问到为止。算法分析
6
对于具有n个顶点和e条边的无向图或有向图，遍历算法DFSTraverse对图中每顶点至多调用一次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#definem20typedefcharvextype;typedefintadjtype;typedefcharrextype;typedefstructnode{intadjvex;structnodenext;}edgenode;typedefstruct
{vextypevertex;edgenodelink;}vexnode;vexnodega[m];vexnodegl[m];typedefstruct{vextypevexs[m];adjtypearcs[m][m];}graph;typedefintdatatype;
7
typedefstruct{datatypedata[m];intfromt,rear;}sequeue;sequeueQ;intn,e;creat_graph(graphga)//无向图的建立//{inti,j,k;getchar();
printf("请输入顶点信息\n");for(i=0;ivexs[i]);}for(i=0;iarcs[i][j]=0;for(k=0;k
ga->arcs[i][j]=1;ga->arcs[j][i]=1;}for(i=0;ivexs[i],ga->arcs[i][j]);printf("\n");}voidcreatadjlist(ga)//无向图的邻接表//vexnodega[];{
8
inti,j,k;edgenodes;printf("请输入顶点信息\n");getchar();for(i=0;i
printf("输入顶点的对序号\n");scanf("%d%d",&i,&j);s=(edgenode)malloc(sizeof(edgenode));s->adjvex=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;}}
intvisited[m];graphg;voiddfsl(inti)//深度遍历无向连接表//{edgenodep;printf("node:%c\n",ga[i].vertex);visited[i]=1;p=ga[i].link;while(p!=NULL){if(!visited[p->adjvex])dfsl(p->adjvex);
9
p=p->next;}}voidbfsl(k)//广度遍历无向连接表//{inti;edgenodep;sequeueQ;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(graphgl)//有向网的建立和输出//{inti,j,k;getchar();printf("请输入顶点信息：\n");for(i=0;ivexs[i]);}for(i=0;i
10
for(j=0;jarcs[i][j]=0;for(k=0;karcs[i][j]=1;}for(i=0;ivexs[i],gl->arcs[i][j]);
printf("\n");}}voidyoubiao(gl)//有向连接表的建立//vexnodegl[];{inti,j,k;edgenodes;printf("请输入顶点信息\n");getchar();for(i=0;i
gl[i].vertex=getchar();gl[i].link=NULL;}for(k=0;kadjvex=j;s->next=gl[i].link;gl[i].link=s;
11
}}voiddfsla(intr)//深度遍历连接表//{edgenodep;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;}}voidbfsla(intt)//广度遍历连接表//{inti;edgenodep;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;
12
}}}SETNNULL(sequeueQ){Q->fromt=-1;Q->rear=-1;}EMPTY(sequeueQ){if(Q->fromt==Q->rearreturn1;
elsereturn0;}datatypeDEQUEUE(sequeueQ){if(EMPTY(Q))printf("队空\n");elsereturnQ->data[(Q->fromt+1)%m];}ENQUEUE(sequeueQ,datatypex){
if(Q->fromt==(Q->rear+1)%m)printf("队满！\n");else{Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%m;}}voidmain(){intc,i,k,r,t,w=1,y=1;
13
graphga,gl;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){case1:printf("请输入网的定点数和边数\n");scanf("%d%d",&n,&e);creat_graph(&ga);break;case2:creatadjlist(&ga);break;case3:
printf("请输入遍历的初时代码\n");scanf("%d",&i);dfsl(i);break;case4:printf("请输入遍历的初时代码\n");scanf("%d",&k);bfsl(k);break;case5:printf("请输入网的定点数和边数\n");scanf("%d%d",&n,&e);youxiangwang(&gl);break;
14
case6:youbiao(&ga);break;case7:printf("请输入遍历的初时代码\n");scanf("%d",&r);dfsla(r);break;case8:printf("请输入遍历的初时代码\n");scanf("%d",&t);bfsla(t);break;case9:break;}
}}2.3.2运行结果1无向图的建立与输出：
图1无向图的建立与输出
15
2为无向邻接表的深度遍历：
图2无向邻接表的深度遍历3为无向邻接表的广度遍历：
图3无向邻接表的广度遍历
16
4无向图的建立与输出：
图4无向图的建立与输出5为有向邻接表的深度遍历：
图5有向邻接表的深度遍历
17
6为有向邻接表的广度遍历：
图6有向邻接表的广度遍历第三章总结3.1后语经过这次对邻接表的课程设计，是我明白了，动手远比说的复杂，对于知识的掌握要更加全面，要求我们更加全面仔细的思考每一个问题，培养了我们独立思考，解决问题的能力使我受益良多。3.2参考文献：[1]徐孝凯，贺桂英.数据结构(c语言描述).北京：清华大学出版社.2004[2]严蔚敏，吴伟民.数据结构(c语言版).北京：清华大学出版社.2007[3]谭浩强.c语言程序设计教程.北京：高等教育出版社.2007
|
|
