dfs.cpp

DFS算法的非递归函数 老师布置的

#include<stdio.h>
#define NUM 8
typedef struct ArcCell
{
	int adj;             //
	int info;           //弧相关信息的指针
	
}
ArcCell;
typedef ArcCell AdjMatrix[NUM][NUM];
typedef struct
{
	int vexs[NUM];     //顶点向量 
//	int  visited[5];   //初始化的时候全将其设置为0
	AdjMatrix arcs;       //邻接矩阵 
	int vexnum,arcnum;    //图的当前顶点数和弧数 
	int kind;      //图的种类标志
}MGraph;
int visited[NUM]={0,0,0,0,0,0,0,0};//必须将visited设置为全局变量
MGraph CreateUND()         //创建无向网  用矩阵的存储方式
{
	MGraph G;
	int IncInfo;
	int v1,v2,w;
	int i,j;
	printf("请输入所建立的图:顶点数，弧数：\n");
	scanf("%d,%d,%d",&G.vexnum,&G.arcnum);
	printf("将顶点数组初始化：\n");
	for(i=0;i<G.vexnum;i++)
	{
		scanf("%d",&G.vexs[i]);
	
	}
	for(i=0;i<G.vexnum;i++)
		for(j=0;j<G.vexnum;j++)
		{
			G.arcs[i][j].adj=1000;
			G.arcs[i][j].info=0;
		}
	printf("请输入弧的两个顶点和权数：\n");
	for(int k=0;k<G.arcnum;k++)
	{
		scanf("%d,%d,%d",&v1,&v2,&w);
		i=v1-1;
		j=v2-1;
		G.arcs[j][i].adj=G.arcs[i][j].adj=w;
//		if(IncInfo)
		//G.arcs[j][i]=G.arcs[i][j];

	}
	return G;
}
void VisitFunc(int v)
{
	printf("%d\n",v);

}
int FirstAdjVex(MGraph G,int v)
{
	int re=-1;
	for(int i=0;i<G.vexnum;i++)
	{
		if(G.arcs[v-1][i].adj<1000)
		{
			re=i;
			break;
		}
	}
	return re+1;//如果在邻接矩阵中存在返回该定点   

}
int NextAdjVex(MGraph G,int v,int w)
{
	int re=-1;
	for(int i=w;i<G.vexnum;i++)
	{
		if(G.arcs[v-1][i].adj<1000)
		{
			re=i;
			break;
		}
	}
		return re+1;

}
void DFS(MGraph G, int v) 
{
           // 从顶点v出发，深度优先搜索遍历连通图 G
	
	
    visited[v-1]=1;
//	visited[v] = TRUE;   
    VisitFunc(v);      // 访问第v 个结点
    for(int w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w))
        if (!visited[w-1])  
			DFS(G,w);  
		                            // 对v的尚未访问的邻接顶点w
                                        // 递归调用DFS 
} // DFS
int main()
{
	MGraph G=CreateUND();
	printf("遍历：\n");
	DFS(G,1);

}