图的应用算法.pptx

图的应用算法;并查集 (Union-Find Sets);设S1={0,6,7,8 }, S2={1,4,9}, S3={2,3,5};初始时, 用函数UFSets(s)构造一个森林, 每棵树只有一个结点, 表示集合中各元素自成一个子集合 S[i] = -1, i = 0, 1, …, n-1 用Find(i)寻找集合元素i的根 如果有两个集合元素i和j Find(i)==Find(j) 表明这两个元素在同一个集合中 如果两个集合元素i和j不在同一个集合中,可用 Union(i,j)将它们合并到一个集合中;集合S1,S2和S3的双亲表示;下标 parent; 并查集操作的算法 查找;int Find( int *parent, int x ) { if ( parent[x]0 ) return x; else return Find( parent, parent[x] ); } ;void Union ( int *parent, int s1, int s2 ) { //求两个不相交集合s1与s2的并 parent[s1] += parent[s2]; parent[s2] = s1; //将s2连接到s1下面 };合并;执行一次Union操作所需时间是O(1)，n-1次Union操作所需时间是O(n)。 若再执行Find(0), Find(1), …, Find(n-1), 若被有哪些信誉好的足球投注网站的元素为i，完成Find(i)操作需要时间为O(i)，完成n次有哪些信誉好的足球投注网站需要的总时间将达到 改进的方法 按树的结点个数合并 按树的高度合并 压缩元素的路径长度;按树结点个数合并 结点个数多的树的根结点作根;void Union ( int *parent, int s1, int s2 ) { //按Union的加权规则改进的算法 int temp = parent[s1]+parent[s2]; if ( parent[s2]parent[s1] ) { parent[s1] = s2; //s2中结点数多 parent[s2] = temp; //s1指向s2 } else { parent[s2] = s1; //s1中结点数多 parent[s1] = temp; //s2指向s1 } };按树高度合并 高度高的树的根结点作根;Union操作的折叠规则;int Find( int *parent, int i ) { //使用折叠规则的有哪些信誉好的足球投注网站算法 for( int j=i; parent[j]=0; j=parent[j] ); //让 j 循双亲指针走到根 while ( i!=j ) { //换parent[i]到j int temp = parent[i]; parent[i] = j; i = temp; } return j; } ;堆(Heap);最小堆的定义;堆的建立;将一组用数组存放的任意数据调整成堆;;;;void FilterDown( MinHeap Heap, int i, int m ) { int i=start, j=2*i+1; //j是i的左孩子 ElemType temp = Heap.heap[i]; while ( j=Heap.MaxSize ) { if ( jHeap.MaxSize Heap.heap[j].keyHeap.heap[j+1].key) j++; if ( temp.key=Heap.heap[j].key ) break; else { Heap.heap[i] = Heap.heap[j]; //下面的上浮 i = j; j = 2*j+1; //向下滑动 } } Heap.heap[i] = temp; } ;int Insert( MinHeap Heap, ElemType x ) { if ( Heap.CurrentSize==Heap.MaxSize ) { cerr 堆已满 endl; re