下载文档原格式
在离散数学中，图是一个由点和边组成的抽象数学模型。
其中，树是一种特殊的图，它是一个无环连通图。
在图论中，树扮演了重要的角色，它具有许多有趣的性质和应用。
而生成树则是树的一个特殊子集，它由给定图中的所有顶点和部分边构成。
本文将介绍图的树的基本概念，并探讨生成树的计数方法。
首先，让我们来看看图的树。
树是一种无环连通图，其中任意两个顶点之间存在唯一一条路径。
它具有以下性质：1.n个顶点的树有n-1条边。
这可以通过归纳法证明：当n=1时，结论成立；假设n=k时成立，那么n=k+1时，只需要添加一个顶点和一条边，即可构成n=k+1个顶点的树。
因此，结论成立。
2.连接树上任意两个顶点的边都是桥。
即如果一条边被删除，那么树就会变成两个或更多个不相连的子树。
3.树是一个高度平衡的结构。
对于一个n个顶点的树，任意两个叶子结点之间的路径长度至多相差1。
4.树的任意两个顶点之间有唯一一条路径，路径长度为顶点之间的边数。
接下来，让我们来讨论生成树的计数方法。
生成树是树的一个特殊子集，它是由给定图中的所有顶点和部分边构成。
生成树的计数在图论中具有重要的意义和应用。
对于一个具有n个顶点的连通图来说，其生成树的个数可以通过Cayley公式计算得到。
Cayley公式是由亚瑟·凯利于1889年提出的，它给出了完全图的生成树数目。
据此，我们可以得到生成树的计数公式为：T = n^(n-2)，其中T表示生成树的个数。
此外，还有一种常见的计数方法是基于度数矩阵和邻接矩阵的矩阵树定理。
矩阵树定理由高斯于1847年提出，它提供了一种计算图的生成树个数的方法。
根据矩阵树定理，一个无向图G的生成树数目等于该图度数矩阵的任意一个(n-1)阶主子式的行列式的值。
其中，度数矩阵是一个对角矩阵，它的对角线上的元素为各个顶点的度数。
邻接矩阵则是一个关于顶点间连接关系的矩阵，其中1表示相邻顶点之间存在边，0表示不存在边。
除了数学方法，还存在一种基于图的遍历的计数方法，称为Kirchhoff矩阵树定理。
吴裕雄--天⽣⾃然数据结构学习笔记：什么是⽣成树，⽣成树
（⽣成森林）详解
对连通图进⾏遍历，过程中所经过的边和顶点的组合可看做是⼀棵普通树，通常称为⽣成树。
如图1所⽰，图 1a) 是⼀张连通图，图 1b) 是其对应的2种⽣成树。
连通图中，由于任意两顶点之间可能含有多条通路，遍历连通图的⽅式有多种，往往⼀张连通图可能有多种不同的⽣成树与之对应。
连通图中的⽣成树必须满⾜以下2个条件：
包含连通图中所有的顶点；
任意两顶点之间有且仅有⼀条通路；
因此，连通图的⽣成树具有这样的特征，即⽣成树中边的数量 = 顶点数 - 1。
⽣成森林
⽣成树是对应连通图来说，⽽⽣成森林是对应⾮连通图来说的。
我们知道，⾮连通图可分解为多个连通分量，⽽每个连通分量⼜各⾃对应多个⽣成树（⾄少是1棵），因此与整个⾮连通图相对应的，是由多棵⽣成树组成的⽣成森林。
广度遍历生成树描述了从起点到各顶点的最短路径选自：朱维荣《数据结构》，机械工业出版社。
根据顶点的个数可以将生成树分为二叉、三叉和四叉三种类型。
其中，二叉生成树是指所有节点均位于同一层次上；三叉生成树则要求至少有两个子树位于不同的层次上；而四叉生成树只需要满足任意两个子树位于相邻层即可。
由此可见，对于一般应用来说，二叉生成树比较适合，但如果遇到特殊情况时，也会使用三叉或者四叉生成树。
广度遍历生成树描述了从起点到各顶点的最短路径。
这里我们假设顶点的个数为 n，那么从起点到第 k+1个顶点之间共有 k 条路径，当 k=2时，称该生成树为二叉生成树，否则就叫做三叉生成树。
生成树是一棵有向无环图，它具备有向图的全部性质，例如，它的所有边都是非空的，且没有重复的边等。
与有向图一样，生成树也存在一些基本操作，包括左右子树的建立、删除及插入等。
在遍历过程中，若某条边的长度小于某个阈值，则称该边为空边，否则就称该边为非空边。
因此，在遍历过程中，如果发现某条边的长度大于某个阈值，则表明该边已经被访问过，并且已经走完了所有的路径，这时候就应该把该边从生成树中删去。
另外，如果某条边的长度小于某个阈值，则表示该边还未被访问过，并且仍然处于未访问状态，直接继续往下进行遍历即可。
生成树是一棵有向无环图，它具备有向图的全部性质，例如，它的所有边都是非空的，且没有重复的边等。
与有向图一样，生成树也存在一些基本操作，包括左右子树的建立、删除及插入等。
在遍历过程中，若某条边的长度小于某个阈值，则称该边为空边，否则就称该边为非空边。
因此，在遍历过程中，如果发现某条边的长度大于某个阈值，则表明该边已经被访问过，并且已经走完了所有的路径，这时候就应该把该边从生成树中删去。
另外，如果某条边的长度小于某个阈值，则表示该边还未被访问过，并且仍然处于未访问状态，直接继续往下进行遍历即可。
1.问题描述：不少涉及图上操作的算法都是以图的遍历操作为基础的。
试写一个程序，演示在连通的无向图上访问全部结点的操作。
2.基本要求：以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。
以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。
3.测试数据：教科书图7.33。
暂时忽略里程，起点为北京。
4.实现提示：设图的结点不超过30个，每一个结点用一个编号表示(如果一个图有n个结点，则它们的编号分别为1,2,…,n)。
通过输入图的全部边输入一个图，每一个边为一个数对，可以对边的输入顺序作出某种限制，注意，生成树的边是有向边，端点顺序不能颠倒。
5.选作内容：(1) .借助于栈类型(自己定义和实现)，用非递归算法实现深度优先遍历。
(2) .以邻接表为存储结构，建立深度优先生成树和广度优先生成树，再按凹入表或者树形打印生成树。
1.为实现上述功能，需要有一个图的抽象数据类型。
该抽象数据类型的定义为：ADT Graph{V 是具有相同特性的数据元素的集合，称为顶点集。
R={VR}VR={<v，w> | v ，w v 且P(v，w)，<v，w>表示从v 到w 得弧，谓词P(v，w)定义了弧<v，w>的意义或者信息}} ADT Graph2.此抽象数据类型中的一些常量如下：#define TRUE 1#define FALSE 0#define OK 1#define max_n 20 //最大顶点数typedef char VertexType[20];typedef enum{DG, DN, AG, AN} GraphKind;enum BOOL{False,True};3.树的结构体类型如下所示：typedef struct{ //弧结点与矩阵的类型int adj; //VRType为弧的类型。
图--0,1;网--权值int *Info; //与弧相关的信息的指针,可省略}ArcCell, AdjMatrix[max_n][max_n];typedef struct{VertexType vexs[max_n]; //顶点AdjMatrix arcs; //邻接矩阵int vexnum, arcnum; //顶点数，边数}MGraph;//队列的类型定义typedef int QElemType;typedef struct QNode{QElemType data;struct QNode *next;}QNode, *QueuePtr;typedef struct{QueuePtr front;QueuePtr rear;}LinkQueue;4.本程序包含三个模块1).主程序模块void main( ){创建树；深度优先搜索遍历；广度优先搜索遍历；}2).树模块——实现树的抽象数据类型3).遍历模块——实现树的深度优先遍历和广度优先遍历各模块之间的调用关系如下：主程序模块树模块遍历模块#include "stdafx.h"#include<iostream>using namespace std;#define TRUE 1#define FALSE 0#define OK 1#define max_n 20 //最大顶点数typedef char VertexType[20];typedef enum{DG, DN, AG, AN} GraphKind;enum BOOL{False,True};typedef struct{ //弧结点与矩阵的类型int adj; //VRType为弧的类型。
生成树算法的三个步骤生成树是图论中的重要概念，它描述了一个连通图的一个子图，该子图包含了图中的所有顶点，并且是无环的。
生成树算法是用来找到一个连通图的生成树的一种方法。
本文将介绍生成树算法的三个步骤：图的遍历、边的选择和生成树的构建。
一、图的遍历图的遍历是生成树算法的第一步，它的目的是将图中的所有顶点访问一遍。
常用的图的遍历算法有深度优先搜索（DFS）和广度优先搜索（BFS）。
深度优先搜索是通过递归的方式进行遍历，从某个顶点开始，先访问它的一个邻接顶点，然后再递归地访问该邻接顶点的邻接顶点，直到所有顶点都被访问过。
广度优先搜索是通过队列的方式进行遍历，从某个顶点开始，先访问它的所有邻接顶点，然后再依次访问这些邻接顶点的邻接顶点，直到所有顶点都被访问过。
二、边的选择边的选择是生成树算法的第二步，它的目的是选择一些边，使得这些边构成一个连通图的生成树。
常用的边的选择算法有最小生成树算法和最大生成树算法。
最小生成树算法的目标是选择一些边，使得这些边的权值之和最小。
常用的最小生成树算法有普里姆算法和克鲁斯卡尔算法。
普里姆算法是从一个顶点开始，每次选择一条最小权值的边，将该边连接的顶点加入到生成树中，直到所有顶点都被加入到生成树中。
克鲁斯卡尔算法是先将所有边按照权值从小到大排序，然后依次选择权值最小的边，如果这条边连接的两个顶点不在同一个连通分量中，则将这条边加入到生成树中。
最大生成树算法的目标是选择一些边，使得这些边的权值之和最大。
常用的最大生成树算法有逆克鲁斯卡尔算法和逆普里姆算法。
逆克鲁斯卡尔算法和逆普里姆算法的原理与克鲁斯卡尔算法和普里姆算法相反。
三、生成树的构建生成树的构建是生成树算法的第三步，它的目的是根据选择的边构建一个生成树。
生成树可以用邻接矩阵或邻接表来表示。
邻接矩阵是一个二维数组，其中的元素表示两个顶点之间是否有边。
邻接表是一种链表的数据结构，其中的每个节点表示一个顶点，节点的值表示该顶点的邻接顶点。
实验项目：图的先深、先广遍历生成树实验目的：1、学会把图转化为程序能识别的邻接矩阵2、透彻理解图的两种遍历方法及对应的生成树。
涉及的知识点：图的表示法、生成树的概念、图的深度优先、广度优先遍历算法实验内容：该程序是对树进行先深、先广遍历，请在此基础上，改为处理指定图，求该图从指定结点出发的先深、先广遍历生成树。
// AdjMWGraph.h : Defines the entry point for the console application.#include "SeqList.h"#include "SeqQueue.h"const int MaxVertices=10;const int Max Weight=10000; //表示无穷大class AdjMWGraph{private:SeqList Vertices; // 顶点信息的线性表int Edge[MaxVertices][MaxVertices]; //边的权信息矩阵int numOf E dges; //当前的边数public:AdjMWGraph(const int sz=MaxVertices);//构造函数，参数是顶点数目int GraphEmpty()const{ return Vertices.ListEmpty(); }int NumOfVertices(void)//当前结点个数{ return Vertices.ListSize(); }int NumOf E dges(void)//边数{ return numOf E dges; }VerT GetValue(const int i); //取结点i的值int GetWeight(const int v1, const int v2); //取弧的权重;//插入顶点vertexvoid InsertVertex(const VerT &vertex);//插入弧<v1,v2>，权为w eightvoid InsertE dge(const int v1,const int v2,int w eight);//删除与顶点i及关联的边void DeleteVertex(const int i);//删除弧<v1,v2>void DeleteEdge(const int v1,const int v2);//取顶点i的第一条邻接边，返回邻接点的下标，否则返回-1int GetFirstNeighbor(const int v);//取顶点v1与<v1,v2>邻接边的下一条邻接边，返回邻接点，否则返回-1 int GetNextNeighbor(const int v1,const int v2);//对连通图从顶点v开始用visit()先深访问void DepthFirstSearch(const int v, int visited[],void visit(VerT item));//对连通图从顶点v开始用visit()先广访问void BroadFirstSearch(const int v, int visited[],void visit(VerT item));//对非连通图用v isit()先深访问void DepthFirstSearch(void visit(VerT item));//对非连通图用v isit()先广访问void BroadFirstSearch(void visit(VerT item));};//构造函数，参数是顶点数目AdjMWGraph::AdjMWGraph(const int sz){for(int i=0;i<sz;i++)for (int j=0;j<sz;j++){if(i==j)Edge[i][j]=0;else Edge[i][j]=MaxWeight;}numOf E dges=0; //边数初始为0}//取顶点i的值VerT AdjMWGraph::GetValue(const int i){if(i<0||i>Vertices.ListSize()){cerr<<"参数越界出错！"<<endl;exit(1);}//使用线性表的GetData(i)成员函数返回顶点i的值return Vertices.GetData(i);}//取弧的权重int AdjMWGr aph::GetWeight(const int v1,const int v2){if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize()){cerr<<"参数越界出错！"<<endl;exit(1);}return Edge[v1][v2];}//插入顶点vertexvoid AdjMWGraph::InsertVertex(const VerT &vertex){//在顶点线性表Vertices的当前表尾ListSize()插入顶点vertexVertices.Insert(vertex,Vertices.ListSize());}//插入弧<v1,v2>，权为w eightvoid AdjMWGraph::InsertEdge(const int v1,const int v2,int w eight) {if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize()){cerr<<"参数越界出错！"<<endl;exit(1);}E dge[v1][v2]=w eight;E dge[v2][v1]=w eight;//选做，无向边变成有向边numOf E dges++;}//删除与顶点v及关联的边void AdjMWGraph::DeleteVertex(const int v){for(int i=0;i<Vertices.ListSize();i++)for(int j=0;j<Vertices.ListSize();j++)if((i==v||j==v)&&(Edge[i][j]>0&&Edge[i][j]<MaxWeight)){E dge[i][j]=MaxWeight;numOf E dges--;}Vertices.Delete(v);}//删除弧<v1,v2>void AdjMWGraph::DeleteEdge(const int v1,const int v2){if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize()){cerr<<"参数越界出错！"<<endl;exit(1);}E dge[v1][v2]=MaxWeight;numOf E dges--;}//取顶点i的第一条邻接边，返回邻接点的下标，否则返回-1int AdjMWGr aph::GetFirstNeighbor(const int v){if(v<0||v>Vertices.ListSize()){cerr<<"参数越界出错！"<<endl;exit(1);}for (int col=0;col<=Vertices.ListSize();col++)if(Edge[v][col]>0 && Edge[v][col]<MaxWeight)return col;return -1;}//取顶点v1与<v1,v2>邻接边的下一条邻接边，返回邻接点，否则返回-1int AdjMWGr aph::GetNextNeighbor(const int v1,const int v2){if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize()){cerr<<"参数越界出错！"<<endl;exit(1);}for(int col=v2+1;col<=Vertices.ListSize();col++)if(Edge[v1][col]>0&&Edge[v1][col]<Max Weight)return col;return -1;}//对连通图从顶点v开始用visit()先深访问void AdjMWGraph::DepthFirstSearch(const int v, int visited[],void v isit(VerT item)) {visited[v]=1;int w=GetFirstNeighbor(v);w hile(w!=-1){if(!visited[w]){visit(GetValue(v));cout<<"---- "<<GetValue(w)<<endl; //递归输出DepthFirstSearch(w,visited,visit);}w=GetNextNeighbor(v,w);}}//对连通图从顶点v开始用visit()先广访问void AdjMWGraph::BroadFirstSearch(const int v, int visited[],void v isit(VerT item)) {VerT u,w;SeqQueue queue; //定义队列queuevisited[v]=1;queue.QInsert(v);w hile(!queue.QueueEmpty()){u=queue.QDelete();w=GetFirstNeighbor(u);w hile(w!=-1){if(!visited[w]){visit(GetValue(u));cout<<"---- "<<GetValue(w)<<endl; //递归输出 visited[w]=1;queue.QInsert(w);}w=GetNextNeighbor(u,w);}}}//对非连通图用vis it()先深访问void AdjMWGraph::DepthFirstSearch(void vis it(VerT item)) {int *visited=new int[NumOfVertices()];for (int i=0;i<NumOfVertices();i++)visited[i]=0;int count=0;for(i=0;i<NumOfVertices();i++)if(!visited[i]){count++;DepthFirstSearch(i,visited,v isit);}delete []v isited;cout<<endl<<"连通分支数="<<count<<endl;}//对非连通图用vis it()先广访问void AdjMWGraph::BroadFirstSearch(void vis it(VerT item)) {int *visited=new int[NumOfVertices()];for (int i=0;i<NumOfVertices();i++)visited[i]=0;int count=0;for(i=0;i<NumOfVertices();i++)if(!visited[i]){count++;BroadFirstSearch(i,visited,v isit);}delete []v isited;cout<<endl<<"连通分支数="<<count<<endl;}//GraphLib.hstruct Row ColWeight{int row;int col;int w eight;};//建立图G，所建立的图G有n个顶点V[0]……V[n-1]，有e条边E[0]...E[e-1] void CreatGr aph(AdjMWGraph &G,Datatype V[],int n,Row ColWeight E[],int e) {for(int i=0;i<n;i++) G.InsertVertex(V[i]);for(int k=0;k<e;k++)G.InsertEdge(E[k].row,E[k].col,E[k].w eight);}void P r intchar(char item){cout<<" "<<item<<" ";}//Graph.cpptypedef char VerT;typedef char Datatype;#include "AdjMWGraph.h"#include "GraphLib.h"void main(void){AdjMWGraph g;char a[]={'1','2','3','4','5','6','7','8'};Row ColWeight row[]={{0,1,1},{0,2,1},{1,0,1},{1,3,1},{1,4,1},{2,0,1},{2,5,1},{2,6,1},{3,1,1},{3,7,1},{4,1,1},{4,7,1},{5,2,1},{5,7,1},{6,2,1},{6,7,1},{7,3,1},{7,4,1},{7,5,1},{7,6,1}};int n=8,e=10;CreatGraph(g,a,n,row,e);cout<<"当前的顶点个数为："<<g.NumOfVertices()<<endl;cout<<"当前的边的条数为："<<g.NumOf E dges()<<endl;cout<<endl;cout<<"从顶点1出发时："<<endl;cout<<"深度优先搜索序列为："<<endl;int *visited1=new int[g.NumOfVertices()];for(int i=0;i<g.NumOfVertices();i++) visited1[i]=0;g.DepthFirstSearch(0,visited1,P r intchar);cout<<endl<<"广度优先搜索序列为："<<endl;for(i=0;i<g.NumOfVertices();i++) visited1[i]=0;g.BroadFirstSearch(0,visited1,P r intchar);delete []v isited1;cout<<endl;cout<<"从顶点2出发时："<<endl;cout<<"深度优先搜索序列为："<<endl;int *visited2=new int[g.NumOfVertices()];for(int j=0;j<g.NumOfVertices();j++) visited2[j]=0;g.DepthFirstSearch(1,visited2,P r intchar);cout<<endl<<"广度优先搜索序列为："<<endl;for(j=0;j<g.NumOfVertices();j++) visited2[j]=0;g.BroadFirstSearch(1,visited2,P r intchar);delete []v isited2;cout<<endl;/*g.DeleteEdge(0,2);g.DeleteEdge(2,0);cout<<endl<<" 删除边("<<g.GetValue(0)<<g.GetValue(2)<<")之后"<<endl; cout<<endl<<"当前的顶点个数为："<<g.NumOfVertices()<<endl;cout<<"当前的边的条数为："<<g.NumOf E dges()<<endl;cout<<"深度优先搜索序列为："<<endl;g.DepthFirstSearch(P rintchar);cout<<endl<<"广度优先搜索序列为："<<endl;g.BroadFirstSearch(P rintchar);*/}。
