broad-first-search（adjlgraph）.c

此代码为“图的广度优先遍历”的源代码

#include<stdio.h>
#include<stdlib.h>

#define MaxVertices 20
#define MaxWeight 10000

typedef char DataType;

typedef struct edge
{
	int dest;
	int weight;
	struct edge *next;
}Edge;

typedef struct
{
	DataType data;
	int score;
	Edge *adj;
}AdjLHeight;

typedef struct
{
	int v1;
	int v2;
	int weight;
}EdgeInformation;

typedef struct
{
	AdjLHeight a[MaxVertices];
	int NumOfVertices;
	int NumOfEdges;
}AdjLGraph;


typedef struct QNode
{
	DataType data;
	struct QNode *next;
}QNode;

typedef struct
{
	QNode *front;
	QNode *rear;
}LinkQueue;

int visited[MaxVertices];

void InitiateAdjL(AdjLGraph *G);
void InsertVertex(AdjLGraph *G,int i,DataType vertex);
void DeleteVertex(AdjLGraph *G,int v);
void InsertEdge(AdjLGraph *G,int v1,int v2,int weight);
void DeleteEdge(AdjLGraph *G,int v1,int v2);
int GetFirstVex(AdjLGraph G,int v);
void CreatGraph(AdjLGraph *G,DataType V[],int n,EdgeInformation E[],int e);
int visited[MaxVertices];
void DFSTraverse(AdjLGraph G);
void DFS(AdjLGraph G,int v);

void InitiateQueue(LinkQueue *Q);
int QueueNotEmpty(LinkQueue Q);
void EnQueue(LinkQueue *Q,DataType x);
void DeQueue(LinkQueue *Q,DataType *x);
void GetHead(LinkQueue Q,DataType *x);
int QueueLength(LinkQueue Q);
void DestoryQueue(LinkQueue *Q);
void Visit(DataType x);
void QueueTraverse(LinkQueue Q);


void InitiateQueue(LinkQueue *Q)
{
	Q->front=NULL;
	Q->rear=NULL;
}

int QueueNotEmpty(LinkQueue Q)
{
	if(Q.front==NULL)                            /*可以写作：Q.front==NULL&&Q.rear==NULL，但不能写作：(Q.front==Q.rear)==NULL*/
		return 0;                                    /*判断队列为空，只要Q.front==NULL即可，不需要考虑Q.rear*/
	else return 1;
}

void EnQueue(LinkQueue *Q,DataType x)
{
	QNode *p;                                                 /*原错写成LinkQueue *p！！！注意LinkQueue 和QNode 分别表示的含义！！！*/
	p=(QNode *)malloc(sizeof(QNode));
	if(p==0)
	{printf("Wrong in EnQueue()!\n");exit(0);}
	p->data=x;
	p->next=NULL;
	if(!QueueNotEmpty(*Q))
	{Q->rear=Q->front=p;}
	else
	{
		Q->rear->next=p;
		Q->rear=p;
	}
}		

void DeQueue(LinkQueue *Q,DataType *x)
{
	QNode *p;
	if(!QueueNotEmpty(*Q))
	{
		printf("The queue is empty!(at DeQueue())!\n");exit(0);
	}
	else if(Q->front==Q->rear)
	{
		*x=Q->front->data;                      /*原错写成Q-front.data！！！注意：Q->front也是指针！！！*/
		Q->front=Q->rear=NULL;
	}
	else
	{
		*x=Q->front->data;
		p=Q->front;
		Q->front=Q->front->next;
		free(p);
	}
}

void GetHead(LinkQueue Q,DataType *x)
{
	if(!QueueNotEmpty(Q))
	{
		printf("The queue is empty!(at GetHead())!\n");exit(0);
	}
	else *x=Q.front->data;
}	

int QueueLength(LinkQueue Q)
{
	QNode *p;
	int i=1;
	p=Q.front;
	if(!QueueNotEmpty(Q))
		return 0;
	else
	while(p!=Q.rear)
	{
		p=p->next;
		i++;
	}
	return i;
}
		
void DestoryQueue(LinkQueue *Q)
{
	QNode *p;
	p=Q->front;
	while(QueueNotEmpty(*Q))
	{
		p=Q->front;
		Q->front=Q->front->next;
		free(p);
	}
}

void Visit(DataType x)
{
	printf("%c  ",x);
}

void QueueTraverse(LinkQueue Q)
{
	QNode *q;
	q=Q.front;
	while(q!=NULL)
	{
		Visit(q->data);
		q=q->next;
	}
	printf("\n");
}




void InitiateAdjL(AdjLGraph *G)
{
	int i;
	for(i=0;i<MaxVertices;i++)
	{
		G->a[i].adj=NULL;
		G->a[i].score=i;
	}
	G->NumOfVertices=0;
	G->NumOfEdges=0;
}

void InsertVertex(AdjLGraph *G,int i,DataType vertex)
{
	if(i!=G->NumOfVertices)
	{printf("i is wrong,at InsertVertex().\n");exit(0);}
	G->a[i].data=vertex;
	G->NumOfVertices++;
}

