#include <stdio.h>
#include <stdlib.h>
#define MAX_NAME 3 /* 顶点字符串的最大长度+1 */
#define MAX_INFO 80 /* 相关信息字符串的最大长度+1 */
#define MAX_VERTEX_NUM 20
#define NULL 0
/* 单链队列－－队列的链式存储结构 */
typedef struct QNode
{
int data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;
typedef char InfoType;
typedef char VertexType[MAX_NAME]; /* 字符串类型 */
/* c7-4.h 无向图的邻接多重表存储表示 */
typedef enum{unvisited,visited}VisitIf;
typedef struct EBox
{
VisitIf mark; /* 访问标记 */
int ivex,jvex; /* 该边依附的两个顶点的位置 */
struct EBox *ilink,*jlink; /* 分别指向依附这两个顶点的下一条边 */
InfoType *info; /* 该边信息指针 */
}EBox;
typedef struct
{
VertexType data;
EBox *firstedge; /* 指向第一条依附该顶点的边 */
}VexBox;
typedef struct
{
VexBox adjmulist[MAX_VERTEX_NUM];
int vexnum,edgenum; /* 无向图的当前顶点数和边数 */
}AMLGraph;
/* 链队列的基本操作 */
InitQueue(LinkQueue *Q)
{ /* 构造一个空队列Q */
(*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));
if(!(*Q).front)
exit(0);
(*Q).front->next=NULL;
return 1;
}
QueueEmpty(LinkQueue Q)
{ /* 若Q为空队列,则返回TRUE,否则返回FALSE */
if(Q.front==Q.rear)
return 1;
else
return -1;
}
EnQueue(LinkQueue *Q,int e)
{ /* 插入元素e为Q的新的队尾元素 */
QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
if(!p) /* 存储分配失败 */
exit(0);
p->data=e;
p->next=NULL;
(*Q).rear->next=p;
(*Q).rear=p;
return 1;
}
DeQueue(LinkQueue *Q,int *e)
{ /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
QueuePtr p;
if((*Q).front==(*Q).rear)
return -1;
p=(*Q).front->next;
*e=p->data;
(*Q).front->next=p->next;
if((*Q).rear==p)
(*Q).rear=(*Q).front;
free(p);
return 1;
}
/* 无向图的邻接多重表存储 */
int LocateVex(AMLGraph G,VertexType u)
{ /* 初始条件: 无向图G存在,u和G中顶点有相同特征 */
/* 操作结果: 若G中存在顶点u,则返回该顶点在无向图中位置;否则返回-1 */
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.adjmulist[i].data)==0)
return i;
return -1;
}
AMLGraph * CreateGraph(AMLGraph *G)
{ /* 采用邻接多重表存储结构,构造无向图G */
int i,j,k,l,IncInfo;
char s[MAX_INFO];
VertexType va,vb;
EBox *p;
printf("请输入无向图G的顶点数,边数: ");
scanf("%d,%d",&(*G).vexnum,&(*G).edgenum);
printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
{
scanf("%s",(*G).adjmulist[i].data);
(*G).adjmulist[i].firstedge=NULL;
}
printf("请顺序输入每条边的两个端点(以空格作为间隔):\n");
for(k=0;k<(*G).edgenum;++k) /* 构造表结点链表 */
{
scanf("%s%s",va,vb); /* 读入两个顶点*/
i=LocateVex(*G,va); /* 一端 */
j=LocateVex(*G,vb); /* 另一端 */
p=(EBox*)malloc(sizeof(EBox));
p->mark=unvisited; /* 设初值 */
p->ivex=i;
p->jvex=j;
p->info=NULL;
p->ilink=(*G).adjmulist[i].firstedge; /* 插在表头 */
(*G).adjmulist[i].firstedge=p;
p->jlink=(*G).adjmulist[j].firstedge; /* 插在表头 */
(*G).adjmulist[j].firstedge=p;
}
return G;
}
VertexType* GetVex(AMLGraph G,int v)
{ /* 初始条件: 无向图G存在,v是G中某个顶点的序号。操作结果: 返回v的值 */
if(v>=G.vexnum||v<0)
exit(0);
return &G.adjmulist[v].data;
}
int visite[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */
int (*VisitFunc)(VertexType v);
void DFS(AMLGraph G,int v)
{
int j;
EBox *p;
VisitFunc(G.adjmulist[v].data);
visite[v]=1;
p=G.adjmulist[v].firstedge;
while(p)
{
j=p->ivex==v?p->jvex:p->ivex;
if(!visite[j])
DFS(G,j);
p=p->ivex==v?p->ilink:p->jlink;
}
}
void DFSTraverse(AMLGraph G,int(*visit)(VertexType))
{ /* 初始条件: 图G存在,Visit是顶点的应用函数。算法7.4 */
/* 操作结果: 从第1个顶点起,深度优先遍历图G,并对每个顶点调用函数Visit */
/* 一次且仅一次。一旦Visit()失败,则操作失败 */
int v;
VisitFunc=visit;
for(v=0;v<G.vexnum;v++)
visite[v]=0;