广度优先搜索.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;

typedef struct QNode                      //图节点
{                     
	int a;
	struct QNode *next;
}QNode;

typedef struct                             //定义对列
{                         
    QNode *head,*last;
}Queue;

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++)             //建立节点数组
	{
		G->vexs[i]=i;　
	}
    for(i=0;i<G->vexnum;i++)
		for(j=0;j<G->vexnum;j++)
			G->arcs[i][j]=0;                 //边数组置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 InitQueue(Queue *Q)                     //建立队列
{
	Q->head=NULL;
	Q->last=NULL;
	return;
}

int EnQueue(Queue *Q,int a)                  //在队列尾部插入a
{
	QNode *temp=malloc(sizeof(QNode));
	if(!temp) 
		return 0;
	temp->a=a;
	temp->next=NULL;
	if(!Q->head)
		Q->head=temp;
	else Q->last->next=temp;
	Q->last=temp;
	return 1;
}

int DeQueue(Queue *Q,int *a)                 //删除队列第一个元素
{
	QNode *temp;
	if(Q->head==NULL)
		return 0;
	temp=Q->head;
	Q->head=temp->next;
	*a=temp->a;
	free(temp);
	return 1;
}

void main(){
	int i,v,u,w;
	MGraph G;
	Queue Q;
	create(&G);
    InitQueue(&Q);
    for(i=0;i<G.vexnum;i++)                       //设置数组visited为各节点遍历情况，未遍历的设为0
		visited[i]=0;               
    for(v=0;v<G.vexnum;v++)
		if(!visited[v])                           //从第一个节点开始遍历，若未遍历，
		{
			visited[v]=1;                         //将标志位置为1
			printf("%4d",G.vexs[v]+1);            //打印节点
			EnQueue(&Q,v);                        //节点入队
			while(Q.head!=NULL)
			{
				DeQueue(&Q,&u);                    //在队列中删去头节点，并用u返回
				for(w=firstVex(G,u);w>=0;w=nextVex(G,u,w))//w为u的第一个邻接点，
					if(!visited[w])                       //若w未遍历过
					{
						visited[w]=1;                     //标志为置1
						printf("%4d",G.vexs[w]+1);        //打印节点 
						EnQueue(&Q,w);                    //入队
					}
			}
		}
	printf("\n");
	return;
}