dfsfunction.cpp

DFS非递归函数 函数功能：图的dfs的非递归算法(用堆栈实现) 输入：图的邻接矩阵 输出：dfs序列

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

#define INFINITY 32767			//最大权值
#define MAX_VERTEX_NUM 20		//最大定点个数
#define OK 1
#define ERROR -1
#define OVERFLOW -2
#define NULL 0
int visited[MAX_VERTEX_NUM];	//用于DFS遍历的辅助数组

typedef struct ArcCell			//邻接矩阵元素结构
{
	int adj;					//顶点关系类型.对带权图为权值类型,对无权图用1或0表示相邻与否
	char *info;					//该边相关信息指针
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct					//“图”结构
{
	char vexs[MAX_VERTEX_NUM];	//顶点向量
	AdjMatrix arcs;				//邻接矩阵
	int vexnum,arcnum;			//图的当前顶点数，边数
}MGraph;

int LocateVex(MGraph G,char v)	//查找为v的顶点在顶点向量G.vexs[]中的位置
{
	int t;
	for(t=0;t<G.vexnum;t++)
		if(v==G.vexs[t])
			return t;
		return -1;
}

int FirstAdjVex(MGraph G,char v)	//查找v的第一个邻接顶点在图G中的位置
{
	int i,j;
	i=LocateVex(G,v);
	if(i==-1)						//顶点v不存在
		return ERROR;
	for(j=0;j<G.vexnum;j++)
		if(G.arcs[i][j].adj==1)
			return j;
		return -1;
}

int NextAdjVex(MGraph G,char v,char w)
{	//	查找v的下一个邻接顶点(相对于w的)在图G中的位置
	int j,i1,i2;
	i1=LocateVex(G,v);
	i2=LocateVex(G,w);
	if(i1==-1||i2==-1||i1==i2)
		return ERROR;
	for(j=i2+1;j<G.vexnum;j++)
		if(G.arcs[i1][j].adj==1)
			return j;
		return -1;
}

int Visit(char v)			//访问顶点v
{
	printf("%c",v);
	return OK;
}

/*------采用邻接矩阵表示法建立无向图及图的DFS遍历----------*/
int GreateUDG(MGraph &G)			//构造无向图G
{
	int v,e,i,j,t;
	char v1,v2;
	printf("请输入顶点数：");
	scanf("%d",&v);
	if(v<0)
		return ERROR;
	G.vexnum=v;
	
	printf("请输入边数：");
	scanf("%d",&e);
	if(e<0)
		return ERROR;
	G.arcnum=e;
	for(t=0;t<G.vexnum;t++)		//输入v个顶点的值到向量G.vexs[]
	{
		printf("请输入顶点%d的信息:",t+1);
		fflush(stdin);
		scanf("%c",&G.vexs[t]);
	}
	for(i=0;i<G.vexnum;i++)		//初始化邻接矩阵G.arcs[][]
		for(j=0;j<G.vexnum;j++)
		{
			G.arcs[i][j].adj=INFINITY;
			G.arcs[i][j].info=NULL;			//无边的其他信息
		}
	for(t=0;t<G.arcnum;t++)					//构造无向图G的邻接矩阵
	{
		fflush(stdin);
		printf("输入v1和v2的信息：v1-v2:");	//短横线-为分隔符
			scanf("%c%*c%c",&v1,&v2);		//"%*c"是—
		i=LocateVex(G,v1);
		j=LocateVex(G,v2);
		if(i==-1||j==-1||i==j)
			return ERROR;
		G.arcs[i][j].adj=G.arcs[j][i].adj=1;
	}
	return OK;
}

void DFS(MGraph G,int v)				//从第v个顶点出发，深度优先遍历图G
{
	int w;
	visited[v]=1;						//设置访问标记
	Visit(G.vexs[v]);
	w=FirstAdjVex(G,G.vexs[v]);
	for(;w>=0;w=NextAdjVex(G,G.vexs[v],G.vexs[w]))
		if(!visited[w])
			DFS(G,w);					//对v的尚未访问的邻接顶点w递归调用DFS()
}

void DFSTraverse(MGraph G)				//深度优先遍历图G
{
	int v;
	for(v=0;v<G.vexnum;v++)
		visited[v]=0;
	for(v=0;v<G.vexnum;v++)
		if(!visited[v])
			DFS(G,v);
}

void main()
{
	//clrscr();
	MGraph G;
	printf("创建无向图：\n");
	if(GreateUDG(G))
	{
		printf("深度优先遍历：");
		DFSTraverse(G);
		printf("\n");
	}
}