一种有向图及无向图所有生成树的搜索算法

摘要

本发明公开了一种有向图及无向图所有生成树的搜索算法，基于MATLAB平台，在有向或无向图中找到以为根节点，包含给定子树的所有生成树，包括节点邻接支路、支路扩张、所有生成树搜索三个部分，所有生成树搜索调用节点邻接支路、支路扩张而实现，在时间复杂度及空间复杂度方面具有十分优越的性能，能够可靠、快速地搜索出有向图及无向图的所有生成树，方法巧妙，思路新颖，具有良好的应用前景。

主权项

一种有向图及无向图所有生成树的搜索算法，其特征在于：该算法基于MATLAB平台，在有向或无向图G₁中找到以r为根节点，包含给定子树T的所有生成树，包括节点邻接支路、支路扩张、所有生成树搜索，节点邻接支路的实现过程，包括以下步骤，步骤(A1)输入节点支路关联矩阵A，行数为节点数，列数等于支路数；步骤(A2)通过赋值语句生成一个与节点支路关联矩阵A维数相同的全零矩阵X；步骤(A3)从左到右依次扫描节点支路关联矩阵A的每一行对应的元素，若元素不为零，则在全零矩阵X的对应位置记录该元素所处的列号；支路扩张的实现过程，包括以下步骤，步骤(B1)，在图G₁中选择一条边e₁，e₁的父节点属于T，子节点不属于T，找到包含T∪e₁的所有生成树，并从图G₁中删去边e₁，形成图G₂；步骤(B2)，重复步骤(1)，在图G_i中选择一条边e_i，e_i的父节点属于T，但是子节点不属于T，在图G_i中，找到包含T∪e_i所有的生成树，并从图^w_i中删去边e_i，形成图G_i+1；步骤(B3)，若删去边e_k是图G_k的桥，停止搜索，所述图G_k的桥为当删去边e_k后，被修改后的图G_k被分成两个孤立的图；所有生成树搜索的实现过程，包括以下步骤，步骤(C1)若G为有向图，则执行步骤(C3)；若为无向图，执行步骤(C2)，将无向图转化为有向图；步骤(C2)，将无向图的每条边加上一个箭头，并在每条有箭头的边的端点之间加上一条箭头方向相反的边，边的编号为原来边的编号加上总边数，所述无向图转化为有向图，执行步骤(C3)；步骤(C3)，初始化T中只包含根节点，F中只包含以根节点为父节点的有向支路。调用节点邻接支路的实现过程，以及支路扩张的实现过程找到以r为根节点包含T的所有生成树。