深度优先搜索.txt

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

#include <stdio.h>
#define maxvertexnum 100
#define queuesize 100
#define null 0

typedef struct{
　　int front,rear,count,data[queuesize];
　}cirqueue;//循环队列结构定义

typedef int vertextype;//为了简单，设图中结点的数据为整型
typedef struct node{
　　int adjvex;//存放邻接点序号
　　struct node *next;//指向下一个边结点
　}edgenode;//图的邻接表的边结点定义

typedef struct vnode{
　　vertextype vertex;//顶点数据域
　　edgenode *firstedge;//指向第一个边结点
　}vertexnode;//图的邻接表表示的顶点结点定义

typedef vertexnode adjlist[maxvertexnum];//用向量定义图的邻接表表示的顶点表

typedef struct{
　　adjlist adjlist;
　　int n;//图的顶点数
　　int e;//图的边数
　}algraph;//定义图的邻接表

typedef enum{FALSE,TRUE}boolean;
boolean visited[maxvertexnum];//保存访问信息的布尔向量

main()//主函数
　{//建立图g，并进行深度优先搜索和广度优先搜索
　　algraph *g;
　　g=(algraph*)malloc(sizeof(algraph));//申请图g的邻接表空间
　　createalgraph(g);//建立图g的邻接表表示
　　printf("the dfs is:");/
　　dfstraverse(g);//对图g进行深度优先搜索，并打印搜索序列
　　printf("the bfs is:");
　　bfstraverse(g);//对图g进行广度优先搜索，并打印搜索序列　
　}

createalgraph(algraph *g)
　{//建立图g的邻接表表示
　　int i,j,k;
　　int flag;
　　edgenode *s;
　　printf("\ncreat:\n")//选择建立有向图或无向图
　　printf("digraph--0\n");
　　printf("undigraph--1\n");
　　scanf("%d",&flag);
　　printf("input n,e\n");
　　scanf("%d%d",&g->n,&g->e);//输入图g的顶点数和边数
　　printf("input nodes:\n");
　　for(i=0;i<g->n;i++){//构造一个只含n个顶点，边数为0的图
　　　　scanf("%d",&(g->adjlist[i].vertex));
　　　　　//输入顶点的数据域（为了简单起见，输入为整数）
　　　　g->adjlist[i].firstedge=null;//将顶点结点的firstedge域置为空
　　　}//end for
　　for(k=0;k<g->e;k++){
　　　　printf("input i,j(0~n-1):\n");
　　　　scanf("%d%d",&i,&j);//输入对应于一条边的顶点序号序偶对，要求顶点序号为0~n-1
　　　　s=(edgenode *)malloc(sizeof(edgenode));//申请一个边结点*s
　　　　s->adjvex=j;//将序号j放入边结点*s的adjvex域
　　　　s->next=g->adjlist[i].firstedge;
　　　　　//将边结点*s作为第一个邻接点插入到序号为i的顶点的边表中
　　　　g->adjlist[i].firstedge=s;
　　　　if (flag){//若要建立无向图
　　　　　　s=(edgenode *)malloc(sizeof(edgenode));申请一个边结点*s
　　　　　　s->adjvex=i;//将序号i放入边结点*s的adjvex域
　　　　　　s->next=g->adjlist[j].firstedge;
　　　　　　　//将边结点*s作为第一个邻接点插入到序号为j的顶点的边表中
　　　　　　g->adjlist[j].firstedge=s;
　　　　　}//end of if
　　　}//end of for
　}//end of creatalgraph

dfs(algraph *g,int i)
　{//对图g进行以序号为i的顶点作为出发点深度优先搜索
　　edgenode *p;
　　printf("visit vertex:%d",g->adjlist[i].vertex);//打印序号为i的顶点信息
　　visited[i]=TRUE;//将序号为i的顶点设置已访问过标记
　　p=g->adjlist[i].firstedge;//设置寻找序号为i的第一个未访问过邻接点的扫描指针
　　while(p){
　　　　if (!visited[p->adjvex])//若*p边结点对应顶点（假设序号为j）未访问过
　　　　　　dfs(g,p->adjvex);//对图g进行以序号为j的顶点作为出发点进行深度优先搜索
　　　　p=p->next;//p顺着边表next指针，往后继续寻找
　　　}//end of while
　}//end of dfs

dfstraverse(algraph *g)
　{//对以邻接表表示的图g进行深度优先搜索
　　int i;
　　for(i=0;i<g->n;i++)//将图g的所有顶点设置未访问过标记
　　　　visited[i]=FALSE;
　　for(i=0;i<g->n;i++)//对图g调用dfs函数进行深度优先搜索
　　　if(!visited[i])
　　　　dfs(g,i);
　　printf("\n");
　}//end of dfstraverse

bfs(algraph *g,int k)
　{//对图g进行以序号为k的顶点作为出发点广度优先搜索
　　int i,j;
　　cirqueue *q;//设置循环队列指针
　　edgenode *p;
　　q=(cirqueue *)malloc(sizeof(cirqueue));//申请循环队列空间
　　q->rear=q->front=q->count=0;//将循环队列置为空队
　　printf("visit vertex:%d",g->adjlist[k].vertex);
　　visited[k]=TRUE;//将序号为k的顶点设置为已访问过
　　q->data[q->rear]=k;q->rear=(q->rear+1)%queuesize;q->count++;//将顶点序号k入队
　　while(q->count){//当队列非空时做以下操作
　　　　i=q->data[q->front];q->front=(q->front+1)%queuesize;q->count--;//将队首元素i出队
　　　　p=g->adjlist[i].firstedge;//设置寻找序号为i顶点的未访问过邻接点的扫描指针p
　　　　while (p){//当*p不为空时，做以下操作
　　　　　　if(!visited[p->adjvex]){//若*p边结点对应顶点（假设序号为j）未访问过
　　　　　　　　printf("visit vertex:%d",g->adjlist[p->adjvex].vertex);
　　　　　　　　　　//访问序号为j的顶点
　　　　　　　　visited[p->adjvex]=TRUE;//设置已访问过标记
　　　　　　　　q->data[q->rear]=p->adjvex;q->rear=(q->rear+1)%queuesize;q->count++;
　　　　　　　　　　//将序号为j的顶点入队
　　　　　　　}//end of if
　　　　　　p=p->next;//p顺着边表next指针，往后继续寻找
　　　　　}//end of while
　　　}//end of while
　}//end of bfs

bfstraverse(algraph *g)
　{//对以邻接表表示的图g进行广度优先搜索
　　int i;
　　for(i=0;i<g->n;i++)//将图g的所有顶点设置未访问过标记
　　　visited[i]=FALSE;
　　for(i=0;i<g->n;i++)//对图g调用bfs函数进行广度优先搜索
　　　if(!visited[i])
　　　　bfs(g,i);
　　printf("\n");
　}