一 学习小结
图的基本知识
1. 图分为无向图和有向图. 若无向图有 n(n-1)/2 条边, 则称之为无向完全图, 若有向图有 n(n-1) 条弧, 则称之为有向完全图
2. 带权图通常称为网
3. 度: 顶点 v 的度指和 v 相关联的边的数目, 记为 TD(v) 入度: 以 v 为头的弧的数目 出度: 以 v 为尾的弧的数目
4. 路径长度是一条路径上经过的边或弧的数目
5. 强连通图: 在有向图 G 中, 对于每一对 vi,vj∈V, 从 vi 到 vj 都存在路径
6. 连通生成树: 一个极小连通子图, 它含有图中全部顶点, 但只有足以构成一棵树的 n-1 条边 其中各边代价之和 (权) 最小的那棵生成树成为最小生成树
图的存储
1. 邻接矩阵
- #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;
创建邻接矩阵的时间复杂度为 O(n²)
2. 邻接表
- #define MvNum 100 // 最大顶点数
- typedef struct ArcNode // 边结点
- {
- int adjvex; // 该边所指向的顶点的位置
- struct ArcNode *nextarc;// 指向下一条边的指针
- }ArcNode;
- typedef struct VNode // 顶点信息
- {
- VertexType data;
- ArcNode *firstarc; // 指向第一条依附该顶点的边的指针
- }VNode,AdjList[MvNum]; //AdjList 表示邻接表类型
- typedef struct
- {
- AdjList Vertices; // 一维数组
- int vexnum,arcnum; // 图的当前顶点数和边数
- }Graph;
创建邻接矩阵的时间复杂度为 O(n+e) (顶点数 + 边数)
图的遍历
1. DFS 深度优先搜索
从某个顶点 v 出发, 遍历 v 所在的连通分量
2. BFS 广度优先搜索
最小生成树
1. Prim 算法 普里姆算法 -- 加点法
时间复杂度 O(n²) 适用于稠密图
主要步骤: 在所有 u∈ U, v∈V-U 的边 (u,v) 属于 E 中找一条权值最少的边(u0,v0), 并入集合 TE(N 上最小生成树中边的集合), 同时 v0 并入 U
2. Kruskal 算法 克鲁斯卡尔算法 -- 加边法
时间复杂度 O(e log e) 适用于稀疏图
初始状态为只有 n 个顶点而无边的非连通图 T = { V , { } } 每个顶点自成一个连通分量
主要步骤: 在 E 中选择权值最小的边, 若该边依附的顶点落在不同连通分量上(即不形成回路), 则将此边并入 T, 否舍去此边而选择下一条权值最小的边
最短路径:1路径上边的数目 2路径上边的权值之和
1. Dijkstra 算法 迪杰斯特拉算法
二 关于上次制定的目标和接下来的目标
这周没有合理安排时间大部分时间花在书面上, 导致上机实践的时间大大缩水, 很惭愧
下一周要先规划分配好时间, 尽量保证足够的实操时间
来源: http://www.bubuko.com/infodetail-3064165.html