深度优先搜索.c

数据结构学习用到的一些程序！！里面有二叉树相关的几个

#include <stdio.h>
#include <malloc.h>
#define MAX 20                                      //定义最大节点个数
static int visited[MAX];                            //定义访问标志位数组

typedef struct                                      //定义图结构                              
{                                     
	int vexs[MAX];                                  //节点数组和边数组
	int arcs[MAX][MAX];　　　　　　　　　　　　　　 
	int vexnum,arcnum;
}MGraph;

void create(MGraph *G)                              //建立图
{                            
	int i,j;
	int v1,v2;
	printf("输入节点数和边数:\n");
	scanf("%d%d",&(G->vexnum),&(G->arcnum));
	for(i=0;i<G->vexnum;i++)                        //节点依次标号1，2，3，4，5....
	{
		G->vexs[i]=i;
	}
    for(i=0;i<G->vexnum;i++)                        //边数组初始化
		for(j=0;j<G->vexnum;j++)
			G->arcs[i][j]=0;
	printf("输入各边:\n");
	for(i=0;i<G->arcnum;i++)                        //输入边数据，并依此更改边数组
	{
		printf("边 %d: ",i+1);
		scanf("%d%d",&v1,&v2);
		G->arcs[v1-1][v2-1]=1;
		G->arcs[v2-1][v1-1]=1;
	}
	printf("结束建立\n");
	return;
}

int firstVex(MGraph G,int v)                       //查找v的第一个邻接点，并返回位置
{
	int i;
	for(i=0;i<G.vexnum;i++)
		if(G.arcs[v][i]==1)
			return i;
	return -1;
}

int nextVex(MGraph G,int v,int w)                  //查找v相对于w之后的第一个节点，并返回节点位置
{ 
	int i;
	for(i=w+1;i<G.vexnum;i++)
		if(G.arcs[v][i]==1)
			return i;
	return -1;
}

void DFS(MGraph G,int v)                            //深度遍历子函数
{
	int w;
	visited[v]=1;
	printf("%4d",G.vexs[v]+1);
	for(w=firstVex(G,v);w>=0;w=nextVex(G,v,w))
		if(visited[w]==0) DFS(G,w);
}

void main()
{
	int i;
	MGraph G;
	create(&G);
    for(i=0;i<G.vexnum;i++) visited[i]=0;
	for(i=0;i<G.vexnum;i++)
		if(visited[i]==0) DFS(G,i);
	printf("\n");
	return;
}