1.cpp

采用图的邻接表作为图的存储结构

#include<stdio.h>
#include<stdlib.h>
#define maxedgenum 20
#define maxvertex 10
int visited[maxvertex];
int n,e; 
typedef int VertexType;
typedef VertexType vexlist[maxedgenum];
struct edgenode
{
int adjvex;
struct edgenode* next;
};
typedef struct edgenode* adjlist[maxedgenum];
typedef int ElemType;
struct QueueSq{
ElemType *queue;
int front,rear;
int MaxSize;
};
void create(vexlist GV,adjlist GL,int n,int e)
{
	int i,j,k;
	printf("顶点已经编号(0-%d):\n",n-1);
	for(i=0;i<n;i++)
		scanf("%d",&GV[i]);
	for(i=0;i<n;i++)
		GL[i]=NULL;
	printf("输入%d条有向无权边:\n",e);
	for(k=1;k<=e;k++)
	{
		struct edgenode *p;
		scanf("%d %d",&i,&j);
		p=(struct edgenode *)malloc(sizeof(struct edgenode));
		p->adjvex=j;
		p->next=GL[i];
		GL[i]=p;
	}
}
void dfs(adjlist GL,int i,int n)
{
	struct edgenode *p;
	printf("%d",i);
	visited[i]=1;
	p=GL[i];
	while (p!=NULL)
	{
		int j=p->adjvex;
		if (!visited[j])
			dfs(GL,j,n);
		p=p->next;
	}
}
void InitQueuel(struct QueueSq* Q)
{
	Q->MaxSize =10;
	Q->queue =(ElemType *)malloc(10*sizeof(ElemType));
	Q->front =Q->rear =0;
}
void againMalloc(struct QueueSq*Q)
{
	ElemType *p;
	p=(ElemType *)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 [i];
		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 bfs(adjlist GL,int i,int n)
{
	struct QueueSq Q;
	InitQueuel(&Q);
	printf("%d",i);
	visited[i]=1;
	EnQueue(&Q,i);
	while (!EmptyQueue(&Q))
	{
		int k=OutQueue(&Q);
		struct edgenode *p=GL[k];
		while(p!=NULL)
		{
			int j=p->adjvex;
			if (!visited[j])
			{
				printf("%d",j);
				visited[j]=1;
				EnQueue(&Q,j);
			}
			p=p->next;
		}
	}
}
void main()
{
	int i,n,e;
	vexlist gv;
	adjlist gl;
	printf("输入待处理的顶点数和边数:\n");
	scanf("%d %d",&n,&e);
	create(gv,gl,n,e);
	printf("按图的邻接表得到的深度优先遍历序列:\n");
	for(i=0;i<maxvertex;i++)
		visited[i]=0;
	dfs(gl,0,n);
	printf("\n");
	printf("按图的邻接表得到的广度优先遍历序列:\n");
	for(i=0;i<n;i++)
		visited[i]=0;
	bfs(gl,0,n);
	printf("\n");
}