-
2021-02-11 17:25:21
G的生成树只有一棵。
16、设G是有n个结点m条边的连通平面图,且有k个面,则k等于:
(1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。
17、设T是一棵树,则T是一个连通且( )图。
答:无简单回路
18、设无向图G有16条边且每个顶点的度数都是2,则图G有( )个顶点。
(1) 10 (2) 4 (3) 8 (4) 16
19、设无向图G有18条边且每个顶点的度数都是3,则图G有( )个顶点。
(1) 10 (2) 4 (3) 8 (4) 12
20、设图G=,V={a,b,c,d,e},E={,,,,},则G是有向图还是无向图?
21、任一有向图中,度数为奇数的结点有( )个。
22、具有6 个顶点,12条边的连通简单平面图中,每个面都是由( )条边围成?
(1) 2 (2) 4 (3) 3 (4) 5
23、在有n个顶点的连通图中,其边数()。
(1) 最多有n-1条(2) 至少有n-1 条
(3) 最多有n条(4) 至少有n 条
24、一棵树有2个2度顶点,1 个3度顶点,3个4度顶点,则其1度顶点为()。
(1) 5 (2) 7 (3) 8 (4) 9
25、若一棵完全二元(叉)树有2n-1个顶点,则它()片树叶。
(1) n (2) 2n (3) n-1 (4) 2
26、下列哪一种图不一定是树()。
(1) 无简单回路的连通图(2) 有n个顶点n-1条边的连通图
(3) 每对顶点间都有通路的图(4) 连通但删去一条边便不连通的图
更多相关内容 -
次小生成树(树剖,生成树)
2020-12-23 12:39:27生成树的概念:在一个无向图中,设顶点数为\(n\),取其中\(n-1\)条边并使所有点相连,所得到的一棵树即为生成树。最小生成树:如果还没有接触过生成树的同学,欢迎戳->最小生成树详解次小生成树:次小生成树...生成树的概念:
在一个无向图中,设顶点数为\(n\),取其中\(n-1\)条边并使所有点相连,所得到的一棵树即为生成树。
最小生成树:
如果还没有接触过生成树的同学,欢迎戳->最小生成树详解
次小生成树:
次小生成树顾名思义,就是边权之和次小的一棵生成树。有严格次小生成树与非严格次小生成树之分。
尽管这个算法的名字叫做次小生成树,不过其实可以理解成一道数据结构
次小生成树可以和次短路径一起理解,有兴趣的同学可以做做模板题
非严格次小生成树的边权之和不一定要比最小生成树的小,即\(Σw\)次≥\(Σw\)最
严格次小生成树的边权之和一定要比最小生成树的小,即\(Σw\)次>\(Σw\)最
想要求出次小生成树?
显然我们可以dfs求出所有的生成树,在排序选出严格次小的就可以了。
但是上述方法显然不能快速求出次小生成树
为了快速的求出来次小生成树,我们需要知道一个结论:次小生成树和最小生成树之间只有一条边的差异。
这一条结论为什么是正确的呢?
我们先来看看\(Kruskal\)是怎么求最小生成树的
\(Kruskal\)是按照边权排序,按照贪心的思路一条一条的加进树边,所以如果要求出次小生成树,那么我们可以放弃一条小的边不选,加入另一条边使图联通。
如果我们"放弃"了两条边,那么只"放弃"一条边的生成树的边权和显然小于"放弃"两条边的生成树的边权和。
所以求出(非)严格次小生成树的朴素算法为:先建立一棵最小生成树。再枚举删去最小生成树上的每一条路径,再在新构成的生成树中选出一棵边权之和最小生成树的即可。
时间复杂度为\(O(nmlogm)\)。当然这种算法还不够优秀,我们可以继续优化
非严格次小生成树我们可以这样优化:
枚举边的时候,枚举没有被并入到最小生成树的边(我们将把这条边加入到生成树中,显然现在的图形不再是一棵树,所以我们要原图中删去一条最大边,使新图仍然联通)
加入边权值为\(W1\)。查询树上每一条的路径,在路径选取一个边权最大值\(W2\)。则当前枚举的答案为\(W−W2+W1\)(W为最小生成树的边权之和)
枚举所有的边之后,取最小值即可。
我们可以用倍增/树剖/LCT来实现查询树上最大值的操作,故复杂度为:\(O(mlogn)\)
再来看看严格次小生成树
不难发现:求非严格最小生成树时,枚举一条边\(W1\),之后再寻找一条生成树上的最大边\(W2\)
显然\(W1≥W2\),因此可能由此得到的次小生成树并非严格。所以我们可以在每次查询时,需要找到严格次小的\(W1\),即\(W1>W2\),这样我们就可以得到严格次小生成树了。
维护仍可以用倍增或者树剖思想。
这里介绍树剖的思路:
先用线段树维护区间最小值与严格次小值,如果是叶子节点最大值就设为他本身,次大值设为0
合并的时候把两个区间的这四个值(两个最大值与两个次大值)排序,再寻找最大值与严格次小值即可。
代码如下:
#include
using namespace std;
#define re register
#define il inline
#define int long long //把所有int转成longlong
#define debug printf("Now is line %d\n",__LINE__);
il int read()
{
re int x=0,f=1;char c=getchar();
while(c'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}//快读
#define maxm 300005
#define inf 12345678900000000
#define maxn 100005
struct Edge{int u,v,w,next;}e[maxm<<1];
struct qj{int ma,ma2;}q[maxn<<2];
struct Edge1
{
int u,v,w;
bool operator
}edge[maxm];
int n,m,vis[maxm],ans=inf,head[maxn],cnt,fa[maxn],mtree;
il void add(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}//前向星加边
namespace smallesttree
{
il int find(int x)
{
while(x!=fa[x]) x=fa[x]=fa[fa[x]];
return x;
}//并查集找祖先
il void init()
{
for(re int i=1;i<=n;i++) fa[i]=i; //预处理并查集
for(re int i=0;i
}
il void kruskal()
{
init();
sort(edge,edge+m);
re int T=0;
for(re int i=0;i
{
re int eu=find(edge[i].u),ev=find(edge[i].v);//寻找祖先
if(eu!=ev)
{
add(edge[i].u,edge[i].v,edge[i].w),add(edge[i].v,edge[i].u,edge[i].w);
mtree+=edge[i].w;//记录子树大小
fa[ev]=eu;//合并
vis[i]=1;//标记该边为树边
if(++T==n-1) break;//边数等于节点数+1即为一颗树
}
}
}
}
//求出最小生成树
namespace treecut
{
int dep[maxn],father[maxn],top[maxn],W[maxn],a[maxn],size[maxn],son[maxn],seg[maxn],col;
//dep:深度 father:父亲节点 top:重链的顶端 W:到根节点的距离 a:点的权值 size:子树大小 son:重儿子 seg:在线段树中的序号(dfs序)
il void dfs1(int u,int fr)
{
dep[u]=dep[fr]+1;
size[u]=1;
father[u]=fr;
for(re int i=head[u];i;i=e[i].next)
{
re int v=e[i].v;
if(v!=fr)
{
W[v]=W[u]+e[i].w;//W为每一个点到根节点的距离
dfs1(v,u);
size[u]+=size[v];
if(size[v]>size[son[u]]) son[u]=v;
}
}
}//预处理出dep、size、father以及son
il void dfs2(int now,int fi)
{
top[now]=fi;
seg[now]=++col;
a[col]=W[now]-W[father[now]];//a为点的权值(它与之父亲节点边的权值)(相当于前缀和)
if(!son[now]) return;
dfs2(son[now],fi);
for(re int i=head[now];i;i=e[i].next)
{
re int v=e[i].v;
if(v!=son[now]&&v!=father[now]) dfs2(v,v);
}
}//预处理出每个节点的top、seg以及权值
//树剖模板就不解释了
#define ls k<<1
#define rs k<<1|1
il bool CMP(int a,int b){return a>b;}
il int getse(int x,int g,int z,int c)
{
re int a[5]={x,g,z,c};
sort(a,a+4,CMP);
for(re int i=1;i<3;++i)
{
if(a[i]!=a[0]) return a[i];
}
}//找到两个区间的最大值和严格次大值(四个数)的最大值与严格次大值
// 就是合并两个区间的最大值和严格次大值
il void build(int k,int l,int r)
{
if(l==r)
{
q[k].ma=a[l];
return;
}
re int mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
q[k].ma=max(q[ls].ma,q[rs].ma);
q[k].ma2=getse(q[ls].ma,q[rs].ma,q[ls].ma2,q[rs].ma2);
}//预处理出区间最大值与次大值
il qj query(int k,int l,int r,int ll,int rr)
{
if(ll>r||rr
if(ll<=l&&rr>=r) return (qj){q[k].ma,q[k].ma2};
re int mid=(l+r)>>1;
re qj t1=query(ls,l,mid,ll,rr),t2=query(rs,mid+1,r,ll,rr);
return (qj){max(t1.ma,t2.ma),getse(t1.ma,t2.ma,t1.ma2,t2.ma2)};
}//查询区间的区间的最大值与次小值
il int LCA(int u,int v,int d)
{
re int need=-inf;
while(top[u]!=top[v])
{
if(dep[top[u]]
qj temp=query(1,1,n,seg[top[u]],seg[u]);
u=father[top[u]];
need=max(need,(temp.ma==d)?temp.ma2:temp.ma);//严格次小边(如果temp.ma==k就是非严格次小)
}
if(dep[u]
qj temp=query(1,1,n,seg[v]+1,seg[u]);
return max(need,(temp.ma==d)?temp.ma2:temp.ma);//同上
}
il void init()
{
dfs1(1,0),dfs2(1,1),build(1,1,n);
}
}
//树链剖分
signed main()
{
n=read(),m=read();
smallesttree::kruskal();//求出最小生成树
treecut::init();//预处理
for(re int i=0;i
{
if(vis[i]) continue;//枚举所有非树边(没有在最小生成树的边)
re int temp=mtree/*最小生成树边权和*/+edge[i].w/*本来的树边的边权*/-treecut::LCA(edge[i].u,edge[i].v,edge[i].w)/*找到严格次小边的边权*/;
if(ans>temp&&temp!=mtree+e[i].w/*其实就是严格此小边不为0(没有找到严格次小边)*/&&temp>mtree) ans=temp;
}
printf("%lld",ans);
return 0;
}
-
图的生成树
2021-02-11 17:25:10定义1 对于无向图G和一棵树T来说,如果T是G的子图,则称T为G的树,如果T是G的生成子图,则称T是G的生成树。定义2 对于一个边上具有权值的图来说,其边权值和最小的生成树称做图G的最小生成树。定理1 对于一个图G,...定义1 对于无向图G和一棵树T来说,如果T是G的子图,则称T为G的树,如果T是G的生成子图,则称T是G的生成树。
定义2 对于一个边上具有权值的图来说,其边权值和最小的生成树称做图G的最小生成树。
定理1 对于一个图G,如果图中的边权值都不相同,则图的最小生成树唯一。
最小生成树
求无向图的最小生成树主要有Prim算法和Kruskal算法。
1.Prim算法
(1)基本算法
将图G中的所有点V分成两个顶点集合Va和Vb。在计算过程中Va中的点为已经选好连接入生成树的点,否则属于Vb。最开始的时候Va包含任意选取的图G中的一个点u,其余的点属于Vb,算法结束时所有与u连通的点属于Va,其余的点仍留在Vb中。如果算法结束时Vb不为空,说明图G的生成树不存在,只存在生成森林。
代码如下:
1 //直接实现,邻接矩阵存储图
2 const int maxn=101;3 void Prim(int n,int dist[maxn],int map[maxn][maxn],intpre[maxn])4 //n个点,dist[i]表示向外延伸的最短边长,map记录图信息,pre[]记录连接信息,5 //dist之和最最小权值
6 {7 inti,j,k;8 intmin;9 bool p[maxn];//记录该点是否属于Va
10 for(i=2;i<=n;i++)11 {12 p[i]=false;13 dist[i]=map[1][i];14 pre[i]=1;15 }16 dist[1]=0;17 p[1]=true;18 for(i=1;i<=n-1;i++)//循环n-1次,每次加入一个点
19 {20 min=INT_MAX;21 k=0;22 for(j=1;j<=n;j++)23 {24 if(!p[j]&&dist[j]
31 p[k]=true;32 for(j=1;j<=n;j++)33 {34 if(!p[j]&&map[k][j]!=INT_MAX&&dist[j]>map[k][j])35 {36 dist[j]=map[k][j];37 pre[j]=k;38 }39 }40 }41 }42 //时间复杂度O(n^2);43
44 //堆实现
45 /*使用堆来保存Vb中每一点到Va中所有点的最短边长并维护其最小值,46 并在访问每条边的时候更新。先将所有的点插入堆,并将值赋为inf,47 将根赋值为0,通过松弛技术进行更新。*/
48 //堆
49 structHeapElement50 {51 intkey,value;52 };53 structMinHeap54 {55 HeapElement H[maxn];56 intsize;57 intposition[maxn];58 void init(){H[size=0].value=-INF;}59 void ins(int key,intvalue)60 void decrease(int key,intvalue)61 voiddelmin()62 }H;63 //边
64 structedge65 {66 intto,w,next;67 }edge[maxm];68 intN,M;69 long longdist[maxn];70 inthead[maxn];71 voidPrim()72 {73 inti,j,k;74 bool p[maxn]={0};75 H.init(true);76 for(i=1;i<=N;i++)77 {78 H.ins(i,INF);79 dist[i]=INF;80 }81 dist[1]=0;82 H.decrease(1,0);83 for(i=1;;)84 {85 p[i]=true;86 H.delmin();//删除堆顶元素
87 for(k=head[i];k!=-1;k=edge[k].next)88 {89 if(!p[j]&&edge[k].w
97 else break;98 }99 }100
101 /*用堆优化的Prim算法主要用于加速变较少的图的最小生成树的计算,特别是稀疏图。102 总的时间复杂度是O((n+m)log n).当边较少时,这种算法相对直接实现的Prim算法来说103 有很好的效果。*/
View Code
2.Kruskal算法
Kruskal算法基于贪心的思想,对于图G={V,E},先构造G‘={V,Ø},然后依次向G’中添加E中未添加过的权值最小的边,如果这条边加入G‘中存在环,则去掉这条边,直到G’成为一棵树。
具体步骤:
①首先初始化,生成图G‘,并将E中的边按权值排序。
②从最小的边开始尝试加入到图G’中,如果当前便加入后存在环,则弃掉当前边,否则标记当前边并计数。
③遍历所有边后,如果选择的边数等于n-1,则生成最小生成树,计算步骤②所选择的边的权值之和,否则最小生成树不存在,只存在最小生成森林,但是Kruskal算法不需要反复运行,当前结果就是图G的最小生成森林。
算法的关键在于如何判断新加入的边会使图G‘产生环,这里使用并查集,并查集中的一个等价类代表图G’中的一个连通分量,也就是一棵树,如果新加入边的两端在并查集的一个等价类中,说明存在环,需要舍掉这条边;否则保留当前边,并合并涉及的两个等价类。
代码如下:
1 //并查集
2 const in maxn=1010;3 intUFSTree[maxn];4 int find(intx);5 void merge(int x,inty)6 //Kruskal
7 const int maxm=100010;8 structnode9 {10 int a,b;//边的起点和终点
11 intw;12 bool select;13 }edge[maxm];14 boolcmp(node a,node b)15 {16 if(a.w!=b.w)return a.w
28 x=find(edge[i].a);29 y=find(edge[i].b);30 if(x!=y)31 {32 merge(x,y);33 k++;34 edge[i].select=true;35 }36 }37 }
View Code
时间复杂度为O(mlog m + m),即主要的时间都花在边的排序上了。个人觉得该算法好理解、好操作。
次小生成树
次小生成树的边的权值和可能等于最小生成树的权值和,或者略大。
定义1 设G={V,E}是连通的无向图,T是图G的一棵最小生成树。如果有另一棵树T1,T1≠T,满足不存在T‘,T’≠T,w(T')
定理1 存在边(u,v) ∈T和(x,y)不属于T满足T\(u,v)U(x,y)是图的一棵次小生成树。
基于定理1,那么所有的T\(u,v)U(x,y)刚好构成了T的邻集,则T的邻集中权值最小的就是次小生成树了。(定义由最小生成树T进行一次可行交换得到的新的生成树所组成的集合,称为树T的邻集,记为N(T)。所谓的可行交换即去掉T中的一条边,再新加入图G中的一条边,使得新生成的图仍为树。)
效率较高的做法是先加入(x,y),对于一棵树,加入(x,y)后一定成为环,如果删去环上除(x,y)以外的最大的一条边,会得到加入(x,y)时权值最小的一棵树。如果能够快速计算最小生成树中点x到y之间路径中最长边的长度,这个问题就能很好地解决。最小生成树中x到y的最长边可以使用树形动态规划或者LCA等方法在O(n^2)的时间复杂度内算出。如果使用Kruskal算法求最小生成树,可以在算法的运行过程中求出x到y路径上的最长边,因为每次合并两个等价类的时候,分别属于两个等价类的两个点间的最长边一定是当前加入的,按照这条性质记录的话就可以求出所有值了。为了便于合并时的修改,需要记录每个集合都有哪些点,可以写一个类似邻接表的数据结构,将以i为代表元的集合的所有点作为i的邻接点进行存储。
具体实现如下:
在Kruskal算法的基础上进行修改,加入对x,y两点在最小生成树上路径中最长边的计算,存入length[][]数组。使用链式前向星记录每个集合都有哪些点。为了合并方便,除了head[]记录每条邻接表的头结点位置外,end[]记录每条邻接表尾节点的位置便于两条邻接表合并。mst为最小生成树的大小,secmst为次小生成树的大小。
代码如下:
1 //并查集
2 const in maxn=1010;3 intUFSTree[maxn];4 int find(intx);5 void merge(int x,inty)6 //Kruskal
7 const int maxm=100010;8 structnode9 {10 int a,b;//边的起点和终点
11 intw;12 bool select;13 }edge[maxm];14 boolcmp(node a,node b)15 {16 if(a.w!=b.w)return a.w
21 structnode122 {23 intto,next;24 };25 node1 link[maxn];//边数组,注意这里是maxn,而不是maxm,是类似的链式前向星
26 int il;//边数组中数据的个数
27 int head[maxn];//邻接表的头结点位置
28 int end[maxn];//邻接表的尾节点位置
29 int length[maxn][maxn];//每两点在最小生成树上路径中最长边长
30
31 void Kruskal(node *edge,int n,intm)32 {33 int k=0;34 inti,x,y;35 //初始化邻接表,对于每个节点添加一条指向其自身的边,表示以i为代表元的集合只有i
36 for(il=0;il
47 if(edge[i].w<0)continue;48 x=find(edge[i].a);49 y=find(edge[i].b);50 if(x!=y)51 {52 //修改部分,遍历两个节点所在的集合
53 for(w=head[x];w!=-1;w=link[w].next)54 {55 for(v=head[y];v!=-1;v=link[v].next)56 {57 int pp=link[w].to,qq=link[v].to;58 length[pp][qq]=length[qq][pp]=edge[i].w;59 }60 }61 link[end[y]].next=head[x];62 end[y]=end[x];63 merge(x,y);64 k++;65 edge[i].select=true;66 }67 }68 }69
70 intmain()71 {72 //先初始化和建图,然后进行下面的操作
73 intmst,secmst;74 Kruskal(edge,n,m);75 mst=0;76 for(i=1;i<=m;i++)77 {78 if(edge[i].select)mst+=edge[i].w;79 }80 secmst=INF;81 for(i=1;i<=m;i++)82 {83 if(!edge[i].select)secmst=min(secmst,mst+
84 edge[i].w-length[edge[i].a][edge[i].b]);85 }86 }
View Code
整个算法运行了一次Kruskal算法,时间复杂度是O(mlogm),同时又对整个length[][]进行赋值,时间复杂度O(n^2),最终又进行了时间复杂度为O(m)的遍历,所以总的时间复杂度为O(mlogm+n^2)。
有向图的最小树形图
首先看一个例子,有一处水源给附近的菜地供水,在没有抽水机的情况下,水只能从高处流向低处,每修一条水渠都有一定的花费,问怎样修才能使花费最低。考虑到水的流向,要求生成的最小生成树必须以水源为根,而且需要能够由根到达所有的节点。这就是最小树形图问题。
定义1 最小树形图的定义:
设G=(V,E)是一个有向图,如果具有以下性质:
(1)G中不包含有向环;
(2)存在一个顶点Vi,他不是任何弧的终点,而V的其他顶点都恰好是唯一的一条弧的终点。则称G是以Vi为根的树形图。
基本算法:
最小树形图基于贪心的思想和缩点的思想。所谓缩点,就是将几个点看成一个点,所有连接到这几个点的边都视为连到收缩点,所以从这几个点连出的边都被视为从收缩点连出。
下面根节点取为V0.
(1)求最短弧集合E0
从所有以Vi(i!=0)为终点的弧中去一条最短的,若对于点Vi,没有入边,则不存在最小树形图,算法结束;如果能取,则得到由n个点和n-1条边组成的图G的一个子图G‘,该子图的权值一定是最小的,但是不一定是一棵树。
(2)检查E0
若E0没有有向环且不含收缩点,则计算结束,E0就是G的以V0为根的最小树形图。若E0没有有向环、但含收缩点,则转步骤(4),若E0含有有向环,则转入步骤(3)。
(3)收缩G中的有向环
把G中的C收缩成点u,对于图G中两端都属于C的边被收缩掉了,其他弧扔保留,得到一个新的图G1,G1中以收缩点为终点的弧的长度要变化,变化的规律是:设点v在环C中,且环中指向v的边长为w,点v'不在环C中,则对于每条边与其对应,且权重为w()-w;对于图G中以环C为起点的边,在图G1中有边,权重为w()。在此步生成的图G1中可能存在重边。
对于图G和图G1:
①如果图G1中没有以V0为根的最小树形图,则图G也没有。
②如果图G1中有以V0为根的最小树形图,则可以按照步骤(4)的展开方法得到图G的最小树形图。
因此,此时需要将G1带入步骤(1)做为图G继续进行计算,反复计算直到图G1的最小树形图求出。
(4)展开收缩点
如果图G1的最小树形图T1已经求出,那么所有T1的弧都属于T。将图G1的一个收缩点u展开成环C,从C中去掉与T1中有相同终点的弧,其他弧都属于T。
在计算的过程中可以发现,图Gi与图Gi-1的最小树形图的权值差正好是被缩掉的环的权值和,在这种性质的影响下,如果不需要知道最终的T0中到底需要那几条边,只需要知道T0的权值时,可以不需要展开。
下面给出只是求权值的代码:
1 double zhuliu(int n,doublemap[maxn][maxn])2 {3 boolvis[maxn];4 bool flag[maxn];//缩点标记为true,则该点已经被收缩,否则仍然存在
5 intpre[maxn];6 double sum=0;7 inti,j,k;8 for(i=0;i
17 for(i=1;i
26 for(i=1;i
30 for(j=0;j
34 {35 vis[j]=true;36 j=pre[j];37 }while(!vis[j]);38 if(!j)continue;//没有找到环
39 i=j;40 //将整个环的权值保存,累计入原图的最小树形图
41 do
42 {43 sum+=map[pre[j]][j];44 j=pre[j];45 }while(j!=i);46 j=i;47 //对与环上的点有关的边,修改边权
48 do
49 {50 for(k=0;k
56 for(j=0;j
66 for(j=pre[i];j!=i;j=pre[j])flag[j]=true;67 //当前环缩点结束,形成新的图G‘,跳出继续求G’的最小树形图
68 break;69 }70 //如果所有的点都被检查,且没有环存在,71 //现在的最短弧集合E0就是最小树形图,累计入sum,算法结束
72 if(i==n)73 {74 for(i=1;i
View Code
时间复杂度为O(n^3)。
参考文献《图论及应用》哈尔滨工业大学出版社
特此申明:严禁转载
2014-02-19
-
python通过递归来创作一棵树
2020-12-21 10:35:17在这里我们要使用到一个简单的有关画图的模块——turtle 下面是turtle的常用函数: 上面的太长了你也可以选择不看,因为我们只用到一些简单的函数。 简单介绍一下turtle模块,这个模块叫做海龟作图,就是模拟海龟... -
har2tree:从 HAR 文件制作一棵树
2021-07-23 16:57:41哈2树 这个包从 HAR 转储生成一棵树。 安装 pip install har2tree -
生成树算法
2021-06-28 09:03:04在图论的数学领域中,如果连通图G的一个子图是一棵包含G的所有顶点的树,则该子图称为G的生成树(SpanningTree)。生成树是连通图的包含图中的所有顶点的极小连通子图。图的生成树不惟一。从不同的顶点出发进行遍历,...在图论的数学领域中,如果连通图G的一个子图是一棵包含G的所有顶点的树,则该子图称为G的生成树(SpanningTree)。生成树是连通图的包含图中的所有顶点的极小连通子图。图的生成树不惟一。从不同的顶点出发进行遍历,可以得到不同的生成树。
常用的生成树算法有DFS生成树、BFS生成树、PRIM 最小生成树和Kruskal最小生成树算法。
中文名
生成树算法
外文名
Spanning tree algorithm
归属学科
图论包 括
DFS、BFS、最小生成树
图的生成树
不惟一
应 用
自动控制
生成树算法自由树
编辑
语音
自由树就是一个无回路的连通图(没有确定根)(在自由树中选定一顶点做根,则成为一棵通常的树)。从根开始,为每个顶点(在树中通常称作结点)的孩子规定从左到右的次序,则它就成为一棵有序树。在图的应用中,我们常常需要求给定图的一个子图,使该子图是一棵树。
生成树算法生成树
编辑
语音
在图论中,如果连通图
的一个子图是一棵包含
的所有顶点的树,则该子图称为G的生成树(SpanningTree)。
生成树是连通图的包含图中的所有顶点的极小连通子图。
图的生成树不惟一。从不同的顶点出发进行遍历,可以得到不同的生成树。
通用定义:
若从图的某顶点出发,可以系统地访问到图中所有顶点,则遍历时经过的边和图的所有顶点所构成的子图,称作该图的生成树。
(1)若G是强连通的有向图,则从其中任一顶点v出发,都可以访问遍G中的所有顶点,从而得到以v为根的生成树。
(2)若G是有根的有向图,设根为v,则从根v出发可以完成对G的遍历,得到G的以v为根的生成树。
(3)若G是非连通的无向图,则要若干次从外部调用DFS(或BFS)算法,才能完成对G的遍历。每一次外部调用,只能访问到G的一个连通分量的顶点集,这些顶点和遍历时所经过的边构成了该连通分量的一棵DFS(或BPS)生成树。G的各个连通分量的DFS(或BFS)生成树组成了G的DFS(或BFS)生成森林。
(4)若G是非强连通的有向图,且源点又不是有向图的根,则遍历时一般也只能得到该有向图的生成森林。
生成树算法分类
编辑
语音
1)生成树的求解方法
设图
是一个具有n个顶点的连通图。则从G的任一顶点(源点)出发,作一次深度优先搜索(广度优先搜索),搜索到的n个顶点和搜索过程中从一个已访问过的顶点
搜索到一个未曾访问过的邻接点
,所经过的边
(共n-1条)组成的极小连通子图就是生成树。(源点是生成树的根)
通常,由深度优先搜索得到的生成树称为深度优先生成树,简称为DFS生成树;由广度优先搜索得到的生成树称为广度优先生成树,简称为BFS生成树。
注意:
①图的广度优先生成树的树高不会超过该图其它生成树的高度
②图的生成树不惟一,从不同的顶点出发进行遍历,可以得到不同的生成树。
生成树算法最小生成树
编辑
语音
对于连通的带权图(连通网)G,其生成树也是带权的。生成树T各边的权值总和称为该树的权,记作:
其中,TE表示T的边集,w(u,v)表示边(u,v)的权。权最小的生成树称为G的最小生成树(Minimum SpannirngTree)。最小生成树可简记为MST。[1]
普里姆(PRIM)算法
算法简单描述
1)输入:一个加权连通图,其中顶点集合为V,边集合为E;
2)初始化:Vnew= {x},其中x为集合V中的任一节点(起始点),Enew= {},为空;
3)重复下列操作,直到Vnew= V:
a. 在集合E中选取权值最小的边,其中u为集合Vnew中的元素,而v不在Vnew集合当中,并且v∈V(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一);
b. 将v加入集合Vnew中,将边加入集合Enew中;
4)输出:使用集合Vnew和Enew来描述所得到的最小生成树。[2]
伪代码描述PrimMST(G,T,r)
{
//求图G的以r为根的MST,结果放在T=(U,TE)中
InitCandidateSet(…);//初始化:设置初始的轻边候选集,并置T=({r},¢)
for(k=0;k
{
//求T的n-1条树边
(u,v)=SelectLiShtEdge(…);//选取轻边(u,v);
T←T∪{(u,v)
};
//扩充T,即(u,v)涂红加入TE,蓝点v并人红点集U
ModifyCandidateSet(…);
//根据新红点v调整候选轻边集
}
}
用普里姆算法构造最小生成树的过程
克鲁斯卡尔(Kruskal) 算法
Kruskal算法是基于贪心的思想得到的。首先我们把所有的边按照权值先从小到大排列,接着按照顺序选取每条边,如果这条边的两个端点不属于同一集合,那么就将它们合并,直到所有的点都属于同一个集合为止。至于怎么合并到一个集合,那么这里我们就可以用到一个工具——-并查集。换而言之,Kruskal算法就是基于并查集的贪心算法。
算法流程:
输入:图G
输出:图G的最小生成树
具体流程:
1)将图G看做一个森林,每个顶点为一棵独立的树
2)将所有的边加入集合S,即一开始S=E
3)从S中拿出一条最短的边(u,v),如果(u,v)不在同一棵树内,则连接u,v合并这两棵树,同时将(u,v)加入生成树的边集E'
4)重复(3)直到所有点属于同一棵树,边集E'就是一棵最小生成树
时间复杂度:
Kruskal算法每次要从都要从剩余的边中选取一个最小的边。通常我们要先对边按权值从小到大排序,这一步的时间复杂度为为O(|Elog|E|)。Kruskal算法的实现通常使用并查集,来快速判断两个顶点是否属于同一个集合。最坏的情况可能要枚举完所有的边,此时要循环|E|次,所以这一步的时间复杂度为O(|E|α(V)),其中α为Ackermann函数,其增长非常慢,我们可以视为常数。所以Kruskal算法的时间复杂度为O(|Elog|E|)。
Kruskal算法构造最小生成树的过程
生成树算法应用
编辑
语音
网络G表示n各城市之间的通信线路网线路(其中顶点表示城市,边表示两个城市之间的通信线路,边上的权值表示线路的长度或造价。可通过求该网络的最小生成树达到求解通信线路或总代价最小的最佳方案。参考资料
1.
Gower J C, Ross G J S. Minimum Spanning Trees and Single Linkage Cluster Analysis[J]. Journal of the Royal Statistical Society, 1969, 18(1):54-64.
2.
江波, 张黎, JIANGBo,等. 基于Prim算法的最小生成树优化研究[J]. 计算机工程与设计, 2009, 30(13):3244-3247.
-
最小生成树个数
2017-02-02 15:49:10在存在权值相等的边时,最小生成树可能有多个。话不多说,求它个数的方法如下:先用Prim生成最小树,同时记录边的关系。用并查集表示//不要压缩路径让每个元素都指向它的父亲节点。找出权值相同的边,去除树上的这条... -
数据结构-图的生成树问题
2019-08-28 10:53:23一、无向图的连通分量和生成树 若图是连通的或强连通的,则从图中某一个顶点出发可以访问到图中所有顶点; 若图是非连通的或非强连通图,则需从图中多个顶点出发搜索访问。而每一次从一个新的起始点出发进行搜索过程... -
数据结构题
2021-02-11 17:25:19设无向图的顶点个数为n,则该图最多有( )条边。A.n-1 B.n(n-1)/2 C. n(n+1)/2 D.0 E.n23.一个n个顶点的连通无向图,其边的个数至少为( )。A.n-1 B.n C.n+1 D.nlogn;4.要连通具有... -
生成树原来这么简单
2020-07-14 12:33:08生成树原来这么简单 文章目录生成树原来这么简单前言摘要什么是生成树?生成树的作用?一、STP1.1 背景1.2 STP增强特性1.2.1 portfast 端口加速1.2.2 backbonefast 骨干加速1.2.3 uplinkfast 上行链路加速1.2.4 BPDU... -
第七章 树 7.1 无向树及生成树
2020-01-01 16:49:117.1 无向树及生成树 先来看一些基本概念: 简单来说就是由多颗数组成的。 来看一些定理: 如果我们让树中的每一条与其下方的结点对应,那么最后多出来一个根节点。故在树中,边数等于结点数减去1。 定理2: 例题... -
几分钟搞明白生成树和最小生成树的定义
2017-11-15 07:57:53注意文字意思:不管是生成树还是最小生成树一定还是输,千万别和图...注意形成的一定是一棵树才是生成树。好了回到正题: 那么我们的生成树怎么在图的基础上生成的呢? 我们学了图应该知道有2种遍历方法:1深度优先 -
一行代码生成一棵圣诞树
2020-06-26 23:17:07一行代码生成一棵圣诞树Python 字符串这块可以玩出很多有意思的功能,今天我以一个精简的字符串打印为例来展示。一棵小树print('*'.rjust(3),'*... -
java 递归 生成树
2018-01-11 16:48:46我的想法是,数据库中存的不一定是一棵树,也就是说最顶级的父节点不止一个。 那就好办了: 1 先读取数据库中的所有数据存放到treeNodeList中。 2 然后遍历list,将其中的最顶级的父节点存到另一个list ---father... -
连通网的最小生成树
2021-12-01 17:16:25这个子图包含有图中全部的n个顶点,但是只有足以构成一棵树的n-1条边,称这样的子图叫做极小连通子图,而构成的这棵树称为连通图的生成树。由于原来的图中每条边/弧上有对应的权值,所以生成的这棵树中权值和随着 n-... -
生成树与快速生成树(STP、RSTP)原理
2018-09-22 20:34:38表面上看生成树的作用是做设备冗余时,防止成环的一种途径,但实际上可以避免做生成树,使用堆叠技术和虚拟化技术来达到防止出现环路的作用(将两个设备做成一个设备,使得整个拓扑还是一个树状结构),所以生成树并... -
最小生成树的构造
2019-11-06 16:13:18一个图的生成树不只一个,权(各边权值之和)最小的生成树则为此图最小生成树 最小生成树具有以下特性: 1、最小生成树形状不唯一,但最小生成树权是唯一的。且为所有生成树中最小的 2、最小生成树边数为顶点数减1 3、... -
最小代价生成树算法
2021-07-27 12:18:41然后,把一条最小代价的边(u,v)加入T中,使T ∪ {(u,v)}仍是一棵树。重复上述加入边的过程指导T中包含了n-1条边为止。为了保证所加入的边不形成环路,要求在每一步所选取的边(u,v)的两个顶点u和v,只能有一个顶点在T... -
生成树协议(三)
2020-09-07 16:30:35STP和RSTP还存在同一个缺陷:由于局域网内所有Vlan共享一棵生成树,因此无法在Vlan间实现数据流量的负载均衡,链路被阻塞后将不承载任何流量,还有可能造成部分Vlan的报文无法转发。 如图所示网络中,生成树结构在... -
数据结构与算法—最小生成树(Prim算法和Kruskal算法算法详解)
2019-10-05 12:28:31在图论中,最小生成树也是一种常用算法,本文将从一些有趣的例子和来讲诉最小生成树的prim算法和kruskal算法。中间也夹杂了马克思主义理论,! -
加权无向图与最小生成树(Prim算法和Kruskal算法)
2020-12-07 16:54:27图的生成树:图的生成树是它的一个含有其所有顶点的无环连通子图。 图的最小生成树:图的权值(所有边的权重之和)最小的生成树。 约定:最小生成树只存在于连通图中,如果图不是连通的,那么分别计算每个连通子图... -
生成树
2019-08-23 11:53:25Spanning tree 交换机之间存在冗余路径,以及交换机的泛洪机制,导致交换机之间产生二层交换环路 造成影响:1.广播风暴(环路) 2.MAC地址表不稳定 3.数据帧的重复拷贝 解决方案:逻辑性阻塞...一、生成树类型 公... -
MSTP(多区域生成树协议)
2020-11-19 21:16:03802.1s中定义的生成树协议,通过生成多个生成树,来解决以太网环路问题。 目的: 在以太网中部署MSTP协议后可实现如下功能: 形成多棵无环路的树,解决广播风暴并实现冗余备份。 多棵生成树在VLAN间实现负载均衡,... -
带你理解最小生成树的生成
2020-09-03 11:14:18一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。最小生成树(Minimum Spanning Tree,MST)可以用kruskal(克鲁斯卡尔)算法或prim(普里姆)算法... -
最小生成树的三种算法及图的相关知识
2018-06-01 21:18:43先介绍几个关于图的几个概念定义: 连通图:在无向图中,若任意两个顶点vi与vj都有路径相通,则称该无向图为连通图。 强连通图:在有向图中,若任意两个顶点vi与vj都有路径相通,则称该有向图为强连通图... -
最小生成树
2014-07-20 07:48:43c,数据结构,图,最小生成树,算法 -
生成树和最小生成树
2018-03-13 15:29:22一、生成树的概念 一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有构成一棵树的(n-1)条边。如果在一棵生成树上添加一条边,必定构成一个环。一棵有n个顶点的生成树(连通无回路图)有且仅有(n-1)... -
生成句法分析树以及从一个小例子来看词义消歧及语义角色标注
2018-07-09 12:14:40一、生成句法分析树把一句话按照句法逻辑组织成一棵树,由人来做这件事是可行的,但是由机器来实现是不可思议的,然而算法世界就是这么神奇,把一个十分复杂的过程抽象成仅仅几步操作,甚至不足10行代码,就能让机器... -
克鲁斯卡尔算法生成最小生成树
2020-02-22 17:05:233)具体做法:首先构造一个只含 n个顶点的森林,然后依权值从小到大从连通网中选择边加入到森林中,并使森林中不产生回路,直至森林变成一棵树为止 首先我们得明白,在解决求最小生成树的算法里,主要就是克鲁斯...