10_非线性数据结构.pptVIP

如果(x,y)是无向图中的一条边，则称x与y互为邻接点； 如果x,y是有向图中的一条弧，则称y为x的邻接点。 x y x y （1）邻接矩阵 使用两个数组，一维数组存储顶点的信息，二维数组存储顶点之间边或弧的信息，这个二维数组又称邻接矩阵 对于图G=(V,E)： 对于带权的图： 其中W(i,j)是与边或弧相关的权。 邻接矩阵示例 0 1 3 2 5 2 8 1 3 0 1 2 3 4 1 0 2 3 4 (a)无向图 (b)有向图 (c)网络 0 1 3 2 4 0 1 3 2 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 0 1 3 2 (a)无向图邻接矩阵 (b)有向图邻接矩阵 (c)网络邻接矩阵 L1=[0,1,2,3,4] L2=[0,1,2,3,4] L3=[0,1,2,3] 邻接矩阵的元素值的计算 对于图G=(V,E)： 对于带权的图： 其中W(i,j)是与边或弧相关的权。 （2）邻接表---数组与链表结合的形式 图中的每个顶点都建立一个单链表，链表中的结点是与该顶点邻接的各个顶点，这个单链表称为该顶点的邻接表，与该顶点邻接的顶点称为表结点。 用一个一维数组存储每个顶点的详细信息，每个顶点称为头结点 图的邻接表存储形式 图的遍历 是指从图的某个顶点出发访问图中其余所有顶点，并且使图中的每个顶点仅被访问一次的过程。 算法主要有深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站两种。 1．深度优先有哪些信誉好的足球投注网站 假定从图中某个顶点v 出发进行遍历，则首先访问此顶点，然后依次从v的各个未被访问的邻接点出发，执行深度优先有哪些信誉好的足球投注网站遍历，直至图中所有和v相通的顶点都被访问到 若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 图的深度优先遍历举例 假定从图中某个顶点v出发进行遍历，则首先访问此顶点，再依次访问v的所有未被访问过的邻接点，然后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和v有路径相通的顶点都被访问到。 若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 2．广度优先有哪些信誉好的足球投注网站 图的广度优先遍历举例 以图(a)为例，假设从A出发进行广度优先有哪些信誉好的足球投注网站，首先访问A，然后依次访问A的各个未被访问过的邻接顶点B、E、D,再分别从B、E、D出发，访问它们的所有还未被访问过的邻接顶点C、F、G。 考虑一个通信网的建设问题。假定在多个城市间建立通信网络，将城市作为顶点，将所有可能的通信线路作为边，就构成一个图结构。再以通信线路的造价作为边的权重就构成一个无向网络。在保证通信功能的前提下，为了使总造价最小，需要寻找网络中权重之和最小的连通子图。 假定G={ V, E }为连通网络，其中V为顶点集合，E为带权边集合。 设置生成树顶点集合U，最初它只包含某一个顶点。设置生成树边集合T，最初为空集。 而后考察这样的边，它的一个顶点u∈U，另一个顶点v∈V-U，每次从所有这样的边中选择权值最小的边(u, v)加入集合T，并把顶点v加入到集合U中。 如此不断重复，直到所有顶点都加入到集合U中为止。 P105 习题3 10，11，12，13 补充 1.下列是一个二叉树的顺序存储结构，元素放在Python的列表中，请画出这棵二叉树。 L=[0,E,B,D,F,C,0,A,0,0,G,H,0,0,I,K] 提示：下标为1的是根结点，0表示空结点(即无此结点) 2.对第13题的图，写出其邻接矩阵 3.对第13题的图，画出其邻接表（示意图） 4.对第13题的图，给出从结点3开始的广度优先遍历序列。 第10讲非线性数据结构 计算机教学实验中心 第 * 页 西安交大 电信学院 管理学院 医学院 …… 信通系 电子系 计算机系 计教中心 …… 计01 计02 计12 张三 李四 王五 树形结构是逐层向下分支定义的层次结构。 树形结构广泛存在客观世界中：家谱、行政区域划分、各种社会组织机构、操作系统中的目录等 第 * 页 树是一个或多个结点组成的有限集合T，有一个特定结点称为根，其余结点分为m（m?0）个互不相交的集合T1，T2，…,Tm。每个集合又是一棵树，被称为这个根的子树。 A B C D E F G H I J 一般的树 K L M 第 * 页 结点的度：结点拥有的非空子树的个数。 树的度：树中所有结点的度中的最大值。 叶子结点：度为零的结点。 分支结点：度不为零的结点。 孩子结点和父结点：某结点所有子树的根结点都称为该结点的孩子结点，同时该结点也称为其孩子结点的父结点或双亲结点。 结点的层次：根结点的层