数据结构与程序设计（7）.ppt

数据结构与　程序设计----第七章 上海东华大学 第七章　图 　图是一种比线性表和树更复杂的数据结构： 在线性表中，数据元素之间是线性关系，即一个元素有一个直接前趋和一个直接后继； 在树结构中，数据元素之间是层次关系，即每一层上的数据元素只能和上一层中至多一个数据元素（父结点）相关，但能与下一层的多个数据元素（儿子结点）相关； 在图结构中，任意两个数据元素之间都可能相关，即数据元素之间的关系可以是任意的。 7.1　图的基本概念和术语 1．图的定义 　图G是由顶点集合V和边的集合E组成，记作G=（V，E）。 　图中的边可以用顶点对来表示，如（u，v）表示顶点u和v之间的一条边，若（u，v）是一个有序对，即需要考虑边的方向，此图为有向图，有向边也称为弧；若（u，v）是一个无序对，即可以忽略边的方向，则图为无向图。 　如果顶点u到v有一条有向边，也可写作u?v，称顶点v与顶点u是相邻的。 2．图的基本概念和术语 （1）路径与回路 　如果v 1?v 2，v 2?v 3，…，v n-1?v n都是图中的有向边，则称顶点序列（v 1，v 2，…， v n）是一条路径，这条路径上的有向边数被称为路径长度。 　如果一条路径上除第一个和最后一个顶点可以相同外，其它都不相同，则称为简单路径。 　如果一条路径的第一个顶点与最后一个顶点相同，则称为回路或环 。若是一条简单路径的第一个顶点与最后一个顶点相同，则称为简单回路 。 （2）连通图 顶点的连通：如果从顶点u到顶点v（u≠v）之间至少有一条路径，则称u和v是连通的。 无向图的连通： 如果无向图中任 意两个顶点都是连 通的，则称该无向 图是连通的，无向 图中极大连通子图 称为连通分量。 有向图的强连通：对一个有向图，如果其中任意两个顶点u和v（u≠v）都有u到v和v到u的路径，则称该图是强连通的，有向图中的极大强连通子图称为该图的强连通分量。 （3）生成树：n个顶点的连通图的生成树是一个极小连通子图，它包含连通图的全部顶点及n-1条边，使所有顶点都连通但不构成回路。生成树具有两个特点： n个顶点的生成树包含n-1条边； 如果在生成树中任意增加一条边，则有一条回路。 （4）顶点的度 顶点v的度是指图中以v为端点的边数，通常记作TD（v）。对有向图还要区分顶点的入度和出度，顶点v的入度是指图中以v为终点的有向边数，记作ID（v）；顶点v的出度是指图中以v为始点的有向边数，记作OD（v）。 3 ．带权图 如果给图的每条边赋与一个权值，则称为带权图。在实际应用中，这个权值具有某种意义，如两个顶点间的距离，时间的耗费等。 7.2　图的存储结构 1．邻接矩阵 图的邻接矩阵表示法是用一个矩阵表示图中顶点间的相邻关系。对一个具有n个顶点的图G=（V，E），其邻接矩阵是一个nXn的矩阵，矩阵元素的值是： 对一个带权图，如果用W u v表示边（u，v）上的权值，则邻接矩阵元素的值是： 从图的邻接矩阵表示法可以看到以下特点： （1）无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称； （2）用邻接矩阵表示的图，很容易确定图中任意两个顶点是否有边相连。但要检测图中有多少条边，则需检测邻接矩阵的每个元素，需要花费较多时间。 2．邻接表 n个顶点的图用邻接表表示，是指用n个向前链表来表示各顶点间的邻接关系，第k个向前链表是由所有与顶点k相邻接的顶点构成的。所有向前链表的表头结点用一个数组来存放。 7.2　图的遍历 　对图的遍历是指从图中的一个顶点出发访问图中所有顶点，且每个顶点仅被访问一次。根据访问图中各顶点的顺序，遍历图的方法主要分为两种：深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站。 1．深度优先有哪些信誉好的足球投注网站 　对一个连通图深度优先有哪些信誉好的足球投注网站的遍历过程是：设图中的一个顶点u是出发点，首先访问出发顶点u，然后选择一个与u邻接且未访问过的顶点v，以v为出发点继续进行深度优先有哪些信誉好的足球投注网站，直到连通图中所有顶点都被访问过。 2．广度优先有哪些信誉好的足球投注网站 　对一个连通图广度优先有哪些信誉好的足球投注网站的遍历过程是：设图中的一个顶点u是出发点，在访问出发顶点u以后依次访问与u邻接且未访问过的所有顶点；然后分别以这些顶点为出发点继续进行广度优先有哪些信誉好的足球投注网站，直到连通图中所有顶点都被访问过。 　对于非连通图需要从多个顶点出发进行深度（或广度）优先有哪些信誉好的足球投注网站才能访问图中所有顶点。 [例7.1] 建立图的邻接矩阵和邻接表，并进行深度优先和广度优先有哪些信誉好的足球投注网站遍历。 建立邻接矩阵 　函数adj_matrix首先输入图的顶点数n并使二维数组mat的元素都为0，然后重复输入各条边的两个顶点u和v，令mat[u][v]和mat[v][u]均为1，如果输入编号为0的顶点，则输入边的过程结束，mat中存储了图的邻接矩阵，函数的返回值是顶点数n。 int adj_matrix(int mat[][M