| 【数据结构】图 | 您所在的位置：网站首页 › 带权图采用邻接表表示实现无向图的广度优先搜索与有向图 › 【数据结构】图 |
【数据结构】图
|
目录
一、基本定义与性质基本术语
二、图的存储1. 邻接矩阵2. 邻接表3. 十字链表4. 邻接矩阵和邻接表存储的比较（1） 邻接矩阵（2） 邻接表
三、图的遍历1. 深度优先搜索 DFS（1） 思路（2） 算法实现邻接矩阵存储图邻接表存储图
2. 广度优先搜索 BFS（1） 思路（2） 算法实现邻接矩阵存储图邻接表存储图
四、图的应用1. 最小生成树（1） 普里姆 （Prim）算法A. 思路B. 算法实现
（2） 克鲁斯卡尔（Kruskal）算法A. 思路B. 算法实现
2. 关键路径（1） AOE网（3） 关键路径A. 思路B. 算法实现
一、基本定义与性质
图由两个集合 V 和 E 组成，记为 G = （V，E）， V 是顶点集，E 是边集 有向图： 顶点对 有序，意为一条由点 x 指向点 y 的有向边。 和 是不同的两条边 在 中，x 是始点 / 弧尾，y 是终点 / 弧头 无向图： 顶点对(x, y) 无序，(x, y) 和 (y, x) 指的是同一条 基本术语n 表示顶点数，e 表示边数 子图： 有一个图的顶点全部都是另一个图的顶点，边也全都是另一个图的边，这个图叫做另一个图的子图完全图 无向完全图： 有 n(n - 1) / 2 条边的无向图，说人话就是每两个顶点之间都有边有向完全图： 有 n(n - 1) 条边的有向图，说人话就是从任何一个顶点都能到任何一个其他顶点 稀疏图和稠密图： 边少的就是稀疏图，边多的就是稠密图网： 带权图邻接点： 无向图中，(v, v’) 表示 v 与 v’ 互为邻接点，v 和 v’ 相邻接，边 (v, v’) 依附于顶点 v 和 v’，边 (v, v’) 和顶点 v v’ 相关联度： 和顶点相关联的边的个数，记作TD(v) 入度： 有向图中从该点发出的边的个数，记作ID(v)出度： 有向图中从该点进入的边的个数，记作OD(v)TD(v) = ID(v) + OD(v)度是边数的两倍 路径长度： 一条路径上边的个数回路 / 环： 起点终点相同简单路径： 顶点不重复的路径简单回路 / 简单环： 起点终点相同，其他不出现重复顶点的回路连通： v 可以到达 v’，则称这两点连通连通图： 图中任意两点连通连通分量： 无向图中极大连通子图强连通图： 有向图中，从任意一个点可以到任意另一个点强连通分量： 有向图中极大强连通子图连通图的生成树： 含有图中全部顶点，但是边数减1，任意添加一条边，必定构成环有向树： 一个顶点入度为0，其余顶点入度为1 二、图的存储 1. 邻接矩阵二维数组，G[i][j] 代表 i 和 j 点的边情况 无向图中，G[i][j] = 1说明有边，G[i][j] = 0说明无边有向图中，G[i][j] = w说明有边，权值是w，G[i][j] = ∞说明无边 #define MaxInt 32767 #define MVNum 100 typedef char VerTexType; typedef int ArcType; typedef struct { VerTexType vexs[MVNum]; // 存顶点 ArcType arcs[MVNum][MVNum]; // 存边 int vexnum, arcnum; // 存顶点数和边数 }AMGraph; 2. 邻接表链式存储结构，分为表头结点表和边表 表头结点表：包含数据和指针，数据表示存的是哪个顶点，指针指向这个顶点相邻的边表集边表：包含数据，邻接点，指针，数据存储权值，邻接点存储是哪个点和本表的顶点相邻，指针指向下一个和顶点相邻的结点 #define MVNum 100 typedef struct ArcNode // 边表 { int adjvex; struct ArcNode *nextarc; OtherInfo info; }ArcNode; typedef struct VNode // 表头结点表 { VerTexType data; ArcNode *firstarc; }VNode, AdjList[MVNum]; typedef struct { AdjList vertices; int vexnum, arcnum; }ALGraph; 3. 十字链表个人觉得可以理解为有向图的邻接矩阵按邻接表的方式存储 看图自己理解吧~感觉考到的概率不大 -优点：可以存下大图 -缺点：麻烦，相对来说没有邻接矩阵直观（其实是本菜狗太弱了） 三、图的遍历 1. 深度优先搜索 DFS （1） 思路不撞南墙不回头，只要有没有走过的点就接着走，一条路走到底，直到不能走了就退回来，找到下一条能走的路 举个栗子 时间复杂度： O(V2) void DFS_AM(AMGraph G, int v) { cout w = p->adjvex; // w是p的值 if (!visited[w]) DFS_AL(G, w); // 只要w点没被遍历过 就递归遍历该点 p = p->nextarc; // p指向下一个边结点 } } 2. 广度优先搜索 BFS （1） 思路知道起点之后，第一次遍历起点，第二次遍历所有与起点距离为1的点，第三次遍历所有与起点距离为2的点，以此类推~ 举个栗子 时间复杂度： O(V2) void BFS_AM(Graph_AM G, int v) { cout if ((G.arcs[u][i] != 0) && (!visited[i])) // 该点没有被遍历过 且 该点和v之间有边 就遍历该点 { cout int u = queue[head ++ ]; // 取出队头并删去 while (u) { if (!visited[u->adjvex]) // 只要没遍历过就立刻遍历 { cout adjvex] = true; queue[rear ++ ] = G.vertices[u->adjvex].FirstEdge; // 把与目前遍历的点相邻的第一个点存进去 } u = u->Next; // 遍历下一个 } } } 四、图的应用 1. 最小生成树在一个连通网的所有生成树里权值之和最小的就是最小生成树。 （1） 普里姆 （Prim）算法 A. 思路从起点开始，每次循环中遍历所有点，选择还没有加入最小生成树且与生成树集合距离最短的点加入生成树，直到所有点都加入生成树中 挖坑~ （2） 克鲁斯卡尔（Kruskal）算法 A. 思路把所有边的权值按照从小到大排序，每次选择当前最小的，如果这条边连接的两个顶点有至少一个没有遍历过，就把这条边加入生成树，直到所有顶点都在生成树里 继续挖坑~ 2. 关键路径 （1） AOE网AOE网——带权有向无环图 边：活动顶点：事件权值：活动持续的时间基本概念 源点： 入度为0的点汇点： 出度为0的点带权路径长度： 一条路径上各边权值之和关键路径： 从源点到汇点带权路径长度最大的路径关键活动： 关键路径上的活动事件 vi 最早发生时间 ve(i) 从源点到 vi 的最长路径长度 ve(0) = 0 ve(i) = max{ve(k) + wk,i}事件 vi 最迟发生时间 vl(i) 不延误任何后继事件的最迟发生时间 vl(i) = min{vl(k) - wi,k}活动 ai = 最早开始时间 e(i) 等于事件 vj 的最早发生时间 e(i) = ve(i)活动 ai = 最晚开始时间 l(i) 等于事件 vk 的最迟发生时间减活动持续时间 l(i) = vl(k) - wi,k当一个活动的最早发生时间等于最晚发生时间，那么说明这个活动是关键活动 （3） 关键路径 A. 思路没有思路，找到最长的一条路径~~，然后凭直觉做吧~~ B. 算法实现再挖一个 |
深搜的结果是：v1 -> v2 -> v4 -> v8 -> v5 -> v3 -> v6 -> v7
【本文地址】
公司简介
联系我们