图的连通性问题，图转换为树--DNF与BNF生成树

快来打我* 2022-07-14 04:08 129阅读 0赞

**使用深度优先搜索和广度优先搜索的方法创建生成树**

//DNF生成树
    #include <iostream>
    using namespace std;
    const int max_vex=30;
    struct linknode//表节点类型定义
    {
    	int adjvex;//邻接点（于vi连通的其它节点）在头结点数组中的位置下标
    	int info;//边或弧的信息，这里表示权值
    	linknode *nextarc;//指向下一个表节点
    };
    struct vexnode//顶点结点定义类型
    {
    	char data;//顶点信息，这里用char型表示
    	          //typedef char vextype;使用模板表示
    	linknode *firstarc;//指向第一个边节点
    };
    struct algraph//图的结构定义
    {
    	int vexnum;
    	vexnode adjlist[max_vex];//顶点数组
    };
    void creatalgraph(algraph *G)//想了一下，这个不是重点，可以在
    	                   //主函数中输入图，或者对顶点数组for输入
    	                   //在依次输入边的数据
    {}
    struct csnode//树节点结构
    {
    	int data;
    	csnode *firstchild,*nextsibiling;
    };
    csnode *dfstree(algralph *G,int v)
    {
    	csnode *t,*ptr,*q;//t为母树根节点，ptr为子树根节点
    	linknode *p;
    	int data2;
    	visited[v]=true;
    	t=new csnode;//建立母树根节点
    	t->data=G->adjlist[v].data;
    	t->firstchild=t->nextsibiling=NULL;
    	q=NULL;//这个q是递归的线索，非常重要，子树根节点做兄弟节点时，在while里转时，q=ptr不为空；子树节点做孩子节点是在dfs的上半部分程序转，每次q被赋空值
    	p=G->adjnode[v].firstarc;
    	while(p!=NULL)
    	{
    		if(!visited[p->adjvex])
    		{
    			prt=dfstree(G,p->adjvex);//prt赋值子树根节点做孩子节点，继续往深处走
    		    if(q==NULL) t->firstchild=prt;
    		    else q->nextsibiling=prt;
    		    q=ptr;
    		}
    		p=p->nextarc;//往旁边走，此时子树根节点变为为生成树兄弟节点
    	}
    	return t;
    }
    int main()
    {
    	algraph *G;
    	int v;bool visited[vexnum];
    	for(v=0;v<vexnum;v++)//为图中顶点建立标记数组
    		visited[v]=false;
    	
    	for(int i=0;i<vexnum;i++)//对于非连通图，要把每个顶点过一遍
    	{
    		if(!visited[i]) dnftree(G,v);//这里没有处理好
    	}
            return 0;
    
    }
    //BNF生成树
    #include <iostream>
    using namespace std;
    const int max_vex=30;
    struct linknode//表节点类型定义
    {
    	int adjvex;//邻接点（于vi连通的其它节点）在头结点数组中的位置下标
    	int info;//边或弧的信息，这里表示权值
    	linknode *nextarc;//指向下一个表节点
    };
    struct vexnode//顶点结点定义类型
    {
    	char data;//顶点信息，这里用char型表示
    	          //typedef char vextype;使用模板表示
    	linknode *firstarc;//指向第一个边节点
    };
    struct algraph//图的结构定义
    {
    	int vexnum;
    	vexnode adjlist[max_vex];//顶点数组
    };
    void creatalgraph(algraph *G)//想了一下，这个不是重点，可以在
    	                   //主函数中输入图，或者对顶点数组for输入
    	                   //在依次输入边的数据
    {}
    struct csnode//树节点结构
    {
    	int data;
    	csnode *firstchild,*nextsibiling;
    };
    struct quene
    {
    	int elem[max_vex];
    	int front,reat;
    }
    int main()
    {
    	algraph *G;
    	int v;bool visited[vexnum];
    	for(v=0;v<vexnum;v++)//为图中顶点建立标记数组
    		visited[v]=false;
    	
    	for(int i=0;i<vexnum;i++)//对于非连通图，要把每个顶点过一遍
    	{
    		if(!visited[i]) bnftree(G,v);
    	}
            return 0;
    
    }
    csnode *bfstree(algraph *G,int v)
    {
    	cdnode *t,*prt,*q;
    	linknode *p;
    	quene *Q=new quene;//建立空队列
    	Q->front=Q->rear=0;//通过front和rear的差来判断队列是否为空
    	int w,k;
    	visited[v]=TRUE;
    	t=new csnode;//建立母树根节点t
    	t->data=G->adjlist[v].data;
    	t->firstchild=t->sibiling=NULL;
    	Q->elem[++Q->rear]=v;//入队
    	while（Q->front!=Q->reat)//队列不空....这里的循环是为了接下来出队列向深处走，所以生成的子树根节点（也是下面程序生成的第1个根节点）应为母树左儿子节点
    	{
    		w=Q->elem[++Q->front];//出队列，赋值给w
    		q=NULL;
    		p=G->adjlist[w].firstarc;
    		while(p!=NULL)//这里的循环是接下来进队列即横向走，所以子树根节点（也是下面程序生成的第2.3.....个根节点）应为母树又兄弟节点
    		{
    			k=p->adjvex;
    			if(!visited[k])
    			{
    				visited[k]=TRUE;
    				ptr=new csnode;
    				prt->data=G->adjlist[v].data;
    	            prt->firstchild=t->sibiling=NULL;
    				if(q==NULL) t->firstchild=prt;
    				else q->nextsibing=prt;
    				q=prt;
    				Q->elem[++Q->rear]=k;
    			}
    			p=p->nextarc;
    		}
    	}
    	return t;
    }