用破圈法求最小生成树

感觉上你那里的“算法基本思想”实现难度很大，因为图的连通性不好维护

找圈的话，随便找个节点为根DFS整个图，然后在这样的DFS生成树中，每条非树边都对应了一个圈，每次找一条非树边，删去所在圈中最长边生成一个新树，直到不存在非树边为止，剩下的就是最小生成树了

具体实现的时候，先求出一个DFS生成树，然后递归处理每棵子树

假设要处理的子树根节点为u，对该子树破圈法的粗略伪代码如下：

void 破圈法(u)

{

for ( v是u的每个子节点 ) 破圈法(v);

for ( e是连接u与其后继的每条非树边 )

{

v=e的另一个端点;

e'=u到v之间的最长树边;

if (w[e]>=w[e']) 删除边e;//w[e]表示e的权

else

{

//用w表示原先e'的在树中较深的端点,p[v]表示v的亲节点

删除边e';

if (v!=w)

{

将v列入u的子节点列表;

将p[v]、p[p[v]]、、w这条路径反向，并将p[v]列入v的子节点列表;

}

}

}

}

上述过程不加优化的时间复杂度为O(VE)，效率非常差

貌似其中找最长边和将v的若干祖先节点路径反向的两步优化空间比较大，或许可将整个时间复杂度下降到O(ElgV)，研究中

给你个函数

参数：数据窗口 adw_tv_date

三列：tv_id,tv_name, tv_ipid(就是你的code， name ，upcode)

long i, ll_id_len, ll_root_handle, ll_insert_handle, ll_currenthandle, ll_handle

string ls_id, ls_name, ls_father_id, ls_upid

treeviewitem ltvi_demo

ltvi_demolabel = '根目录'

ltvi_demopictureindex = 3

ltvi_demoselectedpictureindex = 4

ll_root_handle = tv_demoinsertitemlast(0,ltvi_demo) //插入根目录

for i = 1 to adw_tv_daterowcount() //循环整个数据窗口

ls_id = adw_tv_dateobjecttv_id[i] //取出三个值

ls_name = adw_tv_dateobjecttv_name[i]

ls_upid = adw_tv_dateobjecttv_upid[i]

ltvi_demolabel = ls_name

ltvi_demodata = ls_id

ltvi_demopictureindex = 1

ltvi_demoselectedpictureindex = 2

if isnull(ls_upid) or trim(ls_upid) = '' then //如果没有父节点，即为一级节点，放在根目录下

ll_insert_handle = tv_demoinsertitemlast(ll_root_handle,ltvi_demo)

else //否则根据父节点查找其父节点位置，调用函数wf_reader

ll_handle = tv_demoFindItem(RootTreeItem!, 0)

if ll_handle > 0 then

ll_handle = wf_reader(ll_handle,ls_upid)

if ll_handle > 0 then

tv_demoinsertitemlast(ll_handle,ltvi_demo)

end if

end if

end if

next

ll_currenthandle=tv_demofinditem(roottreeitem!,0)

tv_demoexpanditem(ll_currenthandle)

return 1

函数wf_reder

long ll_handle

long ll_handleOld

TreeViewItem ltvi_Item

String ls_label

String ls_data

if tv_demoGetitem(al_handle,ltvi_Item)= -1 then return -1

ls_data=Trim(String(ltvi_Itemdata))

if ls_data = as_target then

return al_handle

else

ll_handle = tv_demoFindItem(ChildTreeItem!,al_handle)

end if

if ll_handle > 0 then

if tv_demoGetitem(ll_handle,ltvi_Item)= -1 then return 0

ls_data=Trim(String(ltvi_Itemdata))

if ls_data = as_target then

return ll_handle//找到了要添加的节点

else

return wf_reader(ll_handle,as_target)

end if

else

ll_handleOld = al_handle

ll_handle = tv_demoFindItem(NextTreeItem!,ll_handleOld)

do while ll_handle < 0

ll_handle = tv_demoFindItem(ParentTreeItem!,ll_handleOld)

if ll_handle > 0 then

ll_handleOld = ll_handle

ll_handle = tv_demoFindItem(NextTreeItem!,ll_handleOld)

else

ll_handle = tv_demoFindItem(NextTreeItem!,ll_handle)

if ll_handle < 0 then

return -1

end if

end if

loop

if tv_demoGetitem(ll_handle,ltvi_Item)= -1 then return -1

ls_data=String(ltvi_Itemdata)

if ls_data = as_target then

return ll_handle//找到了要添加的节点

else

return wf_reader(ll_handle,as_target)

end if

end if

return ll_handle

里面不是写出来了么？先输入一个N代表有n个节点，然后输入1到1的路径，1到2的路径，一直输到N到N的路径。代码如下：

for(int j=1; j<=n; j++)

{

cin>>v;

if( v )

map[i][j] = v;

}

例如：N=2

v输入 0 2 2 0 代表有两个节点 从1到2和从2到1的距离都是2

我直接打了编译过就给你不保证没错。。。没过的话联系我

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<map>

#include<set>

#include<cstring>

#include<queue>

#include<vector>

#include<stack>

#include<cmath>

using namespace std;

const int INF = 2147483247,maxn = 105,maxm = 10005;

struct edge{

int x,y,v;

bool operator <(const edge &a)const{

if(v !=av)return v<av;else if(x !=ax)return x<ax;else return y<ay;

}

}V[maxm];

int N,M,fa[maxn];

int find(int x){

if(x == fa[x])return x;else return fa[x] = find(fa[x]);

}

int main(){

scanf("%d%d",&N,&M);

for(int i=1;i<=M;i++)

scanf("%d%d%d",&V[i]x,&V[i]y,&V[i]v);

sort(V+1,V+M+1);

for(int i=1;i<=N;i++)fa[i] = i;

for(int i=1;i<=M;i++)

if(find(V[i]x)!=find(V[i]y))fa[find(V[i]x)] = find(V[i]y),printf("%d %d\n",V[i]x,V[i]y);

return 0;

}

function [T,WT]=prim(A)

%Prim法求最小生成树

%A为无向图G={V，E}的权矩阵;

%T为A的最小生成树的权矩阵，WT为其权值。

n=length(A);

A(find(A==0))=inf;

T=zeros(n);WT=0;

V=2:n;%未通过点的集合

V1=1;%通过点的初始集合

p=1;%记录通过点的个数

i=1;[y,k]=min(A(i,:));%{从以1为一个端点，以V中的点为另一个端点的所有边中，找出权值最小的边%}

p=p+1;V1(p)=k;%将找到的点加到V1中

V(k-1)=[];T(i,k)=y;T(k,i)=y;%将找到的点从V中删去，并把相应边加到T中。

WT=WT+y;A(i,k)=inf;A(k,i)=inf;

while p<n

s=1;

for i=V1 %找出临跨V1和V的权值最小的边

y(s)=min(A(i,V));s=s+1;

end

y=min(y);%y为找出的最小权值

for i=V1 %找出与y相关联的两个点

for j=V

if(A(i,j)==y)T(i,j)=y;T(j,i)=y;A(i,j)=inf;A(j,i)=inf;WT=WT+y;

p=p+1;V1(p)=j;%将点加到V1中

V(find(V==j))=[];%将通过点从V中删掉

end

break;end;end;end

end

%可以在MATLAB中输入以下命令进行检验：

A=[inf 4 15 inf 7 inf 28;4 inf 9 inf inf inf inf;15 9 inf 25 5 inf inf;inf inf 25 inf 32 16 12;7 inf 5 32 inf inf 30;inf inf inf 16 inf inf 20;28 inf inf 12 30 20 inf]；

[T,WT]=prim(A)

数据结构（实验报告）

姓名： 高 申 雷

学号： 0613042024

日期： 2008年3月25日

一、实验题目： 停 车 场 管 理

二、问题描述：

设停车场是一个可以停放n辆汽车的狭长通道，且只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里向大门口处停放（最先到达的第一辆车放在停车场的最里面）。如果停车场已放满n辆车，则后来的车只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆次序。编制一程序模拟该停车场的管理。

三、需求分析：

停车场采用栈式结构，停车场外的便道采用队列结构（即便道就是等候队列）。停车场的管理流程如下：

①当车辆要进入停车场时，检查停车场是否已满，如果未满则车辆进栈（车辆进入停车场）；如果停车场已满，则车辆进入等候队列（车辆进入便道等候）。

②当车辆要求出栈时，该车到栈顶的那些车辆先d出栈（在它之后进入的车辆必须先退出车场为它让路），再让该车出栈，其他车辆再按原次序进栈（进入车场）。当车辆出栈完毕后，检查等候队列（便道）中是否有车，有车则从队列头取出一辆车压入栈中。

四、概要设计：

1、用栈模拟停车场，用队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。

2、每一组输入数据包括三个数据项：汽车到达或离去的信息，汽车牌照号码以及到达或离去的时刻。

3、每次输入完进行输出 *** 作：若是车辆到达，输出汽车在停车场内或便道上的停车位置；若是车辆离去，输出停留时间和应缴纳的费用（在便道上停留的时间不收费）。

4、其中栈以顺序结构实现，队列以链表结构实现。

五、详细设计：

1、定义栈（停车场） struct stack

初始化栈void initstack(stack s)

元素进栈int instack(stack s,cinfo x)

元素出栈cinfo outstack(stack s)

2、定义队列（车场外的便道）struct queue

初始化队列void initqueue(queue q)

元素进队列void inqueue(queue q,int num1)

元素出队列int outqueue(queue q)

3、处理车辆到达的情况void carrival(stack s,queue q,cinfo x)

处理车辆离开void carleave(stack s1,stack s2,queue q,cinfo x)

4、主程序void main()

注：详细设计中的具体代码见模块代码中。

六、模块代码：

#include"iostreamh"

int N;

const int M=5;//M为单元时间的收费值

struct cinfo//定义栈中元素的类型

{ int cnum; int atime;

};

struct stack//定义栈

{ cinfo cstack[3000];//这里随便定义一个数字表示数组的长度,因为后

int top; //面会根据用户输入的N值作为停车场能够停车的

int size; //数量

};

struct node//定义队列节点的类型

{ node next; int nnum;

};

struct queue//定义队列

{ node front,rear;

};

void initstack(stack s)//初始化栈

{ s->top=-1;

}

int instack(stack s,cinfo x)//元素进栈

{ //int 元素进栈n;

if(s->top==N-1)

{ cout<<"Stack is full!"<<endl; return 0;

} else

{ s->cstack[++s->top]=x;

return 1;

}

}

cinfo outstack(stack s)//元素出栈

{ cinfo y;

if(s->top<0)

{ ycnum=NULL;

yatime=NULL;

return y;

} else

{ s->top--;

return s->cstack[s->top+1];

}

}

void initqueue(queue q)//初始化队列

{ q->front=new node;

q->rear=q->front;

q->front->next=NULL;

q->front->nnum=0;

}

void inqueue(queue q,int num1)//元素进队列

{ node p;

p=new node;

p->nnum=num1;

p->next=NULL;

q->rear->next=p;

q->rear=p;

q->front->nnum++;

}

int outqueue(queue q)//元素出队列

{ node p;

int n;

if(q->front==q->rear) return 0;

else {

p=q->front->next;

q->front->next=p->next;

if(p->next==NULL)

q->rear=q->front;

n=p->nnum;

delete p;

q->front->nnum--;

return n;

}

}

void carrival(stack s,queue q,cinfo x)//处理车辆到达的情况

{ int f;

f=instack(s,x);

if(f==0) {

inqueue(q,xcnum);

cout<<"The Number"<<xcnum<<" "<<"car park into the pos"<<q->front->nnum<<" "<<"of the road"<<endl;

} else

{ cout<<"The Number"<<xcnum<<" "<<"car park into the pos"<<s->top+1<<" "<<"of the room"<<endl;

}

}

void carleave(stack s1,stack s2,queue q,cinfo x)//处理车辆离开

{ node p;

cinfo y;

int a,n=0;

while((s1->top>-1)&&(n==0))

{ y=outstack(s1);

if(ycnum!=xcnum) {

a=instack(s2,y);

} else

n=1;

}

if(ycnum==xcnum)

{ cout<<"The number"<<xcnum<<" "<<"car want to leave,the charge is"<<" "<<(xatime-yatime)M<<" "<<"yuan!"<<endl;

while(s2->top>-1)

{ y=outstack(s2);

n=instack(s1,y);

}

a=outqueue(q);

if(a!=0)

{ ycnum=a; yatime=xatime;

n=instack(s1,y);

cout<<"The Number"<<ycnum<<" "<<"car park into the pos"<<s1->top+1<<" "<<"of the room"<<endl;

}

} else

{ while(s2->top>-1)

{ y=outstack(s2);

n=instack(s1,y);

}

p=q->front;

n=0;

while(p->next!=NULL&&n==0)

{ if(p->next->nnum!=xcnum)

p=p->next;

else {

p->next=p->next->next;

q->front->nnum--;

if(p->next=NULL)

q->rear=q->front;

cout<<"The number"<<xcnum<<" "<<"want to leave from the road"<<endl;

n=1;

}

}

if(n==0)

{ cout<<"You have entered a wrong number!"<<endl;

}

}

}

void main()//主程序

{ //int maxsize;

cout<<"Start，Written by ZIGZ"<<endl<<endl<<endl;

cout<<"Please enter a number as the maxsize of the roomStack:"<<endl;

cin>>N;//这里N将作为栈能存放元素的数量

while(N<=0)

{ cout<<"Oh!You have enter a wrong number,'N' should above 0Please enter another number again:"<<endl;

cin>>N;

} //stack max;

//max->size=maxsize;

char ch1;

stack s1,s2;

queue q;

cinfo x;

int flag;

s1=new stack;

s2=new stack;

q=new queue;

initstack(s1);

initstack(s2);

initqueue(q);

flag=1;

for(;;) {cout<<"Please enter the infomation: 'A'/'D'; car number; car arrival time"<<endl;

cin>>ch1>>xcnum>>xatime;

switch(ch1)

{ case'A':

case'a':carrival(s1,q,x);

break;

case'D':

case'd':carleave(s1,s2,q,x);

break;

case'E':

case'e':flag=0;cout<<"Ok,the system will be shut down!Written by ZIGZ!"<<endl;

break;

default:cout<<"You have enter a wrong!!"<<endl;

}

if(flag==0)

break;

}

}

七、运行结果：

八、经验小结：

通过《停车场管理》的实验学习使我基本上理解并学会了用栈的先进后出和队列的先进先出的原理去解决实际问题的思想和方法。但是在编程方面还是很欠缺，还要加强学习。

以上就是关于用破圈法求最小生成树全部的内容，包括:用破圈法求最小生成树、如何在PB中遍历生成树、图论中最小生成树，用c++编译等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！