图基本概念、遍历算法与生成树.pptVIP

* 求解多入口迷宫中一条路径的方法： * 广度优先周游 从图的某个（未访问过的）顶点v出发， 先访问顶点v（将其标记为已访问）， 接着依次访问v的所有未访问过的相邻结点w1，w2，…，wx， 然后，再依次访问与w1，w2，…，wx邻接的所有未被访问过的顶点，…… 以此类推，直到所有已访问顶点的相邻结点都被访问过。 这时，如果图中还有未被访问过的顶点，则从某个未被访问过的顶点出发进行同样方法有哪些信誉好的足球投注网站，直到图中所有顶点都被访问过时，周游结束． * 广度优先周游算法 从顶点v0出发的一个BFS序列为∶v0, v1, v2, v3, v4, v5, v6, v7 queue * 广度优先周游算法 1、每个顶点包含一个mark字段，在周游前所有顶点的mark字段均被置为FALSE，周游到该结点时将相应的mark字段改为TRUE。 2、在bft中调用函数bfs ( g , v )，从顶点v出发按广度优先周游g中能访问的各个顶点。 具体实现中使用一个队列q，队列元素的类型为Vertex。 * 广度优先算法的实现 void bfs ( Graph g , Vertex v ){ Vertex v1, v2; Queue q = createEmptyQueue ( ); /* 队列元素的类型为Vertex */ enQueue ( q ,v ) ; while ( !isEmptyQueue(q) ) { v1 =frontQueue ( q ) ; deQueue ( q ); //get a node from queue v1.mark = TRUE ; //set start from mark v2 = firstAdjacent ( g ,v1 ); //get nodes, enQueue while ( v2!=NULL ) { if ( v2.mark == FALSE ) enQueue ( q, v2 ); v2 = nextAdjacent ( g , v1 , v2 ) ; } } } * 邻接表数据结构（模拟过河问题） 这样就构成一条边 * 操作函数 * 广度优先周游算法 1、每个顶点包含一个mark字段，在周游前所有顶点的mark字段均被置为FALSE，周游到该结点时将相应的mark字段改为TRUE。 2、在bft中调用函数bfs ( g , v )，从顶点v出发按广度优先周游g中能访问的各个顶点。 具体实现中使用一个队列q，队列元素的类型为Vertex。 * * 过河问题图的生成： * * * * * * Hu Junfeng Hu Junfeng 图基本概念、遍历算法与生成树 胡俊峰 2013/05/14 * 回顾一下过去讲的一些内容 二叉树、堆、huffman树 有哪些信誉好的足球投注网站问题（栈、队列） 深搜 广搜 * 本次课主要内容 图的基本概念 图的相邻矩阵及邻接表的表示方法 图抽象数据类型 图的周游方法 求图的最小生成树（林） * 图的基本概念 反映连通关系及属性 反映顶点属性及关联 * 图与其他数据结构的关系 线性结构：唯一前驱，唯一后继，线性关系 树形结构：唯一前驱，多个后继，层次关系 图形结构：多对多、任意，网状关系 图结构中结点(图中通常称为顶点)的前驱和后继结点个数不再限制，即结点之间的关系是任意的 图是更复杂的非线性结构。 * 图由顶点（vertex）集合和边（edge）集合E组成， 记为G=(V，E)。 每条边就是一个顶点的偶对，所以E也就是V上的一个二元关系。 例如： V = { a,b,c,d}; E = {a,b, a,d, c,d, d,a} 图的形式化定义 a b c d * 在有向图中，V1，V3 表示从V1到V3的一条边，也称弧（尖括号表示）。V1为弧尾或始点，V3为弧头或终点。 在无向图中，(V1，V3)表示V1和V3之间的一条边。 (V1,V3) = (V3,V1) 无序对 V1 V3 V2 V4 V1 V3 V2 V4 有向图无向图 * 图顶点与边的关系 图G的顶点数n和边数e满足以下关系∶ 若G是有向图，则0≤e≤n(n-1) 有向完全图：有n(n-1)条边的有向图 若G是无向图，则0≤e≤n(n-1)/2 无向完全图：有n(n-1)/2条边的无向图 在顶点个数相同的图中，完全图具有最多的边数 V1 V3 V2 V4 * ‘度’ 的定义 关联：