dfstraverse.cpp

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

//CreatUDN.cpp
//采用邻接矩阵表示法,构造图
# include <iostream.h>
# include <malloc.h>
# include <conio.h>
# include <stdio.h>

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

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;

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=w;			//weight
	   if(IncInfo!=0)
		   {	G.arcs[i][j].info=&IncInfo;
			//printf("%d",*G.arcs[i][j].info);
		}
   } //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 DFS(MGraph G,int v,int visited[MAX_VERTEX_NUM])//int *visited)	//DFS() 子函数
//从第 v 个顶点出发，递归地深度优先遍历图 G
{  int j;
   visited[v]=1;
   cout<<v<<"->";		//访问第 v 个顶点
   for(j=1;j<=G.vexnum;j++)
	   if((G.arcs[v][j].adj!=INFINITY)&&(visited[j]!=1))
			//w=j;
			DFS(G,j,visited);
} //DFS() end

void DFSTraverse(MGraph G)		//DFSTraverse() 子函数,对图 G 作深度优先遍历
{  int v;
   int visited[MAX_VERTEX_NUM];
   for(v=1;v<=G.vexnum;++v)
      visited[v]=0;				//访问标志数组初始化
   for(v=1;v<=G.vexnum;++v)
	  if(visited[v]==0)			//对尚未访问的顶点调用 DFS
		  DFS(G,v,visited);
} //DFSTraverse() end

void main()				//main() 函数
{   MGraph G;
    cout<<endl<<endl<<"DFSTraverse.cpp";
    cout<<endl<<"================"<<endl;
    if(CreatUDN(G))		//调用 CreatUDN()
	{	//cout<<endl<<"Create MGraph success !";	//如果构造图成功,则输出图
		printf("\nCreate MGraph success !");
		ShowMGraph(G);	//显示构造成功后的图
	}
    cout<<endl<<endl<<"DFS Traverse is as follows :";
    cout<<endl<<"Begin->";
    DFSTraverse(G);		//调用 DFSTraverse()
	cout<<"end!"<<endl<<endl<<"...OK!...";
    getch();
} //main() end