连通分量 无向图的极大连通子 图称为连通分量 连通图的连通分量即为 自身 ⊙⑥④ 有向图的极大强连通 ⊙Q@ 子图称为强连通分量 强连通图的强连通分量 (b) 即为自身 Khn 2021/2/11 数据结构及其算法第7章图
•连通分量 •无向图的极大连通子 图称为连通分量 • 连通图的连通分量即为 自身 •有向图的极大强连通 子图称为强连通分量 • 强连通图的强连通分量 即为自身 2021/2/11 数据结构及其算法 第7章 图 12
生成树、生成森林 仅考虑无向图 从图中删去一些边,使得图中不再存在回路,则 到原图的生成树或生成森林 连通图得到生成树 非连通图得到生成森林 结果不一定唯 根据树的性质,n个结点的树有且仅有n-1条边 ⊙ ①① (a) 2021/2/11 数据结构及其算法第7章图 13
•生成树、生成森林 • 仅考虑无向图 •从图中删去一些边，使得图中不再存在回路，则得 到原图的生成树或生成森林 • 连通图得到生成树 • 非连通图得到生成森林 • 结果不一定唯一 •根据树的性质，n个结点的树有且仅有n-1条边 2021/2/11 数据结构及其算法 第7章 图 13
7.2图的表示与实现 多重链表法 邻接矩阵法 邻接表法 囚中 多重链表法表示 (a)有向图 (b)无向图 (b) 2021/2/11 数据结构及其算法第7章图
7.2 图的表示与实现 •多重链表法 •邻接矩阵法 •邻接表法 2021/2/11 数据结构及其算法 第7章 图 14 多重链表法表示 (a) 有向图 (b) 无向图
邻接矩阵法:用二维数组(矩阵)记录顶点之间的 边信息 无向图可以只存储矩阵的上/下三角 G1 0000 arcs 1000. 1010 10101 G2 arcs=0 1 011 01100 2021/2/11 数据结构及其算法第7章图
•邻接矩阵法：用二维数组（矩阵）记录顶点之间的 边信息 •无向图可以只存储矩阵的上/下三角 2021/2/11 数据结构及其算法 第7章 图 15
对于网,邻接矩阵还可以记录边的权值,以特殊值 (如无穷大)表示没有边 5 8 5 o∞5 2021/2/11 数据结构及其算法第7章图 16
•对于网，邻接矩阵还可以记录边的权值，以特殊值 （如无穷大）表示没有边 2021/2/11 数据结构及其算法 第7章 图 16