数据结构与算法：SHIYAN3.TXT

#include "stdio.h"
#define MAX_VERTEX_NUM 7
#define MAXQSIZE 7
#define NULL 0
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
int info;
}ArcNode; /*//边结点类型*/
typedef struct VNode{
char data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertices; /*//邻接表*/
int vexnum,arcnum;
}ALGraph;
#define MAXSIZE 100
typedef struct {
int *base;
int front;
int rear;
}SqQueue;
SqQueue Q;
ALGraph G;
void InitQueue ();
void BFS(ALGraph G,int v);
void InitQueue ()
{ Q.base=(int *)malloc(MAXQSIZE*sizeof(int));
if (!Q.base) exit(0);
Q.front=Q.rear=0;
}
int LocateVex(ALGraph G,char u)
{
int i;
for (i=0;i<G.vexnum;i++)
{ if(u==G.vertices[i].data) return i; }
if (i==G.vexnum) {printf("Error u!\n");exit(1);}
return 0;
}
void CreateALGraph_adjlist()
{ int i,j,k,w; char v1,v2;
ArcNode *p;
printf("Input vexnum & arcnum:");
scanf("%d,%d",&G.vexnum,&G.arcnum);
printf("Input Vertices:");
getchar();
for (i=0;i<G.vexnum;i++)
{ scanf("%c",&G.vertices[i].data);
G.vertices[i].firstarc=NULL;
}
printf("Input Arcs(v1,v2 & w):\n");
for (k=0;k<G.arcnum;k++)
{ getchar();
scanf("%c%c",&v1,&v2);
i=LocateVex(G,v1);
j=LocateVex(G,v2);
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
p->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p;
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=i;
p->nextarc=G.vertices[j].firstarc;
G.vertices[j].firstarc=p;
} return;
}
int visited[MAX_VERTEX_NUM];
void DFS(ALGraph G,int v)
{ ArcNode *p;
printf("%c",G.vertices[v].data);
visited[v]=1;
p=G.vertices[v].firstarc;
while (p)
{if (!visited[p->adjvex]) DFS(G,p->adjvex);
p=p->nextarc;
}
}/*//从第v个顶点出发DFS*/
void DFSTraverse()
{ int v;
for (v=0;v<G.vexnum;++v)
visited[v]=0;
for (v=0;v<G.vexnum;++v)
if (!visited[v]) DFS(G,v);
}
void BFSTraverse()
{
int v;
for (v=0;v<G.vexnum;++v)
visited[v]=0;
for (v=0;v<G.vexnum;++v)
if (!visited[v]) BFS(G,v);
}
void BFS(ALGraph G,int v)
{ ArcNode *p;
InitQueue(Q);
printf("%c",G.vertices[v].data);
visited[v]=1;
Q.base[Q.rear]=v;
Q.rear=(Q.rear+1)%MAXQSIZE;
while (Q.front!=Q.rear)
{ v=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
p=G.vertices[v].firstarc;
while (p)
{ if (!visited[p->adjvex])
{ printf("%c",G.vertices[p->adjvex].data);
visited[p->adjvex]=1;
Q.base[Q.rear]=p->adjvex;
Q.rear=(Q.rear+1)%MAXQSIZE;
}
p=p->nextarc;
}
}
}
main()
{
CreateALGraph_adjlist();
DFSTraverse();
BFSTraverse();
}