图dfs bfs.cpp

数据结构代码（严为民）

#include<stdio.h>
#include"队列int.h"

#define MAX_VERTEX_NUM 20 //最大顶点个数

typedef struct{
char vexs[MAX_VERTEX_NUM]; //顶点向量
int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和弧数
}*mGraph,MGraph;


 int LocateVex(mGraph G,char v)
 { /* 初始条件:图G存在,v和G中顶点有相同特征 */
   /* 操作结果:若G中存在顶点v,则返回该顶点在图中位置;否则返回-1 */
   int i;
   for(i=0;i<G->vexnum;++i)
     if(G->vexs[i]==v)
	 return i;
   return -1;
 }





int FirstAdjVex(mGraph G,int vexl)
 { /* 初始条件: 图G存在,vexl是G中某个顶点 */
   /* 操作结果: 返回vexl的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */
   int i,j=0;
 
   for(i=0;i<G->vexnum;i++)
	   if(G->AdjMatrix[vexl][i]!=j)
		   return i;
   return -1;
 }


int NextAdjVex(mGraph G,int vexl,int w)
 { /* 初始条件: 图G存在,vexl是G中某个顶点,w是vexl的邻接顶点 */
   /* 操作结果: 返回vexl的(相对于w的)下一个邻接顶点的序号, */
   /*           若w是vexl的最后一个邻接顶点,则返回-1 */
   int i,j=0;
  
   for(i=w+1;i<G->vexnum;i++)
     if(G->AdjMatrix[vexl][i]!=j)
       return i;
   return -1;
 }

void CreateUDN(mGraph G)
{int i,j,k,w;char v1,v2;
printf("请输入顶点数和边数:");
	scanf("%d%d",&G->vexnum,&G->arcnum);getchar();
printf("请输入%d个顶点:",G->vexnum);
for(i=0;i<G->vexnum;++i)scanf("%c",&G->vexs[i]);getchar();
for(i=0;i<G->vexnum;++i)
for(j=0;j<G->vexnum;++j)G->AdjMatrix[i][j]=0;

for(k=0;k<G->arcnum;++k){
  printf("请输入两个顶点和权重:"); 
	scanf("%c%c%d",&v1,&v2,&w);
	getchar();

    i=LocateVex(G,v1);j=LocateVex(G,v2);  printf("这两个顶点的编号:%d %d\n",i,j);
	G->AdjMatrix[i][j]=w;
     G->AdjMatrix[j][i]=G->AdjMatrix[i][j];

}

}

int visited[MAX_VERTEX_NUM];
void(*VisitFunc)(mGraph G,int v);

void print(mGraph G,int v)
{printf("%c",G->vexs[v]);}

void DFS(mGraph G,int vexl){// vexl顶点编号
	int w;
      visited[vexl]=1;VisitFunc(G,vexl);
	  for(w=FirstAdjVex(G,vexl);w>=0;w=NextAdjVex(G,vexl,w))
		  if(!visited[w])DFS(G,w);
}



void DFSTraverse(mGraph G,void(*Visit)(mGraph G,int v)){
	VisitFunc=Visit;
      int i;printf("深度优先搜索遍历输出结点:");
      for(i=0;i<G->vexnum;++i)visited[i]=0;
      for(i=0;i<G->vexnum;++i)
		  if(!visited[i])DFS(G,i);
}



void BFSTraverse(mGraph G,void(*Visit)(mGraph G,int v)){
     printf("\n广度优先搜索遍历输出结点:");
	int u,w,v;
	LinkQueue Q;
	for(v=0;v<G->vexnum;++v)visited[v]=0;
    InitQueue(&Q);
    for(v=0;v<G->vexnum;++v)
		if(!visited[v]){
                visited[v]=1;Visit(G,v);
                  EnQueue(&Q,v);
				  while(!QueueEmpty(&Q)){
                       u=DeQueue(&Q);
					   for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
						   if(!visited[w]){
							   visited[w]=1;Visit(G,w);
                               EnQueue(&Q,w);
						   }
				  }
		}
}
                                   
    






void PRINTF(mGraph G)
{
	int i,j;printf("\n");printf("以下是用邻接矩阵表示图结点和权重:\n");printf(" ");
	for(i=0;i<G->vexnum;++i)printf(" %c",G->vexs[i]);
	for(i=0;i<G->vexnum;++i){
	printf("\n");printf("%c",G->vexs[i]);printf(" ");
	for(j=0;j<G->vexnum;++j)printf("%d ",G->AdjMatrix[i][j]);}

printf("\n");
}
 
void main()
{MGraph G;
CreateUDN(&G);
DFSTraverse(&G,print);
BFSTraverse(&G,print);
PRINTF(&G);
}