回复 楼主 风车转风车 89
这是源程序
。。。。。。。。。。。。。。。。。。。。。。。。。。。
程序代码：
#include<stdio.h>
#include<stdlib.h>
#define MAX_VEX_NUM 20
typedef struct arc_node
{
int adjvex;
struct arc_node *next_arc;
int arc_infor;
}arc_node;
typedef struct vex_node
{
int vex;
arc_node *first_arc;
}vex_node;
typedef struct graph
{
int arc_num,vex_num,vex[MAX_VEX_NUM];
int kind;//kind为0为无向图，1为有向图
vex_node *adj_list;
}Graph;
//.................................................创建一个图
int locate_graph(Graph *g,int vex)
{
int i;
for(i=0;i<g->vex_num;i++)
if(g->adj_list[i].vex==vex)
return i;
}//找到定点vex说在邻接矩阵的位置
void creat_graph(Graph *g)//采用临街表寸出土的信息
{
int i,j,k,vex1,vex2;arc_node *s;
printf("输入图的顶点数，边数，和图的类型\n");
scanf("%d%d%d",&(g->vex_num),&(g->arc_num),&(g->kind));
getchar();
printf(" %d %d %d\n",g->vex_num,g->arc_num,g->kind);
for(i=0;i<g->vex_num;i++)
{
printf("输入图的顶点值\n");
scanf("%d",&g->adj_list[i].vex);
getchar();
printf(" %d \n",g->adj_list[i].vex);
g->adj_list[i].first_arc=NULL;
}//初始化邻接矩阵
for(k=0;k<g->arc_num;k++)
{
if(g->kind==0)
{
printf("输入起始顶点vex1和终点vex2的值\n");
scanf("%d%d",&vex1,&vex2);
getchar();
i=locate_graph(g,vex1);
j=locate_graph(g,vex2);
s=(arc_node*)malloc(sizeof(arc_node));
s->adjvex=vex2;
s->next_arc=g->adj_list[i].first_arc;
g->adj_list[i].first_arc=s;
s=(arc_node*)malloc(sizeof(arc_node));
s->adjvex=vex1;//边连接的另一定点
s->next_arc=g->adj_list[j].first_arc;//由此可知先输入的边在邻接表的后面位置
g->adj_list[j].first_arc=s;
}
else // 当为有向图时
{
printf("输入起始顶点vex1和终点vex2的值\n");
scanf("%d%d",&vex1,&vex2);
getchar();
i=locate_graph(g,vex1);
s=(arc_node*)malloc(sizeof(arc_node));
s->adjvex=vex2;
s->next_arc=g->adj_list[i].first_arc;
g->adj_list[i].first_arc=s;
}
}
}
//..............................................创建图完毕
//..................................深度优先搜索
void DFS(Graph *g,int i)
{
arc_node *p;
g->vex[i]=1;
printf(" %d ",g->adj_list[i].vex);
p=g->adj_list[i].first_arc;
while(p!=NULL)
{
if(g->vex[p->adjvex]!=1)
DFS(g,p->adjvex);
p=p->next_arc;
}
}
void DFS_traverse(Graph *g)
{
int i;
for(i=0;i<g->vex_num;i++)
g->vex[i]=-1;
for(i=0;i<g->vex_num;i++)
{
if(g->vex[i]==-1)
DFS(g,i);
}
}
//.........................................................................................
//..................................................广度优先搜索
#define N 30
typedef struct Queue
{
int *base;
int front,rear,size;
}Queue;
void init_queue(Queue *q)
{
q->front=0;
q->rear=0;
q->size=N;
q->base=(int*)malloc(q->size*sizeof(int));
}
void push_queue(Queue *q,int vex)
{
if((q->rear+1)%q->size==q->front)
printf(" the queue is full\n");
else
q->base[q->rear++]=vex;
}
int pop_queue(Queue *q)
{
int vex;
if(q->front=q->front)
printf(" the queue is empty\n");
else
vex=q->base[q->front++];
return vex;
}
void BFS(Graph *g,int i,Queue *q)
{
arc_node *p;
g->vex[i]=1;
printf(" %d ",g->adj_list[i].vex);
push_queue(q,i);
while(q->front!=q->rear)
{
i=pop_queue(q);
p=g->adj_list[i].first_arc;
while(p!=NULL)
{
if(g->vex[p->adjvex]!=1)
{
printf(" %d ",g->adj_list[i].vex);
push_queue(q,p->adjvex);
}
p=p->next_arc;
}
}
}
void BFS_traverse(Graph *g,Queue *q)
{
int i;
init_queue(q);
for(i=0;i<g->vex_num;i++)
g->vex[i]=-1;
for(i=0;i<g->vex_num;i++)
{
if(g->vex[i]==-1)
BFS(g,i,q);
}
}
//...............................................主函数
void main()
{
Graph g1,*g; Queue *q,q1;
g=&g1;q=&q1;
creat_graph(g);
DFS_traverse(g);
printf("...............................................\n");
BFS_traverse(g,q);
}
