tu.cpp

无向图的实现和深度优先算法

#include"head.h"
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20 //最大顶点个数
#define MAX_NAME 5//顶点字符串的最大长度+1

typedef  int VRType;                                                		
typedef  char  VertexType[MAX_NAME];		//顶点类型


enum GraphKind{DG,DN,AG,AN};

typedef struct{

	VRType adj;

} ArcCell ,AdjMatrix[MAX_VERTEX_NUM][ MAX_VERTEX_NUM];
                   //弧元类型	
                  //弧的邻接矩阵类型

struct MGraph{
	VertexType  vexs[MAX_VERTEX_NUM];		//顶点向量
	AdjMatrix  arcs;							//邻接矩阵
	int  vexnum, arcnum;						//顶点数和弧数
	//GraphKind kind;							//种类标志（无向图取值UDG）
};


int LocateVex(MGraph G,VertexType u)
{//初始条件：图G存在，u和G中顶点有相同特征
	//操作结果：若G中存在顶点u，则返回该顶点在图中位置，否则返回-1；

	int i;
 for(i=0;i<G.vexnum;++i)
  if(strcmp(u,G.vexs[i])==0)
   return i; 
 return -1;


}
VertexType& GetVex(MGraph G,int v)
{
	if(v>+G.vexnum||v<0)
		exit(ERROR);
	return G.vexs[v];
}

Status GreateAG(MGraph &G)
{//邻接矩阵表示法，构造无向图G
	int i,j,k;
	VertexType va,vb;
	printf("请输入无向图G的顶点数，边数：");
	scanf("%d,%d,",&G.vexnum,&G.arcnum);
	printf("请输入%d个顶点的值(<%d个字符)\n",G.vexnum,MAX_NAME);
	for(i=0;i<G.vexnum;++i)//构造顶点向量
		scanf("%s",G.vexs[i]); //初始化邻接矩阵
	for(i=0;i<G.vexnum;++i)	
	for(j=0;j<G.vexnum;++j)
		{
			G.arcs[i][j].adj=0;//图
		}
		printf("请输入%d条边的顶点1 顶点2(以空格作为间隔)\n",G.arcnum);
		for(k=0;k<G.arcnum;++k)
		{
			scanf("%s%s*c",va,vb);
			i=LocateVex(G,va);
			j=LocateVex(G,vb);
			G.arcs[i][j].adj=G.arcs[j][i].adj=1;//无向图
		}
		
		return OK;

}




int FirstAdjVex(MGraph G,VertexType v)
{//初始条件：图G存在，v是G中某个顶点
	//操作结果:返回v的第一个邻接顶点的序号.若没有邻接顶点,则返回-1
	int i,j=0,k;
	k=LocateVex(G,v); //k为顶点v在图G中的序号
	for (i=0;i<G.vexnum;i++)
		if(G.arcs[k][i].adj!=j)
			return i;
		return -1;

}


int NextAdjVex(MGraph G,VertexType v,VertexType w)
{
	//初始化条件:图G存在,v是G中某个顶点,w是v的相邻顶点
	//操作结果:返回v的下一个邻接顶点的序号,若w是v的最后一个邻接顶点,则返回-1
	int i,j=0,k1,k2;
	k1=LocateVex(G,v);//k1为顶点v在图中的序号
	k2=LocateVex(G,w);//k2为顶点v在图中的序号
	for(i=k2+1;i<G.vexnum;i++)
		if(G.arcs[k1][i].adj!=j)
			return i;
		return -1;
}

bool visited[MAX_VERTEX_NUM];//访问标志数组(全局)
Status(*VisitFunc)(VertexType);//函数变量
void DFS(MGraph G,int v)
{//从第v个顶点出发递归地深度优先遍历图G
	VertexType w1,v1;
	int w;
	visited[v]=TRUE;//设置访问标志为Ture(已访问)
	VisitFunc(G.vexs[v]);//访问第v个顶点
	strcpy(v1,GetVex(G,v));
	for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,GetVex(G,w))))
	for(int j=0;j<G.arcnum;j++)
		if(!visited[w])
			DFS(G,w);//递归
}

void DFSTraverse(MGraph G,Status(*Visit)(VertexType))
{//初始条件:图G存在,Visit是顶点的应用函数
	//操作结果:从第一个顶点起,深度优先遍历图G,并对每个顶点调用Visit一次且只有一次,一旦Visit失败,则操作失败
	int v;
	VisitFunc=Visit;
	for(v=0;v<G.vexnum;v++)
		visited[v]=FALSE; //初始化访问标志数组
	for(v=0;v<G.vexnum;v++)
		if(!visited[v])
			DFS(G,v);   //对没有访问的顶点调用DFS
		printf("\n");

}

void Display(MGraph G)
{
	//输出邻接矩阵
	
	int i,j;
	printf("%d个顶点%d条边\n",G.vexnum,G.arcnum);
	for(i=0;i<G.vexnum;i++) //输出G.vexs
		printf("G.vex[%d]=%s\n",i,G.vexs[i]);
	printf("%d条边:\n",G.arcnum);//输出弧
	for(i=0;i<G.vexnum;i++){
		for(j=i+1;j<G.vexnum;j++)
			if(G.arcs[i][j].adj)
			printf("%s-%s  ",G.vexs[i],G.vexs[j]);
		printf("\n");
	}
	


}
Status visit(VertexType i)
{
	printf("%s ",i);
	return OK;
}

void main(){
	MGraph g;
	GreateAG(g);  //构建无向图
	Display(g);    //显示图
       printf("深度优先算法结果:\n");
		DFSTraverse(g,visit);

}