数据结构–图
于2020年11月1日2020年11月1日由Sukuna发布
1.图的定义和术语
1.图
图G由顶点集V和关系集E组成,记为:G=(V,E),V是顶点(元素)的有穷非空集,E是两个顶点之间的关系的集合...(连通图的连通分量是自身)
对有向图G
● 若在图G中,每对顶点vi和vj之间, 从vi到vj,且从 vj到vi都存在路径,则称G是强连通图。...有向图中
表示从i到j有n条边,列和就是入度,行和是出度
对于网来说道理亦同
2.邻接表:
无向图:把与头结点相连的所有元素都存进对应的链表里
有向图的邻接表:它指向的元素存进链表
有向图的逆邻接表...初始化:把进入点标记为U集合,每个节点到进入点的距离标记为V-U中各顶点到U的最短直接路径,相邻结点数组标记为A
进入Prim算法:遍历一遍V-U中各顶点到U的最短直接路径,发现V集合中1是最小的,C...进入U集
接着遍历与C连接的的点,更新V-U中各顶点到U的最短直接路径,我们发现C到F的距离为8,比无穷大小,更新值为8,把F中的相邻结点记为C
注意:在找最小的结点时,要忽略已经进入U集的结点的值,