查找一个图中所有树算法.doc

思路：1.使用堆栈列出所有可能的支路，因为树中支路个数为n-1。2.判断支路是否包含所有节点，包含则为树。核心函数：/*功能：获得图的所有树*参数：图的关联矩阵*返回：所有树的数组（以节点形式存放）*/MatrixGetAllTrees(constMatrix&m)MatrixAllTrees;vectorBranchs;intBranchNum=m0.size();/初始化可选支路堆栈for(inti=0;im.size()-1;i+)Branchs.push_back(i);doif(IsTree(m,Branchs)/如果这些支路能构成树，添加到返回数组中AllTrees.push_back(Branchs);while(GetNextBranch(Branchs,BranchNum);/获得下一个可用支路，找不到则结束returnAllTrees;程序源代码：#include#include#include#include#include#includeusingnamespacestd;typedefvectorvector Matrix;MatrixGetAssociatedMatrix()intNoteNum,BranchNum;coutNoteNum;coutBranchNum;MatrixM(NoteNum);for(Matrix:iteratorit=M.begin();it!=M.end() ; +it)(*it).resize(BranchNum);intNoteBegin,NoteEnd;for(intj=0;jBranchNum;j+)cout支路j+1：;scanf(%d-%d,&NoteBegin,&NoteEnd);assert(NoteBegin=NoteNum&NoteEnd= 0 &NoteEnd= 0);/checkMNoteBegin-1j =MNoteEnd-1j = 1;/fillreturnM;voidPrintAssociatedMatrix(constMatrix&m)coutendl关联矩阵为：endl;for(Matrix:size_typei=0;im.size();i+)for(Matrix:size_typej=0;jmi.size();j+)coutmijt;coutendl;boolIsTree(constMatrix&m,constvector&Branchs)vectorflag(m.size();fill(flag.begin(),flag.end(),false);for(vector:size_typei=0;iBranchs.size();i+)for(Matrix:size_typej=0;jm.size();j+)if(mjBranchsi = 1)flagj=true;for(vector:size_typej=0;jflag.size();j+)if(!flagj)returnfalse;returntrue;boolNextBranch(vector&Branchs,intMaxValue)if(Branchs.empty()returnfalse;if(Branchs.back() MaxValue)Branchs.back()+;returntrue;elseBranchs.pop_back();returnNextBranch(Branchs,MaxValue-1);boolGetNextBranch(vector&Branchs,intBranchNum)intBranchLength=Branchs.size();intMaxValue=BranchNum- 1;if(NextBranch(Branchs,MaxValue)/add othersfor(inti=Branchs.size();iBranchLength;i+)Branchs.push_back(Branchs.back()+1);returntrue;returnfalse;MatrixGetAllTrees(constMatrix&m)MatrixAllTrees;vectorBranchs;intBranchNum=m0.size();/initfor(inti=0;im.size()-1;i+)Branchs.push_back(i);doif(IsTree(m,Branchs)AllTrees.push_back(Branchs);while(GetNextBranch(Branchs,BranchNum);returnAllTrees;voidPrintTree(constvector&Tree)cout;for(vector:const_iteratorit=Tree.begin();it!=Tree.end(); +it)if(it!=Tree.begin()cout-;coute(*it)+1;coutendl;voidPrintAllTrees(constMatrix&AllTrees)coutendl共有AllTrees.size()个树，分别是：endl;for(Matrix:size_typei=0;iAllTrees.size();i+)cout树i+1：endl;PrintTree(AllTreesi);intmain(intargc,char*argv)MatrixInputMatrix=GetAssociatedMatrix();/获得关联矩阵，由用户输入PrintAssociatedMat