边表（邻接矩阵） 顶点表.pptVIP

* §7.3.2 广度优先遍历 算法 遍历算法类似于DFSTraverse void BFS(ALGraph *G, int k) { //以vk为源 InitQueue(Q); //队列Q初始化 printf(“%c”, G-adjlist[k].vertex); //访问源vk Visited[k]=TRUE; EnQueue(Q, k); //相当于vk入队 * §7.3.2 广度优先遍历 while ( !QueueEmpty(Q) ) { i=DeQueue(Q); //vi出队 p=G-adjlist[i].firstedge; //取vi边表头指针 while(p) { //依次有哪些信誉好的足球投注网站vi的邻接点vj if(!Visited[p-adjvex]) //vj未访问过，设p-adjvex=j printf(“%c”,G-adjlist[p-adjvex].vertex); //访问vj Visited[p-adjvex]=TRUE; EnQueue(Q, p-adjvex); //vj入队 } p=p-next; //在下一边表结点中找vi下一个邻接点 } } } * §7.3.2 广度优先遍历 BFS队列 时间 每个顶点入队一次，每个边表结点有哪些信誉好的足球投注网站一次 时间与dfs相同 * §7.4 图的连通性问题 §7.4.1 无向图的连通分量和生成树 1.求连通分量 每外部调用一次DFS或BFS，可求一连通分量的顶点集 2.生成树和生成森林 生成树 连通图G的极小连通子图，但包含G的所有顶点（支撑树），不唯一 n个顶点的连通图的生成树一定有n-1条边 * §7.4.1 无向图的连通分量和生成树 生成森林：各连通分量的生成树集合 求生成树和生成森林（使用DFS和BFS） 设G是无向图，?v∈V(G)做出发点 若图连通，则做一次DFS或BFS，必将G中n个顶点都访问到，且只做一次访问 两种有哪些信誉好的足球投注网站方法中，从vi有哪些信誉好的足球投注网站到vj时，须经过边(vi,vj)，故只需添加输出边的操作即可： * §7.4.1 无向图的连通分量和生成树 在dfs和bfs中，均在 while(p) { if( !Visited[p-adjvex] ) { 加入打印：（i，p-adjvex） //dfs须在递归前加入 } 若G连通则求出的生成树，否则为生成森林 若G为有向图，仅当源点为有根图的根时，才能求得生成树，否则为生成森林 * * * * * * * * * * * * * * * * * * * * Ch.7 图 图是一种复杂的非线性结构 应用：AI、工程、数学、生物、计算机 结点间的逻辑关系：任两个结点都可能相关 * * §7.1 概念 Def：图由两集合组成G=(V, E) V(G):顶点集——顶点的有穷非空集 E(G):边集——V中顶点偶对的有穷集 无向图：边由顶点的无序对构成。 和 表示同一条边，称为无向边 有向图：边由顶点的有序对构成。 和 表示不同的有向边 弧尾 ——起点 弧头 ——终点 * * §7.1 概念 例子： 约定：只讨论简单图 不允许有反身边：即 或 则 不允许平行边： 中不允许有重复元素 * * §7.1 概念 顶点和边的关系：设 无向图： 当 时，则为零图 当 ，则称之为（无向）完全图 完全图中任一顶点到其他顶点均有边 有向图： 当 ，则称之为有向完全图 * * §7.1 概念 稀疏图、稠密图. 边少、边多. 邻接与关联（依附） 若 ，则 和 互为邻接点 若 ，则 邻接到 ， 邻接自 边 和 关联（依附）于顶点 和 不好定义前驱和后继 * * §7.1 概念 顶点的度 无向图：关联于顶点的边数 。例 有向图：出度—以 为起点的边数 入度—以 为终点的边数 ——对有向或无向图均成立