深度搜索——邻接矩阵的遍历（图）

深度搜索——邻接矩阵的遍历（图）

在深度优先遍历过程中，首先需要明白深度优先遍历的实质，就是从邻结点入手，逐一遍历，当访问到一个邻结点后，又从该邻结点开始，向下一个邻接点访问，知道所有访问例所有结点的领结点，判断判断标准为当访问重新回到初始结点时，如果初始结点的所有的邻结点都被访问完，则遍历结束

#include<stdio.h>
#include<stdlib.h>
#define MaxVertexNum 100
typedef int ElemenType;

typedef struct{
	ElemenType list[MaxVertexNum];
	int top;
	int length;
}LIFO;	//定义栈结构体
/*
图---- 
*/
typedef int VertexType;	//结点的类型 
typedef int EdgeType;		//边的类型 


typedef struct{				 
	VertexType	vexs[MaxVertexNum];
	EdgeType 	edge[MaxVertexNum][MaxVertexNum];
	int v,e;	//定义顶点数，边数	
}MGraph;		//定义邻接矩阵

//打印邻接矩阵
void Mprint(MGraph M){		

		 for(int i=0;i<M.v;i++)
	 {
	 printf("________________________________________\n");
	 	for(int j=0;j<M.v;j++)
		 printf("|%-3d|",M.edge[i][j]); 
		 printf("\n");
		 }
	 printf("________________________________________\n");
} 

//无向图的创建
void create_MGraph(MGraph *M){	 
	int i,j,k;
	printf("请分别输入顶点数和边数：(格式：顶点数，边数)\n");
	scanf("%d%d",&(M->v),&(M->e));
	printf("请输入顶点信息：\n");
	for(i=0;i<M->v;i++)
		scanf("%d",&(M->vexs[i])); //填充顶点表 
		getchar(); 
	printf("请输入每条边对应的两个顶点的序号(格式：为:i,j):\n");
	for(k=0;k<M->e;k++){
		scanf("%d%d",&i,&j);
		M->edge[i-1][j-1]=1;
		M->edge[j-1][i-1]=1;
	}
}
int visit[MaxVertexNum]={0};	//创建全局变量数组visit[],标记以访问节点

//关于邻接矩阵的DFS递归算法
void DFSM1(MGraph M,int V){		 
	visit[V-1]=1;
	printf("%d ",M.vexs[V-1]);
	for(int i=0;i<M.v;i++)
	if(i!=V-1&&visit[i]!=1&&M.edge[V-1][i]==1)
	DFSM(M,i+1);
}

//栈的判空
int Empty_LIFO(LIFO *L){	 
	if(L->top==-1)	return 1;
	else return 0;
}

//创建栈
LIFO* Creat_LIFO(){	 
	LIFO *L;
	L=(LIFO*)malloc(sizeof(LIFO)*MaxVertexNum);
	L->length=MaxVertexNum;
	L->top=-1;
	return L;
}
int Pop_LIFO(LIFO *L,ElemenType *e){		// 出栈 
	if(Empty_LIFO(L))	return 0;
	*e=L->list[L->top];
	L->top--;
	return 1;
}
int Push_LIFO(LIFO *L,ElemenType e){		//压栈
	if(L->top==L->length-1){
		printf("\n栈满，入栈false！\n");
		return 0;
	}
	L->top++;
	L->list[L->top]=e;
}
int getAdjVex(MGraph M,int V){
	for(int i=0;i<M.v;i++)
		if(i!=V-1&&M.edge[V-1][i]==1&&visit[i]==0)
		return  i+1;
	return 0;
}

void DFSM2(MGraph M,int V){		//关于邻接矩阵的DFS非递归算法 
	int i;
	LIFO *L;
	L=Creat_LIFO();
	for(i=0;i<M.v;i++)	//初始化visit数组 
		visit[i]=0;
	printf("%d ",M.vexs[V-1]);
	visit[V-1]=1;
	Push_LIFO(L,V);
	while(!Empty_LIFO(L)||getAdjVex(M,V)){
		if(getAdjVex(M,V)){
			V=getAdjVex(M,V);
			printf("%d ",M.vexs[V-1]);
			visit[V-1]=1;
			Push_LIFO(L,V);
		}
		else if(!Empty_LIFO(L)){
			if(getAdjVex(M,L->list[L->top]))
				V=L->list[L->top];
			else 	Pop_LIFO(L,&V);
		}
	} 
	free(L);
}

测试代码

int main(){
	MGraph M;
	int k,i;
	create_MGraph(&M);
	Mprint(M);
	while(1){
		printf("\n请输入图要遍历的初始点序号：(输入范围：1-n)");
		scanf("%d",&k);
		if(k==-1)break;
		for(i=0;i<5;i++)
		visit[i]=0;
		DFSM2(M,k);	//非递归遍历
	}
	return 0; 
}

/*
1 2
1 3
4 3
3 5
*/