#include<stdlib.h>
#define MaxVertexNum 12
#define MaxEdgeNum 20
#define MaxValue 1000
typedef int VertexType;
typedef VertexType vexlist[MaxVertexNum];
typedef int adjmatrix[MaxVertexNum][MaxVertexNum];
int visited[MaxVertexNum]={0};
void Create1(vexlist GV,adjmatrix GA,int n, int e)
{ int i,j,k,w;
printf("输入%d个顶点数据\n",n);
for(i=0;i<n;i++)
scanf("%d",&GV);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(i==j) GA[j]=0;
else GA[j]=MaxValue;
printf("输入%d条有向无权\n",e);
for(k=1;k<=e;k++)
{
scanf("%d %d %d",&i,&j,&w);
GA[j]=GA[j]=w;
}
}
void OutputMatrix(adjmatrix GA,int n)
{ int i,j;
for(i=0;i<n;i++){
for(j=0;j<n;j++)
printf("%d ",GA[j]);
printf("\n");
}
}
void dfs1(adjmatrix GA,int i,int n)
{ int j;
printf(" %d",i);
visited=1;
for(j=0;j<n;j++)
if(GA[j]!=0 && GA[j]!=MaxValue && !visited[j])
dfs1(GA,j,n);
}
typedef int ElemType;
struct QueueSq{
ElemType *queue;
int front,rear;
int MaxSize;
};
void InitQueue1(struct QueueSq* Q)
{
Q->MaxSize=10;
Q->queue=malloc(10*sizeof(ElemType));
Q->fr->rear=0;
}
void againMalloc(struct QueueSq* Q)
{
ElemType *p;
p=realloc(Q->queue,2*Q->MaxSize*sizeof(ElemType));
if(!p){
printf("存储空间用完!\n");
exit(1);
}
Q->queue=p;
if(Q->rear=Q->MaxSize-1){int i;
for(i=0;i<=Q->rear;i++)Q->queue[i+Q->MaxSize]=Q->queue;
Q->rear+=Q->MaxSize;
}
Q->MaxSize=2*Q->MaxSize;
}
void EnQueue(struct QueueSq* Q,ElemType x)
{
if((Q->rear+1)%Q->MaxSize==Q->front) againMalloc(Q);
Q->rear=(Q->rear+1)%Q->MaxSize;
Q->queue[Q->rear]=x;
}
int EmptyQueue(struct QueueSq* Q)
{if(Q->front==Q->rear) return 1;else return 0;
}
ElemType OutQueue(struct QueueSq* Q)
{ if(Q->front==Q->rear)
{
printf("队列已空，无法删除!\n");
exit(1);
}
Q->front=(Q->front+1)%Q->MaxSize;
return Q->queue[Q->front];
}
void bfs1(adjmatrix GA, int i, int n)
{ struct QueueSq Q;
InitQueue1(&Q);
printf("%d",i);
visited=1;
EnQueue(&Q,i);
while (!EmptyQueue(&Q)){
int j;
int k=OutQueue(&Q);
for(j=0;j<n;j++){
if(GA[j]!=0 && GA[k][j]!=MaxValue && !visited[j]){
printf(" %d",j);
visited[j]=1;
EnQueue(&Q,j);
}
}
}
}
void main()
{ int i,n,e;
vexlist gv;
adjmatrix ga;
printf("输入待处理图的顶点数和边数:");
scanf(" %d %d",&n,&e);
Create1(gv,ga,n,e);
OutputMatrix(ga,n);
printf("按图的领接点矩阵得到的深度优先遍历许里序列：\n");
for(i=0;i<MaxVertexNum;i++) visited=0;
dfs1(ga,0,n);
printf("\n");
printf("按图的领接点矩阵得到的广度优先遍历许里序列：\n");
for(i=0;i<n;i++) visited=0;
bfs1(ga,0,n);
printf("\n");
}
最新评论