精华内容
下载资源
问答
  • 2019-04-17 19:30:38

    摘要

    在图论的数学领域中,如果连通图 G的一个子图是一棵包含G 的所有顶点的树,则该子图称为G的生成树(SpanningTree)。生成树是连通图的包含图中的所有顶点的极小连通子图。图的生成树不惟一。从不同的顶点出发进行遍历,可以得到不同的生成树(来自百度百科)

    算法思想

    任意选择一条有向边,记录此边的顶点集合S,删除集合S中各顶点之间的所有有向边,在新的矩阵中寻找与集合S中顶点相关联的有向边,选择其中一条有向边,将其顶点保存到S中,删除该边,删除集合S中各顶点之间的所有有向边,重复以上过程直到S中包含所有的顶点。

    程序的参数说明

    W表示图的邻接矩阵。
    W1表示所生成树的邻接矩阵

    MATLAB实现

    function W1 = treedgraf(W)
    
    n = size(W,1);
    W1 = zeros(n,n);
    C = zeros(1,n);
    a = find(W ~= 0);
    t2 = mod(a(1), n);
    if t2 == 0
        t2 = n;
    end
    C(1) = t2;
    for i = 1:(n - 1);
        a = find(W(C(1:i),:) ~= 0);
        if a(1) / i > floor(a(1) / i)
            t = floor(a(1) / i) + 1;
        else
            t = floor(a(1) / i);
        end
        t1 = mod(a(1), i);
        if t1 == 0
            t1 = i;
        end
        W1(C(t1),t) = 1;
        C(i+1) = t;
        W(C(1:(i+1)),C(1:(i+1))) = 0;
    end
    

    测试

    测试用例:W =

     0     1     1     1     0     0
     0     0     1     0     0     0
     0     0     0     0     1     1
     0     0     0     0     0     1
     0     0     0     0     0     0
     0     0     0     0     0     0
    

    测试结果:W1 =

     0     1     1     1     0     0
     0     0     0     0     0     0
     0     0     0     0     1     1
     0     0     0     0     0     0
     0     0     0     0     0     0
     0     0     0     0     0     0
    

    更多相关内容
  • 有向图转化为最小生成,在交通系统建模中运用广泛
  • 最小生成 经典算法Kruskal算法 int cmp(const node &c,const node &d) { return c.z<d.z; } int find(int x) //路径压缩(没有按秩合并)的并查集 { if (fa[x]!=x) fa[x]=find(fa...

    最小生成树

    经典算法Kruskal算法

    int cmp(const node &c,const node &d)
    {
        return c.z<d.z;
    }
    
    int find(int x)           //路径压缩(没有按秩合并)的并查集
    {
        if (fa[x]!=x)
           fa[x]=find(fa[x]);
        return fa[x];
    }
    
    int unionn(int f1,int f2)
    {
        fa[f1]=f2;
    }
    
    int doit()
    {
        int i,j=0;
        int tot=0;
        for (i=1;i<=m;i++)
        {
            int r1=find(way[i].u);
            int r2=find(way[i].v);
            if (r1!=r2)
            {
                tot+=way[i].z;
                unionn(r1,r2);
                j++;
            }
            if (j==n-1) break;
        }
        return tot;
    }
    
    void Kruskal()
    {
        sort(way+1,way+1+m,cmp);
        int size=doit(); 
    }

    这里不得不提一句什么叫

    Kruskal重构树

    例题
    简单的代码讲解

    Kruskal重构树可以拿来处理一些最小生成树的边权最值问题
    形象的理解就是:
    Kruskal连边时并不直接合并两个并查集
    而是新建一个节点x
    将两个点所在子树都连到x的儿子上

    这样生成的树有一些十分优美的性质:

    1.二叉树(好吧意义不大)
    2.原树与新树两点间路径上边权(点权)的最大值相等
    3.子节点的边权小于等于父亲节点(大根堆)
    4.原树中两点之间路径上边权的最大值等于新树上两点的LCA的点权

    看图理解一下吧
    这里写图片描述

    看一下性质的体现:
    1.不用说了
    2.原树上2—>5:2,新树上也是
    3.不用说了
    4.1—>6:4
    确认满足性质

    看一下Kruskal重构树的构建:

    维护一个类似并查集的东西

    其中有按秩合并和路径压缩
    据说这样并查集的时间复杂度才有保证

    树的记录方式:爸爸记录法(只记录父亲
    没有必要把树上的边都连起来
    结点深度只要调用一个记忆化搜索就好了
    (代码还是很丑)

    int cmp(const node &a,const node &b)
    {
        return a.v<b.v;
    }
    
    int find(int a)  //路径压缩 
    {
        if (fa[a]!=a) fa[a]=find(fa[a]);
        return fa[a];
    }
    
    void kruskal()
    {
        sort(e+1,e+1+m,cmp);
        int i,o=0;
        for (int i=1;i<=n;i++) fa[i]=i,size[i]=1;
        for (i=1;i<=m;i++)
        {
            int f1=find(e[i].x);
            int f2=find(e[i].y);
            if (f1!=f2)
            {
                if (size[f1]>size[f2]) swap(f1,f2);  //按秩合并 
                fa[f1]=f2;                           //并查集中的标志节点,f1连到f2上 
                size[f2]=max(size[f2],size[f1]+1);   //size并查集的深度 
                f[f1]=f2;                            //Kruskal重构树中的父节点 
                z[f1]=e[i].v;                        //Kruskal重构树中的结点值(就是原树中的边值) 
            }
        }
    }
    
    int getdep(int bh)
    {
        if (deep[bh]) return deep[bh];
        if (!f[bh]) return deep[bh]=1;
        return deep[bh]=getdep(f[bh])+1;
    }

    言归正传

    为了更好地理解最小生成树,
    我们给出两条性质:

    性质一:切割性质
    假定所有的边权均不相同
    设S为既非空集也非全集的V(点集)的子集,
    边e是满足一个端点在S内,另一个端点不在S内的所有边中权值最小的边
    则图G的所有生成树均包含e


    性质二:回路性质
    假定所有的边权均不同
    设C是图G中的任意回路,边e是C上权值最大的边,
    则图G的所有生成树不包含e

    例1:

    每对结点间的最小瓶颈路上的最大边长

    解:
    求出最小生成树之后:
    一般来说,最朴素的用lca(n^2logn)
    然而现在有了更好的做法:
    用dfs把最小生成树变成有根树,同时计算f(u,v)
    当新访问一个结点的时候,考虑所有访问过的老结点
    更新f(x,u)=max(f(x,v),w(u,v)),其中v是u的父结点
    复杂度O(n^2)

    次小生成树

    权值之和排在第二的生成树

    最朴素的求法:像次短路一样,次小生成树和最小生成树不会完全一样,
    我们枚举最小生成树上的边并删除,在剩下的边里做Kruskal,得到的生成树中权值最小的就是次小生成树
    复杂度O(nmα(n,m))

    还有一种更好的方法

    枚举要加入哪条新边
    在最小生成树上加上一条边u-v,图上会出现一条回路,我们需要删除一条边
    所以删除的边一定在最小生成树中u-v的路径上
    回路性质得,删除的一定是路上的一条最长边
    所以我们像例一中一样,求出f(u,v)
    剩下的部分只需要O(m)的时间(枚举所有m-n+1条边,O(1)求出新生成树的权值)
    时间复杂度O(n^2)

    有向最小生成树

    给定一个有向带权图G和其中一个结点u,找到一个以u为根结点,权和最小的生成树
    有向生成树(directed spanning tree)也叫树形图(arborescence)
    是指一个类似树的有向图,满足如下条件

    • 恰好有一个入度为0的结点,称为根结点
    • 其他结点的入度均为一
    • 可以从根节点到达所有其他结点

    朱-刘算法

    首先是预处理:
    删除自环判断根结点是否可以到达其他结点,如果不是,无解

    算法主过程:
    首先,给所有非根结点选择一条全最小的入边,
    如果选出来的n-1条边构不成圈,则可以证明这些边形成了一个最小树形图
    否则把每个圈缩成一个点,继续上述过程

    缩圈之后,圈上的所有边都消失了,因此在最终答案的时候需要累加上这些边的权值
    但是这样就有一个问题:
    假设算法在某次迭代中,把圈C缩成了结点v
    则下一次迭代的时候,给v选择的入边将与C中的入弧冲突
    这里写图片描述
    如图,圈中已经有了Y—>X,如果收缩之后我们又给X选了一条入边Z—>X
    我们就要删除Y—>X(每个非根结点只有一个入度)
    这等价于把弧Z—>X减小了Y—>X的权值

    展开全文
  • 有向图 G=(V, E) 的拓扑排序

    千次阅读 2020-08-13 20:55:21
    拓扑排序是有向图中全部顶点的一种线性排序,只有有向图中入度0的顶点才能成为拓扑排序的第一个顶点,不断重复地寻找入度0的顶点,即可得到拓扑排序结果,具体方法可以通过深度优先搜索或广度优先搜索来解决有向...

    有向图 G = ( V , E ) G=(V,E) G=(V,E) 的拓扑排序

    拓扑排序概念

    拓扑排序是针对有向图而言的,无向图中不存在拓扑排序的概念。所谓拓扑排序,即为有向图中全部顶点的一种线性排序。这个线性排序结果需要满足一定的条件,即对于有向图中的任意两个顶点 u u u v v v,若图中存在有向边 u → v u \rightarrow v uv,则在拓扑排序结果中顶点 u u u一定位于 v v v的前面。

    那么,由拓扑排序的概念可以推出,只有有向图中入度为0的顶点才能成为拓扑排序的第一个顶点。这个原则也是解决有向图拓扑排序的一个指导性原则。

    A O V AOV AOV网络

    由于存在一些概念上的联系,这里简单插入介绍一下 A O V AOV AOV网络的概念。
    Activity On Vertex Network,顶点表示活动,边表示活动间的先后关系的网络图。拓扑排序是对 A O V AOV AOV网络的一种简化或者调度活动的执行顺序的过程。

    由于网络中,不同的活动之间可能存在相互依赖,因此拓扑排序最终给出了一种合理地调度活动执行的先后顺序。如果所有活动之间存在着一种或多种合理的顺序,能够顺利完成全部活动,则表明该 A O V AOV AOV网络为有向无回路图或有向无环图。若某个活动A依赖活动B,而活动B又依赖活动A,则表明 A O V AOV AOV网络存在回路或向环。因此无法合理的完成全部活动。

    拓扑排序方法

    那么,如何确定一个有向图是否具有拓扑排序,也即是确定一个有向图是否存在回路或环呢?这里给出执行拓扑排序的方法:
    不断重复地寻找入度为0的顶点,执行如下操作:首先将该顶点作为拓扑排序的输出结果,然后将该顶点及顶点关联的出边从图中删去。循环结束条件为:所有的顶点都已搜索完毕,或着顶点未搜索完,但是顶点的入度不为0,无法删除。

    解释一下

    入度(inDegree):顶点的入度表示有向图中以该顶点为终点的边的个数;出度(outDegree):顶点的出度表示有向图中以该顶点为起点的边的个数。因此,所谓的顶点的出边是指以顶点为起点的边。

    由拓扑排序推出的原则可知,拓扑排序的第一个顶点即为入度为0的点,那么在有向图中删除该顶点后的构成的新图,重复地进行拓扑排序即可得到最终的拓扑排序结果。

    具体到解决问题的方法上,我们直到关于图的搜索一般有两种方式:广度优先搜索和深度优先搜索。

    广度优先搜索步骤

    1. 定义inDegree用于存储搜索过程中每一个顶点的入度。
    2. 遍历一边图的邻接表,将每一个顶点的邻接表转化为对应顶点的入度。
      具体地,对于一条有向边 u → v u \rightarrow v uv,则inDegree(v) += 1。
    3. 选择入度为0的顶点开始搜索,将顶点作为拓扑排序输出。
    4. 对于已经完成搜索的顶点,更新其邻接表中顶点的入度,值减一。
    5. repeat 3,4,until 循环结束条件。
    6. 循环结束条件:a、搜索完有向图中全部顶点,b、无法完成全部顶点的搜索。
    7. 满足条件a时,表明有向图存在拓扑排序结果;满足条件b时,则表明该有向图存在回路或环,不存在拓扑排序。

    BFS Pseudocode

    e d g e s edges edges 邻接表集合
    i n D e g r e e s inDegrees inDegrees 顶点的入度集合
    b f s Q bfsQ bfsQ 搜索队列,存放入度为0的顶点
    t o p o L i s t topoList topoList 存储拓扑排序结果

    BFS(G(V, E))
        //初始化
        for u in G(V)
        	for v in edges(u)
              	do inDegrees(v) += 1
    
        //放入入度为0的顶点
        for degree in inDegrees
            do if degree == 0 then
                bfsQ.push(i);
    
        //循环搜索
        while bfsQ not empty do
            //搜索到入度为0的顶点
            vertex = bfsQ.pop
            //插入到拓扑排序结果中
            topoList.add(vertex)
    
    		//搜索顶点vertex的邻接表
            for v in edges(vertex)
            	//更新顶点v的入度值
                inDegrees(v) -= 1
                do if inDegrees(v) == 0
                    //顶点入度减为0时添加待搜索队列中
                    then bfsQ.push(v)
    
            //搜索结束后,判断结束条件
            //当拓扑排序结果为全部的顶点时,表明满足循环结束条件a,否则满足循环结束条件b。
            return topoList.size() == |V| ? topoList: 0;
    

    深度优先搜索步骤

    DFS在搜索过程中顶点具有三种状态:未搜索(0),搜索中(1),已搜索(2)。
    三种状态的含义如下:
    未搜索(0):表示搜索过程中该顶点尚未被发现,属于一个新顶点,
    搜索中(1):表示该顶点已被发现, 但其邻接顶点还尚未被搜索完,
    已搜索(2):表示该顶点及其邻接顶点都完成搜索。

    DFS Pseudocode

    e d g e s edges edges 邻接表集合
    v i s i t e d visited visited 用于保存顶点的搜索状态
    S S S 栈,保存拓扑排序结果

    algorithm for DFS(G(V,E))
        //初始化visited
        for u in V[G]
            do visited(u) = 0
    
        for u in V[G]
            do if visited(u) == 0 then
            	//深度优先搜索全部的顶点
                DFS(u)
        拓扑排序结果为S出栈的顺序,原因是先完成搜索的顶点存放到栈的底部
    
    DFS(u)
    	//顶点的状态设为搜索中
        do visited(u) = 1
        for v in edges(u)
        	//深度优先的方式进行邻接表的搜索
            do if visited(v) == 0 then
            	//遇到未搜索状态的顶点,继续进行深度优先搜索
                DFS(u)
            do if visited(v) == 1 then
            	//遇到搜索中状态的顶点,说明此前该顶点已经在这条深度优先搜索路径中出现两次
            	//这里表明有向图中存在回路或环
            do if visited(v) == 2 then
            	//pass 不重要的
                trivial
        //到这里说明顶点u已经完成深度优先搜索,更新其搜索状态为已搜索
        visited(u) == 2
        //入栈
        S.push(u)
    

    典型的应用

    力扣题解-207. 课程表
    力扣题解-210. 课程表 II

    展开全文
  • 数据结构-结构转化为二叉树

    千次阅读 2019-12-07 18:10:55
    首先声明这个不是连通,存在3个连通分支 #include<iostream> using namespace std; struct TreeNode{ int data; struct TreeNode* f; struct TreeNode* s; }; char name[13]={'a','b','c','d','e','f'...
    • 不多bb先上代码

    首先声明这个图不是连通图,存在3个连通分支

    在这里插入图片描述

    #include<iostream>
    using namespace std;
    struct TreeNode{
        int data;
        struct TreeNode* f;
        struct TreeNode* s;
    };
    char name[13]={'a','b','c','d','e','f','g','h','i','j','k','l','m'};//data[a],a号点的名字
    struct G{
        int n;
        int weight[20][20];
    };
    struct G* creat(){
        struct G* G=new struct G;
        cin>>G->n;
        for(int a=0;a<G->n;a++){
            for(int b=0;b<G->n;b++){
                cin>>G->weight[a][b];
            }
        }
        return G;
    };
    struct TreeNode* creatNode(int data ){
        struct TreeNode* head=new struct TreeNode;
        head->data=data;
        head->s=NULL;
        head->f=NULL;
        return head;
    };
    void fun1(struct G *G,struct TreeNode ** head,int *flag,int dian){
        int f=1;//g==1 访问了第一个孩子 g==0 没有访问第一个;
        flag[dian]=1;
        struct TreeNode *pr=NULL;
        for(int a=0;a<G->n;a++){
            if(G->weight[dian][a]==1&&flag[a]!=1){
                struct TreeNode* p=creatNode(a);
                if(f==1){
                    (*head)->f=p;
                    f=0;
                }else{
                    pr->s=p;
                }
                pr=p;
                fun1(G,&p,flag,a);
            }
        }
    }
    void fun(struct G* G ,struct TreeNode**head,int *flag){
        struct TreeNode* pr=NULL;
        for(int a=0;a<G->n;a++){
            if(flag[a]!=1){
                struct TreeNode*p=creatNode(a);
                if(*head==NULL)*head=p;
                else {
                    pr->s=p;
                }
                pr=p;
                fun1(G,&p,flag,a);
            }
        }
    }
    void xian(struct TreeNode* head){
        if(head==NULL)return ;
        cout<<name[head->data]<<' ';
        xian(head->f);
        xian(head->s);
    }
    void hou(struct TreeNode *head){
        if(head==NULL)return ;
        hou(head->f);
        cout<<name[head->data]<<' ';
        hou(head->s);
    }
    main(){
        struct G* G=creat();
        int *flag= new int[G->n];
        for(int a=0;a<G->n;a++){
            flag[a]=0;
        }
        struct TreeNode* head=NULL;
        fun(G,&head,flag);
        xian(head);
        cout<<endl;
        hou(head);
    }
    /*
        13
        0 1 1 0 0 1 0 0 0 0 0 1 0
        1 0 0 0 0 0 0 0 0 0 0 0 1
        1 0 0 0 0 0 0 0 0 0 0 0 0
        0 0 0 0 1 0 0 0 0 0 0 0 0
        0 0 0 1 0 0 0 0 0 0 0 0 0
        1 0 0 0 0 0 0 0 0 0 0 0 0
        0 0 0 0 0 0 0 1 1 0 1 0 0
        0 0 0 0 0 0 1 0 0 0 1 0 0
        0 0 0 0 0 0 1 0 0 0 0 0 0
        0 0 0 0 0 0 0 0 0 0 0 1 1
        0 0 0 0 0 0 1 1 0 0 0 0 0
        1 0 0 0 0 0 0 0 0 1 0 0 1
        0 1 0 0 0 0 0 0 0 1 0 1 0
    
    
    0 1 12 9 11 2 5 3 4 6 7 10 8
    xian:
    a b m j l c f d e g h k i
    zhong:
    l j m b c f a e d k h i g
    */
    
    

    这个算法真的花费了我好多脑力,注意事项:

    思路

    • 如果这个图不是连通图需要一个函数把每个连通分量都“合在”一个二叉树中(这是fun()的功能)
    • 创建一个图 这个很简单你们都会
    • fun()将遍历图的每一个连通分支同时以一个连通分支的其中一个点作为根节点调用fun1()函数来遍历这个连通分支中的所有点
    • fun1()函数是个深度优先的遍历 但要值得注意的是first这个变量代表的意思:时候遍历了这个点的下一个点(赋给左孩子)否则(给右孩子)而且永远有一个单独的指针指向我们新创建的节点!!这是是最关键的!(反正我在这弄了好久)

    注意事项

    • 简单说一下fun()函数 的最关键的部分:创建一个节点存储第一个点(一定是第一个点)如果head没有东西,那就给head 因为这是我们在外界函数的头!如果*head有东西 那就给 当前活跃的节点()的右孩子 这是因为我们是兄弟啊 不管怎么说我都会以这个新创的节点为活跃节点
    • fun1()函数 最关键的部分:我们的父亲(头结点已经知道了)来了,我们要接到父亲的身上。(记住:递归函数调用的时候有可能回来的)要记录是否访问了第一个孩子将其赋给左孩子 否则赋给活跃节点的右兄弟!

    赶紧写代码吧

    展开全文
  • 树转化为二叉树表示

    千次阅读 2016-08-05 20:14:45
    二叉树在数据结构的重要性是因为...如果需要将上转换二叉树,也就是由N个分支转换2个分支。我们可以把每一个拥有同一父节点的子节点,也就是兄弟结点右连接起来。保留最左边的父子连接,将其他的父子连接都
  • 向图的最小生成

    千次阅读 2020-06-20 16:25:09
    //的数据结构 class MGraph { private: vector<vector<int>> adjMatrix; vector<int> nodeData; int nodeNum; public: MGraph(int num) { nodeNum = num; nodeData
  • 有向图删除边得到有向无环图

    千次阅读 2019-04-26 00:30:05
    给定用邻接表表示的有向图G,从G中删除一些边,将G转化为有向无环图 具体思路 判定是否是有向图可以通过DFS或者拓扑排序来完成,笔者采用的是DFS的方式。具体的思路:对图进行DFS,在每一个没有被访问的过的结点做...
  • 向图的连通分量和生成

    千次阅读 2020-06-15 20:04:17
    //的邻接表表示 //弧节点 class GraphArcNode { private: int weight; int adjVertexIndex; GraphArcNode* nextArcNode; public: GraphArcNode(int d = 0, int index = 0) { weight = d; adjVertexIndex ...
  • 的定义背景知识看到这篇博客相信一开始映入读者演练的就是下面这幅了,这就是传说中的七桥问题(哥尼斯堡桥问题)。在哥尼斯堡,普雷格尔河环绕着奈佛夫岛(中的A岛)。这条河将陆地分成了下面4个区域,该处...
  • DFS的代码 w=第一个点 for every vertex v adjacent to w ...上随找一点 初,取A点;此时遍到A! 然后找到B点,那B点成第二遍点! 第二步完成后,红表到B而过的边 复步2,就遍到C。 三步完后,...
  • 有向图无向图判断有环(求环的长度)

    千次阅读 2018-06-13 12:39:18
    东北地区赛个无向图判自环的题当时没苟出来,回来之后想了想用并查集可以实现,然后仔细查了一波还有哪些方法…… 总结一波博客吧QAQ…… 资源来源: ... ... ...
  • 邻接表的特征 1.与图结构的一般化储存方式。还能实现开散式Hash。 2.可以看成“带有索引数组的多个数据链表”构成的结构集合。 3.这样的结构分成若干类,每类可以构成链表...带权有向图的存储 具体代码实现...
  • 9 概率模型(四):道德、因子

    千次阅读 2020-06-05 12:56:32
    Moral Graph 存在的意义就是将有向图转化为无向图来研究。因为无向图比有向图更加的Generalize 一些。在概率图中,我们可以分为贝叶斯网络(有向图) 和马尔可夫网络(无向图)。 无向图可以表示:p(x)=1z∏i=1kϕci
  • 有向图中打印所有的环路

    千次阅读 2017-06-10 13:34:47
    最近项目中需要研究了一下有向图的环路问题。一个IT企业中有成千上万个应用,各个应用之间都是相互依赖的,一个用户请求...这样所有的应用形成一个有向图,那么如果这个有向图中出现了环路,就悲剧了,用户的请求
  • 1)遍历无向图的各顶点,将其作为一个初始点,建立深度优先生成 2)在建树函数DFSTree()中,设置标识,将第一个结点设置根节点的左孩子,其余结点作为左孩子的兄弟,具体见DFSTree()函数 3)在生成森林函数...
  • | 深度优先生成和广度优先生成

    万次阅读 多人点赞 2018-11-07 17:52:40
    本章的第一节中,介绍了有关生成和生成森林的有关知识,本节来解决...例如,图 1 中的无向图是由 V1~V7 的顶点和编号分别 a~i 的边组成。当使用深度优先搜索算法时,假设 V1 作为遍历的起始点,涉及到的顶点和...
  • 图(有向图、无向图)

    万次阅读 2013-12-03 17:02:06
    ⑶均为图 (Graph),它若干个不同的点 v 1, v 2, …, v n,在其中一些点之间用直线或曲线连接。中的这些点被称为顶点 (vertex)或结点,连接顶点的曲线或直线称为边 (edge)。通常将这种由若干个顶点...
  • 向图的最小生成(prim算法)

    千次阅读 2015-09-16 19:10:32
    假设整个无向图中的点记A,最小生成中的点记T,其他点记Q(也就是Q= A-T),T与Q相连的边记B 算法构造过程: 1、初始化:首先将一个点(随意一个)加入最小生成中 2、在所有Q中找到一条权值最小的边B...
  • ——最小生成

    万次阅读 多人点赞 2018-11-01 14:40:48
    图——最小生成 1. 基本概念 在一个连通无向图G=(V, E)中,对于其中的每条边(u,v)∈E,赋予其权重w(u, v),则最小生成问题就是要在G中找到一个无环子集T ...
  • 硬核图解面试最怕的红黑【建议反复摩擦】

    万次阅读 多人点赞 2020-11-05 09:26:58
    考虑到部分读者充足的精力研究以2-3-4树为概念模型的红黑树,在介绍2-3树的同时也会带上2-3-4树的基础知识,帮助学余力的读者去理解算法导论中的红黑树。(所以如果没有必要,只看2-3树的部分就行)。 我们在...
  • 一个的生成集合当中权值之和最小的生成,可以一种,也可以多种,这与本身结构有关。 包括了中的所有节点,所有节点之间都边,但是没有连通; 就是 N个顶点 N-1个边; 就是一个连通的极...
  • 的深度优先搜索算法并生成DFS

    万次阅读 2017-12-04 00:59:53
    前面一篇文章介绍了的广度优先搜索算法和BFS,这篇文件笔者将介绍另一种的遍历算法-深度优先算法概述深度优先搜索(Depth-First Search,DFS)选取下一顶点的策略,可概括:优先选取最后一个被访问到的顶点...
  • Prufer 数列,可以用来解一些关于无根计数的... (1)无根树转化为 Prufer 序列。 首先定义无根中度数 111 的节点是叶子节点。 找到编号最小的叶子并删除,序列中添加与之相连的节点编号,重复执行直到只...
  • 因子

    千次阅读 2018-10-19 08:56:37
    有向图和无向图都可以使得,若干个变量的一个联合概率函数(或全局函数)能够表示成,这些变量的子集上的因子的乘积。 因⼦图比有向图和无向图更显式地表示了这个分解,方法是:在表示变量的结点的基础上,又引入...
  • 的广度优先搜索算法并生成BFS

    万次阅读 2017-12-04 00:11:24
    笔者在前面的两篇文章中介绍了的两种实现方法: 的邻接表的实现 的邻接矩阵的实现 接下来笔者将介绍遍历算法
  • 点云地图PCL转换成为八叉地图octomap

    万次阅读 多人点赞 2018-04-12 11:55:20
    //TODO//完成离线点云地图到八叉地图的转换//进一步在线实时完成点云地图到八叉地图的转换
  • 判断无向图中是否回路

    万次阅读 多人点赞 2014-12-15 17:05:10
     在有向图中,先找出入度0的顶点,删除与这个顶点相关联的边(出边),将与这些边相关的其它顶点的入度减1,循环直到没有入度0的定点。如果此时还有未被删除顶点,则必存在环路,否则不存在环路。
  • 数据结构(线性表&&

    千次阅读 2020-03-06 16:12:44
    定义:线性表是n个元素的有限序列,通常表示{a1,a2,...,an},对于非空线性表如下几个特点: 1)存在唯一的一个被称为"第一个"(“最后一个”)的元素; 2)除第一个元素序列中的每一个元素都唯一前驱; 3)除...
  • BFS遍历和DFS遍历

    千次阅读 2019-11-29 11:26:52
    以下为图到遍历转化(如果不清楚的遍历,请先阅读笔者的另一篇文章:的遍历(动图)),按照DFS遍历的顺序,绘制成一棵,途中红色的边就是遍历过程中没有经过的边(在遍历上,红色的边其实是不存在的,只是为了和...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 65,558
精华内容 26,223
关键字:

有向图转化为树

友情链接: TEST_TCP.rar