void InsertEdge(AdjLGraph *G,int v1,int v2,int weight)
{
	Edge *p;
	if(v1<0||v1>=G->NumOfVertices||v2<0||v2>=G->NumOfVertices)
	{
		printf("v1 or v2 is wrong,at InsertEdge().\n");
		exit(0);
	}
	p=(Edge *)malloc(sizeof(Edge));
	p->weight=weight;
	p->dest=v2;
	p->next=G->a[v1].adj;
	G->a[v1].adj=p;
	G->NumOfEdges++;
}

void DeleteEdge(AdjLGraph *G,int v1,int v2)
{
	Edge *curr,*pre;
	pre=NULL;
	curr=G->a[v1].adj;
	while(curr->dest!=v2||curr->next!=NULL)
	{
		pre=curr;
		curr=curr->next;
	}
	if(curr==NULL)
	{
		printf("The edge between v1 and v2 is not exist!\n");
		exit(0);
	}
	else if(curr!=NULL&&curr->dest==v2&&pre==NULL)
	{
		G->a[v1].adj=NULL;
		free(curr);
		G->NumOfEdges--;
	}
	else if(curr!=NULL&&curr->dest==v2&&pre!=NULL)
	{
		pre->next=curr->next;
		free(curr);
		G->NumOfEdges--;
	}
}

int GetFirstVex(AdjLGraph G,int v)
{
	Edge *p;
	if(v<0||v>=G.NumOfVertices)
	{
		printf("v is wrong!(at GetFirstVex()).\n");
	     exit(0);
	}
	p=G.a[v].adj;
	if(p!=NULL)
	return p->dest;
	else return -1;
}

int GetNextVex(AdjLGraph G,int v1,int v2)
{
	Edge *curr;
	if(v1<0||v1>=G.NumOfVertices||v2<0||v2>=G.NumOfVertices)
	{
		printf("v1 or is wrong!(at GetNextVex()).\n");
	     exit(0);
	}
	curr=G.a[v1].adj;
	while(curr->dest!=v2&&curr!=NULL)
	{
		curr=curr->next;
	}
	if(curr==NULL)
	{printf("v2 is not adjacent to v1.(at GetNextVex()\n");exit(0);}
	else if(curr->dest==v2&&curr->next==NULL)
		return -1;
	else return curr->next->dest;
}
	
void CreatGraph(AdjLGraph *G,DataType V[],int n,EdgeInformation E[],int e)
{
	int i;
	InitiateAdjL(G);
	for(i=0;i<n;i++)
		InsertVertex(G,i,V[i]);
	for(i=0;i<e;i++)
	     InsertEdge(G,E[i].v1,E[i].v2,E[i].weight);
}

void BFS(AdjLGraph G,int v)               
{
	DataType w,u;     /*不能写为int w,u;否则警告为：Suspicious pointer vonversion in function```*/  
	LinkQueue myqueue;           /*虽然说w,u的类型与下面要得到的int型不相符，但不影响结果*/
	InitiateQueue(&myqueue);
	Visit(G.a[v].data);
	visited[v]=1;
	EnQueue(&myqueue,v);
	while(QueueNotEmpty(myqueue))
	{
		DeQueue(&myqueue,&u);
		w=GetFirstVex(G,u);
		while(w!=-1)
		{
			if(!visited[w])
		     {
				Visit(G.a[w].data);
				visited[w]=1;
			     EnQueue(&myqueue,w);
		     }
			w=GetNextVex(G,u,w);
		}
	}
}


void BFSTraverse(AdjLGraph G)
{
	int i;
	for(i=0;i<G.NumOfVertices;i++)
	visited[i]=0;
	for(i=0;i<G.NumOfVertices;i++)
	if(visited[i]==0)
		BFS(G,i);
}


	
void main()
{
	AdjLGraph mygraph;Edge *curr;
	char vertex[]={'A','B','C','D','E'};
	EdgeInformation Edge[]={{0,1,10},{0,4,20},{0,3,30},{0,2,40},{2,4,50},{3,1,40}};
	int n=5,e=6;int i,j;
	
	CreatGraph(&mygraph,vertex,n,Edge,e); /*原错写成vertex[],Edge[]！！！在函数调用时，应只写数组名，不要把中括号带上！！！*/
	printf("The graph is as follow:\n");
	for(i=0;i<mygraph.NumOfVertices;i++)
	{
		printf("%c   ",mygraph.a[i].data);
		printf("%d  ",mygraph.a[i].score);
		curr=mygraph.a[i].adj;  
		while(curr!=NULL)
		{
			printf("->%d  ",curr->dest);
			curr=curr->next;
		}
		printf("\n");
	}
	
	printf("\n\nMy own to traverse the graph is:\n");
	for(i=0;i<mygraph.NumOfVertices;i++)
	printf("%c   ",mygraph.a[i].data);
	printf("\n");
	
	printf("\n\nThe Breadth First Traverse is:\n");
	BFSTraverse(mygraph);
	printf("\n");
}