图的遍历#include<stdio.h>
#include<stdlib.h>
#define max 100 //定义节点最大个数
int tag[100];
typedef char datatype;
/*----------------定义边信息--------------*/
typedef struct node
{
int adress; // 记录节点位子
struct node *next; //指向下一条边的指针
} edgenode;
/*-------------节点元素---定义类型--------------*/
typedef struct vnode
{
datatype element; //节点元素
edgenode *firstedge; //节点所指向的第一条边
int id;
} vexternode;
/*----------------定义邻接表类型--------------*/
typedef struct map
{
vexternode maplist[max]; //存放头结点的顺序表
int n,e; //图的顶点数和边数
} linkmap;
int v[100]={0}; //深度优先遍历中标记已访问的信息
int dv[100]={0}; //广度优先遍历中标记已访问的信息
/*----------------定义建立图--------------*/
linkmap *create(linkmap *maps)
{
int chr[100][2],chh;//chr建立二元组（没权值）
char c[100]; // 存放节点元素
int i,j,m,k;
edgenode *p,*pre;
maps=(linkmap *)malloc(sizeof(linkmap));
printf("***********************************");
printf("\n");
printf("请输入节点个数：");
printf("输入节点个数：");
scanf("%d",&maps->n);
printf("请输入边的个数:");
scanf("%d",&maps->e);
scanf("%c",&chh); //空格
printf("请输入节点元素：");
for(i=0;i<maps->n;i++)
{
scanf("%c",&c[i]);//输入节点元素
scanf("%c",&chh);//空格
maps->maplist[i].element=c[i];//把节点元素存放到邻接表中
maps->maplist[i].firstedge=NULL;
}
printf("请输入二元组（节点与节点之间的关系）\n");
for(i=0;i<maps->e;i++)
for(j=0;j<2;j++)
scanf("%d",&chr[i][j]);
m=0;
for(i=0;i<maps->n;i++)
{
for(k=0;m<maps->e&&chr[m][0]==i;m++,k++)
{
p=(edgenode *)malloc(sizeof(edgenode));
p->adress=chr[m][1]; //边p保存节点位子
if(k==0)
maps->maplist[i].firstedge=p;
else
pre->next=p;
pre=p;
}
p->next=NULL;
}
return maps;
}
/*----------------深度优先-------------*/
void dfs(linkmap *maps,int i)//i用来指定深度优先遍历的起始值
{
edgenode *pp;
printf("%c",maps->maplist[i].element);
v[i]=1;
pp=maps->maplist[i].firstedge;
while(pp)
{
if(!v[pp->adress])
dfs(maps,pp->adress);
pp=pp->next;
}
}
void dfsmap(linkmap *maps)
{
int i=0;
for(i=0;i<maps->n;i++)
v[i]=0;
for(i=0;i<maps->n;i++)
if(!v[i])
{
dfs(maps,i);
}
}
/*----------------广度优先-------------*/
void bfs(linkmap *map,int i)
{
edgenode *p;
int queue[100],front,real,k;
front=-1;
real=-1;
printf("%c",map->maplist[i].element);
dv[i]=1;
queue[++real]=i;
while(front<real)
{
k=queue[++front];
p=map->maplist[k].firstedge;
while(p)
{
if(!dv[p->adress])
{
printf("%c",map->maplist[p->adress].element);
queue[++real]=p->adress;
dv[p->adress]=1;
}
p=p->next;
}
}
}
void bfsmap(linkmap *maps)
{
int i=0;
for(i=0;i<maps->n;i++)
dv[i]=0;
for(i=0;i<maps->n;i++)
if(!dv[i])
bfs(maps,i);
}
/*----------------计算入度数-------------*/
void id(linkmap *maps)
{
int i=0;
edgenode *p=maps->maplist[i].firstedge;
for(i;i<maps->n;i++)
maps->maplist[i].id=0;
for(i=0;i<maps->n;i++)
{
p=maps->maplist[i].firstedge;
while(p)
{
maps->maplist[p->adress].id++;
p=p->next;
}
}
}
/*----------------输出各节点的入度数-------------*/
void print(linkmap *maps)
{
int i=0;
for(i;i<maps->n;i++)
printf("%d",maps->maplist[i].id);
}
/*----------------输出拓扑排序-------------*/
int topsort(linkmap *map)
{
int k=0,i,j,v,tag[100];//tag用来标记是否已访问到
int queue[100];//用队列存储
int front=0,real=0;
edgenode *p;
for(i=0;i<map->n;i++)
{
tag[i]=0;//初始化标记
}
for(i=0;i<map->n;i++)
{
if(map->maplist[i].id==0&&tag[i]==0)
{
queue[++real]=i;//让每一个未被访问到的且入度为0的节点进栈
tag[i]=1;//当节点进栈时，标记此节点被访问过
}
}
while(front<real)//当栈不为空时
{
v=queue[++front];//出栈
printf("%c ",map->maplist[v].element);//输出刚出栈的元素
k++;//用来统计拓扑排序输出的个数
p=map->maplist[v].firstedge; //p指向此节点的下一条边
while(p)
{
j=p->adress;//j记下下一条边所对应节点的位子
if(map->maplist[j].id==0&&tag[j]==0)//下一条边节点入度减一，并判断之后入度是否为零且未被访问过
{
queue[++real]=j;//让每一个未被访问到的且入度为0的节点进栈
tag[j]=1;//进栈……
}
p=p->next;//p指向下一条关联于该节点的边
}
}
return k; //k用来计算输出的个数，并判定了是否有环
}
/*--------图的非递归遍历-------*/
void fdg(linkmap *maps,int i)
{
edgenode *p,*q;
linkmap *m;
int stack[100];
int top=0;
stack[top]=i;
printf("%c ",maps->maplist[i].element);
tag[i]=1;
p=maps->maplist[i].firstedge;
while(top>=0)
{
while(p)
{
if(tag[p->adress]!=1)
printf("%c ",maps->maplist[p->adress].element);
stack[++top]=p->adress;
tag[p->adress]=1;
q=p;
p=maps->maplist[p->adress].firstedge;
if(p&&tag[p->adress]==1)
p=p->next;
}
do{
p=q;
if(top==0)
{ p->adress=stack[top];
top--;
}
else
p->adress=stack[--top];
p=maps->maplist[p->adress].firstedge;
if(top==-1) break;
while(p!=NULL)
{
if(tag[p->adress]==1)
p=p->next;
else
break;
};
}while(!p);
}
}
void fdgsmap(linkmap *maps)
{
int i=0;
for(i=0;i<maps->n;i++)
tag[i]=0;
for(i=0;i<maps->n;i++)
if(!tag[i])
fdg(maps,i);
}
void main()
{
edgenode *p1;
linkmap *maps;
int i=0,c,num;
maps=create(maps);
id(maps);
printf("深度优先遍历结果为：");
dfsmap(maps);
printf("\n广度优先遍历结果为：");
bfsmap(maps);
printf("拓扑排序结果为：");
num=topsort(maps);
if(num==maps->n)
printf("此拓扑排序树无环\n");
else
printf("此拓扑排序树有环\n");
printf(" \n非递归深度优先遍历结果为：");
fdgsmap(maps);
printf("\n");
}
5
402
6KB
2010-05-31
12
