dfstree.cpp

c语言数据结构源代码（全）相当经典

//DFSTree.cpp
//无向图的深度优先构造生成树

# include <iostream.h>
# include <malloc.h>
# include <conio.h>
# include <stdio.h>

# define INFINITY 1000
# define MAX_VERTEX_NUM 20
# define OK 1
# define TRUE 1
# define FALSE 0
typedef enum{DG,DN,UDG,UDN} GraphKind;
typedef int EType;
typedef int InfoType;
typedef int VertexType;
typedef int ElemType;

typedef struct ArcCell		//定义 MGraph
{  EType adj;
   InfoType *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{  VertexType vexs[MAX_VERTEX_NUM];
   AdjMatrix  arcs;
   int vexnum,arcnum;
   GraphKind kind;
}MGraph;

typedef struct CSNode		//定义 CSNode
{   ElemType data;
    struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;

int LocateVex(MGraph G,int v)	//确定v在G中的位置
{
	return(v);
}

int CreatUDN(MGraph &G)		//CreatUDN() 子函数
{  int i,j,k,v1,v2,w;
   int IncInfo;
   cout<<endl<<"Please input the number of G.vexnum 顶点数目 (eg, 4): ";
   cin>>G.vexnum;			//输入顶点数目
   cout<<"Please input the number of G.arcnum 弧的数目 (eg, 4): ";
   cin>>G.arcnum;			//输入弧的数目
   //cout<<"Please input IncInfo 弧的信息 (0 for none)                  : ";
   printf("Please input IncInfo 弧的信息 (0 for none)          : ");
   //cin>>IncInfo;			//输入弧的信息
   scanf("%d",&IncInfo);
   for(i=1;i<=G.vexnum;++i)
     for(j=1;j<=G.vexnum;++j)
       {  G.arcs[i][j].adj=INFINITY;	//初始化邻接矩阵
		  G.arcs[i][j].info=NULL;
       }
   cout<<"Plese input 弧 arc(V1-->V2), For example: arc(1,3),arc(2,4)..."<<endl;
   for(k=0;k<G.arcnum;++k)	//构造邻接矩阵
   {   cout<<endl<<"Please input the "<<k+1<<"th arc's v1 弧头 [1.."<<G.vexnum<<"] :";
       cin>>v1;				//输入弧头
       cout<<"Please input the "<<k+1<<"th arc's v2 弧尾 [1.."<<G.vexnum<<"] :";
       cin>>v2;				//输入弧尾
       cout<<"Please input the "<<k+1<<"th arc's weight 权      :";
       cin>>w;				//输入权
	   i=LocateVex(G,v1);	//确定v1在G中的位置
       j=LocateVex(G,v2);	//确定v2在G中的位置
       while(i<1||i>G.vexnum||j<1||j>G.vexnum)	//如果弧头或弧尾不合法,重新输入
       {	cout<<"Please input Again the "<<k+1<<"th arc's v1 弧头[1.."<<G.vexnum<<"] :";
			cin>>v1;
			cout<<"Please input Again the"<<k+1<<"th arc's v2 弧尾[11.."<<G.vexnum<<"] :";
			cin>>v2;
			cout<<"Please input Again the "<<k+1<<"th arc's weight 权      :";
			cin>>w;
			i=LocateVex(G,v1);	//确定v1在G中的位置
			j=LocateVex(G,v2);	//确定v2在G中的位置
       } //while end
       G.arcs[i][j].adj=G.arcs[j][i].adj=w;			//weight
	   if(IncInfo!=0)
			{	G.arcs[i][j].info=&IncInfo;
			}
   } //for end
   return (OK);
} //CreatUDN() end

void ShowMGraph(MGraph G)	//输出图 G
{	int i,j;
	for(i=1;i<=G.vexnum;++i)
		for(j=1;j<=G.vexnum;++j)
			if(G.arcs[i][j].adj!=INFINITY)
				printf("\narc(%d,%d) weight=%d  ",i,j,G.arcs[i][j].adj);
}

void DFSTree(MGraph G,int v,CSTree &T,int visited[MAX_VERTEX_NUM])
//从第v个顶点出发深度优先遍历G,建立以T为根的生成树
//T以孩子兄弟链表作为存储结构
{    int w,first;
     CSTree p,q;
     visited[v]=TRUE;
	 first=1;
	 for(w=1;w<=G.vexnum;++w)
		if((G.arcs[v][w].adj!=INFINITY)&&(visited[w]!=1))
		{	printf("\nArc(%d,%d)",v,w);
			p=(CSTree)malloc(sizeof(CSNode));	//分配孩子结点
			p->data=w;
			p->firstchild=NULL;
			p->nextsibling=NULL;
			if(first)			//w是v的第一个其他未被访问的邻接顶点
			{   T=(CSTree)malloc(sizeof(CSNode));
				T->firstchild=p;//是根的第一个孩子结点
				first=FALSE;
			} //if end
			else				//是上一个邻接顶点的右兄弟结点
				q->nextsibling=p;
			q=p;
			DFSTree(G,w,q,visited);	//从第w个顶点出发深度优先遍历图G,建立子生成树q
		} //if end
} //DFSTree() end

void main()				//main() 函数
{  MGraph G;
   int first=TRUE;
   CSTree T;
   T=(CSTree)malloc(sizeof(CSNode));
   int visited[MAX_VERTEX_NUM],v;
   cout<<endl<<endl<<"DFSTree.cpp";
   cout<<endl<<"==========="<<endl;
   if(CreatUDN(G))		//构造图G
   {	printf("\nCreate MGraph success !");
		ShowMGraph(G);
   }
   for(v=1;v<=G.vexnum;++v)
      visited[v]=0;		//初始化visited[v]
   cout<<endl<<endl<<"Create MiniSpanTree as follows:"<<endl;
   for(v=1;v<=G.vexnum;++v)
		if(!visited[v])
			DFSTree(G,v,T,visited);	//调用 DFSTree()
   cout<<endl<<endl<<"...OK!...";
   getch();
} //main() end