最小生成树.ppt

最小生成树GraphG=(V,E)有向图无向图表示方法邻接表邻接矩阵Graph结点=顶点:vertex,node边=弧:edge,arc,link边e=(u,v)u,v邻接(adjacent)边e和u,v关联结点的度数(degree)是与它相关联的边数子图子图(subgraph):边的子集和相关联的点集导出子图(inducedgraph):点的子集和相关联的边集图的存储——邻接矩阵邻接矩阵g[i][j]表示顶点i和顶点j的边关系是否有边相连边权值空间复杂度:O(n^2)访问速度快、直观、适合稠密图的存储方式—邻接矩阵邻接矩阵使用场合数据规模不大n<=1000,m越大越好稠密图最好用邻接矩阵图中不能有多重边出现在做网络流类型的题目时候多采用邻接矩阵,因为网络流的复杂度高,本身就要求数据规模不能太大,并且需要频繁地更新矩阵中的数据。图的存储方式—邻接表邻接表mp[i]用链表的方式存储顶点i的相邻结点空间复杂度:有向图O(2m+n)无向图O(4m+n)对稀疏图可以减少存储空间可以直接访问到一个点的相邻结点图的信息一般都不做修改图的存储方式—邻接表邻接表使用场合顶点数很多n>1000,边数却不多。采用邻接表存储后,很多算法的复杂度也都是跟边数有关。连通性的问题很多情况边数不多,多采用邻接表存储方式邻接表codestructedge{intx,y,nxt;;}bf[E];voidaddedge(intx,inty,){bf[ne].x=x;bf[ne].y=y;bf[ne].c=c;bf[ne].nxt=head[x];head[x]=ne++;}并查集(DisjointSet)导引问题在某个城市里住着n个人,现在给定关于n个人的m条信息(即某2个人认识), 假设所有认识的人一定属于同一个单位,请计算该城市最多有多少单位?