欢迎来到天天文库
浏览记录
ID:34092905
大小:52.50 KB
页数:6页
时间:2019-03-03
《课程名称 数据结构14》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、课程名称数据结构14授课题目图有向图授课日期2003年11月26日授课班级生物医学工程授课时数4授课方式理论课授课重点、难点1.有向图及其表示方法:邻楼表,邻楼矩阵2.图的遍历,与树的遍历及线性3.掌握先深搜索与先广搜索授课内容、教具与时间分配授课内容、教具与时间分配第五章图51.1有向图及其表示方法(存储方法)(P127)图5.1有向图顶点的集合V={1,2,3,4},顶点表示对象弧的集合E={(1,2),(1,3),(2,4),(3,2),(4,3)}对象之间的关系图G=(V,E)有序对、相邻:一条弧:v→w,v为弧的尾,w为弧的头,是顶点v和w的有序对,w和v是
2、相邻的。①→②≠②→①,故而称为有向图。路经:顶点序列路径长途:弧的条数简单路径:简单环路:标号有向图:图5.2,顶点、弧附加信息无向图:若图中的边是顶点的无序对,则称此图为无向图。无向图中顶点间的联系不用→表示。5.1.2邻接矩阵P127一、邻接矩阵是有向图的一种表示方法(存储方法),是二维数组方法。二、图G=(V,E),V={1,2,3……n}用邻接矩阵表示有向图:ary〔i〕〔j〕行列有向图标号有向图i→j1a无0空格(布尔矩阵)0,1元素10对应图5.1对应图5.2三、函数adjmatrix建立图的邻接矩阵,返回图的顶点个数。9输入方法:v1v2weight=
3、110=1210③④……=000输入结束四、函数prmatrix打印邻接矩阵。5.1.3邻接表一、图的另一种表示方法(存储方法),是链接方法二、对图中的任一顶点,由此顶点出发的全部相邻顶点用一个向前链表表示,向前链表的前后次序不影响图顶点之间的相互联系。向前链表的表头结点,构成一个数组list[],表头结点有信息场和链场组成,信息场另作它用。图5.3p128。123两者等价132一、函数adjlist建立有向图邻接表,返回图的顶点个数。二、函数pradjlist打印邻接表。对p.128graph.h的说明1.#include"llist.h"p.392.adjmatr
4、ix(matrix)建立有向图(或无向图)邻接矩阵,返回顶点个数。实参是MAX×MAX二维数组名。二维数组matrix[][MAX]是邻接矩阵。输入图的顶点个数。v1v2weight=110对矩阵的每个元素赋值INFIN(9999)。v1v2weight=1210用循环语句向矩阵输入数据,以下图为例:v1v2weight=13910v1v2weight=220①②......v1v2weight=0009输入完毕,循环结束。③④3.prmatrix(mat,n)打印邻接矩阵。实参是已生成的邻接矩阵二维数组的数组名,和图的顶点个数。printf((mat[i][j])=
5、=INFIN)?"t":"%d",mat[i][j]);printf("");如果矩阵元素是INFIN不打印否则打印矩阵元素值即weight4.adjlist(list)建立有向图的邻接表,返回图的顶点个数。实参是大小为MAX的结构体数组变量。list[]是结构体数组变量。输入图的顶点个数。list[]赋初值。数据场目前暂空,也可供某些操作存放一定的标志。顶点标号以p.127图5.1为例,用循环语句输入数据建立邻接表:数组下标v1v2=12或v1v2=131v1v2=13v1v2=122v1v2=243v1v2=324v1v2=43v1v2=00输入完毕,循环结
6、束。5.pradjlist(list,n)打印邻接表数据场的值。实参是已生成的邻接表的表头结点所构成的数组的数组名,和图的顶点个数。以p.127图5.1为例。6.参考p.30,补写push(arg)和pop()。参考p.40inser(arg)和delete()补写engqueue(arg)和dequeue()。NODE*front=NULL,*rear=NULL;enqueue(arg)intarg;{NODE*ptr;ptr=getnode(NODE);ptr->info=arg;ptr->link=NULL;if(front==NULL)front=ptr;el
7、serear->link=ptr;rear=ptr;}dequeue(){NODE*ptr;intvar;if(front==NULL)return(-1);ptr=front;front=ptr->link;var=ptr->info;free(ptr);if(front==NULL)rear=NULL;return(var)}5.2有向图的遍历图遍历的定义:p130图的遍历比树的遍历要复杂,从树根到树中的每个结点只有一条路径,而从图的起始点到达图中的每个顶点可能存在着多条路径。当顺着图中的一条路径访问过某一个顶点后,可能还会顺着另一条路径回到该顶
此文档下载收益归作者所有