07 图
图的定义与术语
图的定义
\[
Graph = (V, ~E)
\]
无向图
用 \((x, y)\) 来表示两个顶点 x 和 y 之间的一条边。
无向完全图：\(n(n-1) / 2\) 条边。
- 邻接点：如果 (x, y) ∈ E，称 x, y 互为邻接点，即 x, y 相邻接
- 依附：边 \((x, y)\) 依附于顶点 x, y
- 相关联：边 \((x, y)\) 与 x, y 相关联
- 顶点的度：和顶点相关联的边的数目，记为 \(TD(x)\)
有向图
用 \(<x,y>\) 表示从 x 到 y 的一条弧 (Arc)，且称 x 为弧尾，y 为弧头。
- \(N={V, E}\)
- \(V={0, 1, 2, 3, 4}\)
- \(E={<0, 1>, <0, 3>, <0, 4>, <1,2>, <2,4>, <3, 2>}\)
有向完全图：\(n(n-1)\) 条边。
- 邻接：如果 \(<x,y> \in E\)，称 x 邻接到 y，或 y 邻接自 x
- 相关联：弧 \(<x,y>\) 与 x, y 相关联
- 入度：以顶点为头的弧的数目，记为 \(ID (x)\)
- 出度：以顶点为尾的弧的数目，记为 \(OD (x)\)
- 度：\(TD(x)=ID(x)+OD(x)\)
路径
回路
连通
子图
生成图
图的存储结构
邻接矩阵
- 无向邻接图又被叫做“对称阵”。
- 上图展示了有向图矩阵的性质⬆️
邻接表
无向图的
有向图的
网格
结点结构
//弧
class ArcNode {
int adjvex; //该弧所指向的顶点的位置
ArcNode *nextarc; //指向下一条弧的指针
InfoType *info; //该弧相关信息的指针,或权值
}
图的结构定义：
逆邻接表
十字链表
结点结构
邻接多重表
暂略
图的遍历
- 邻接矩阵: \(O(n^2)\)
- 邻接表: \(O(n+e)\)
- DFS & BFS 都是 \(O(n)\)
深度优先遍历
邻接矩阵的
void DFS(AMGraph G, int y) {//图G为邻接矩阵类型
cout << v;
visited[v] = true; //访问第v个顶点
for(w = O; w< G.vexnum; w+ +) {//依次检查邻接矩阵v所在的行
if( (G.arcs[v][w]!=0) && (!visited[w])) {
DFS(G, w); //w是v的邻接点，如果w未访问，则递归调用DFS
}
}
}
邻接表的
无
广度优先遍历
void BFS (Graph G, int v) { //按广度优先非递归遍历连通图G
cout<<v;
visited[v] = true; //访问第v个顶点
InitQueue(Q); //辅助队列Q初始化，置空
EnQueue(Q, v); //v进队
while(!QueueEmpty(Q)) { //队列非空
DeQueue(Q, u); //队头元素出队并置为u
for(w = FirstAdjVex(G, u); w >= O; w = NextAdjVex(G, u, w)) {
if(!visited[w]) { //w为u的尚未访问的邻接顶点
cout<<w;
visited[w] = true;
EnQueue(Q, w); //w进队
}//if
}
}//while
}//BFS
图的应用
最小生成树 (MST)
Minimum Spanning Tree
定义
- 但是含有 n 个顶点 n-1 条边的图不一定是生成树！
性质
Prim 算法
Kruskal 算法
最短路径
Dijkstra 算法
Floyd 算法
拓扑排序
有向无环图
定义
在 AOV 网没有回路的前提下，我们将全部活动排列成一个线性序列，使得若 AOV 网中有弧 \(<i，j>\) 存在，则在这个序列中，\(i\) 一定排在 \(j\) 的前面。具有这种性质的线性序列称为拓扑有序序列，相应的拓扑有序排序的算法称为拓扑排序。
方法
关键排序
