数据结构第七章[图].ppt

;★ 基本术语;★基本术语;(b). 这条边依附于顶点vi 和vj。;v1; 无向图：; 1.顶点的度; 边的数目达到最大的图称为完全图. 边的数目达到或接近最大的图称为稠密图,否则,称为稀疏图.; 2. 路径; 3.子图 ; 4.图的连通; 5.生成树;对于一个图,需要存储的信息应该包括:;一.邻接矩阵存储方法;0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0;(1).无向图的邻接矩阵一定是一个对称矩阵.;除了邻接矩阵中的n*n个元素存储顶点间的邻接关系 外往往还需要另设一个向量存储n个顶点的信息。 类型定义如下: #define Vnum 图的顶点数 enum adj{0,1}; typedef adj adjmatrix[vnum][vnum];;无向网邻接矩阵的建立算法如下: 思想:首先将矩阵A的每个元素都初始化为∞ 然后,读入 边及权值(i,j,Wij),将A的相应元素置成Wij 。;二.邻接表存储方法;1;0;#define VERNUM 图的顶点数 typedef struct Node { int adjvex; // 该弧所指向的顶点的位置 struct Node *next; // 指向下一条弧的指针 }EdgeNode; typedef struct Vnode { //顶点结点的结构 VertexType vertex; //顶点信息 EdgeNode *link; //指向第一条依附该顶点的弧 } AdjList[VERNUM];;思想:(1)将邻接表表头数组初始化,第i个表头的vertex为i,link为nil。 (2)读入顶点对i,j,产生一个表结点,将j放入到adjvex域,将该结点链到表头的link域上。; void build-adjlist(AdjList ga) { scanf(“%d,%d”,n,e); //读入顶点数，边数e for (i=0; in ;i++) //初始化邻接表 { ga[i].Vertex=i; ga[i].link=Null; } for( j=0;je;j++) {scanf(“%d,%d”,i,j); //读入顶点对i,j p=new struct EdgeNode; p-adjvex=j; p-next=ga[i].link; ga[i].link=p;} };邻接多重表 (Adjacency Multilist);顶点结点的结构 存储顶点信息的结点表以顺序表方式组织, 每一个顶点结点有两个数据域： data 存放与该顶点相关的信息， Firstout 是指示第一条依附该顶点的边的指针。 在邻接多重表中,所有依附于同一个顶点的边都链接在同一个单链表中。 ;从顶点i出发, 可以循链找到所有依附于该顶点的边，也可以找到它的所有邻接顶点。 ;有向图的情形 在用邻接表表示有向图时，有时需要同时使用邻接表和逆邻接表。用有向图的邻接多重表(十字链表)可把这两个表结合起来表示。 边结点的结构;顶点结点的结构 每个顶点有一个结点，它相当于出边表和入边表的表头结点：其中， 数据域data存放与该顶点相关的信息， Firstin指示以该顶点为头 (箭头端)的第一条边。 Firstout指示以该顶点为尾(出边端)的第一条边.;邻接多重表的结构; 从图中某个指定的顶点出发, 按照某一原则对图中 所有顶点都访问一次, 得到一个由图中所有顶点组成的 序列, 这一过程称为图的遍历.; 为了标记某一时刻图中哪些顶点是否被访问,定 义一维数组visited[1:n], 有 1 表示第i个顶点已经被访问 visited[i] = 0 表示第i个顶点还未被访问;例如：用深度优先有哪些信誉好的足球投注网站法遍历下图。;现将深度优先有哪些信誉好的足球投注网站的递归算法描述如下：; 分析上述过程,在遍历图时,对图中每个顶点至多调用一次dfs过程，因为一旦某个顶点被标志成已被访问，就不再从它出发进行有哪些信誉好的足球投注网站。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构，当用二维数组表示邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需时间为O(n2 ),其中n