1.7 图
1.7.1 图的邻接矩阵存储表示
#include<limits.h> /* INT_MAX等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<math.h> /* floor(),ceil(),abs() */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
#define MAX_NAME 5 /* 顶点字符串的最大长度+1 */
#define MAX_INFO 20 /* 相关信息字符串的最大长度+1 */
typedef int VRType;
typedef char InfoType;
typedef char VertexType[MAX_NAME];
#define INFINITY INT_MAX /* 用整型最大值代替∞ */
#define MAX_VERTEX_NUM 20 /* 最大顶点个数 */
typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */
typedef struct
{
VRType adj; /* 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否； */
/* 对带权图，c则为权值类型 */
InfoType *info; /* 该弧相关信息的指针(可无) */
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM]; /* 顶点向量 */
AdjMatrix arcs; /* 邻接矩阵 */
int vexnum,arcnum; /* 图的当前顶点数和弧数 */
GraphKind kind; /* 图的种类标志 */
}MGraph;
/* 图的数组(邻接矩阵)存储(存储结构由定义)的基本操作*/
int LocateVex(MGraph G,VertexType u)
{ /* 初始条件:图G存在,u和G中顶点有相同特征 */
/* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vexs[i])==0)
return i;
return -1;
}
Status CreateFAG(MGraph *G)
{ /* 采用数组(邻接矩阵)表示法,由文件构造没有相关信息的无向图G */
int i,j,k;
char filename[13];
VertexType va,vb;
FILE *graphlist;
printf("请输入数据文件名(f7-1.dat)：");
scanf("%s",filename);
graphlist=fopen(filename,"r");
fscanf(graphlist,"%d",&(*G).vexnum);
fscanf(graphlist,"%d",&(*G).arcnum);
for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
fscanf(graphlist,"%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i) /* 初始化邻接矩阵 */
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=0; /* 图 */
(*G).arcs[i][j].info=NULL; /* 没有相关信息 */
}
for(k=0;k<(*G).arcnum;++k)
{
fscanf(graphlist,"%s%s",va,vb);
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=1; /* 无向图 */
}
fclose(graphlist);
(*G).kind=AG;
return OK;
}
Status CreateDG(MGraph *G)
{ /* 采用数组(邻接矩阵)表示法,构造有向图G */
int i,j,k,l,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("请输入有向图G的顶点数,弧数,弧是否含其它信息(是:1,否:0): ");
scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i) /* 初始化邻接矩阵 */
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=0; /* 图 */
(*G).arcs[i][j].info=NULL;
}
printf("请输入%d条弧的弧尾 弧头(以空格作为间隔): \n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s%s%*c",va,vb); /* %*c吃掉回车符 */
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=1; /* 有向图 */
if(IncInfo)
{
printf("请输入该弧的相关信息(<%d个字符): ",MAX_INFO);
gets(s);
l=strlen(s);
if(l)
{
info=(char*)malloc((l+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[i][j].info=info; /* 有向 */
}
}
}
(*G).kind=DG;
return OK;
}
Status CreateDN(MGraph *G)
{ /* 采用数组(邻接矩阵)表示法,构造有向网G */
int i,j,k,w,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("请输入有向网G的顶点数,弧数,弧是否含其它信息(是:1,否:0): ");
scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i) /* 初始化邻接矩阵 */
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=INFINITY; /* 网 */
(*G).arcs[i][j].info=NULL;
}
printf("请输入%d条弧的弧尾 弧头 权值(以空格作为间隔): \n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s%s%d%*c",va,vb,&w); /* %*c吃掉回车符 */
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=w; /* 有向网 */
if(IncInfo)
{
printf("请输入该弧的相关信息(<%d个字符): ",MAX_INFO);
gets(s);
w=strlen(s);
if(w)
{
info=(char*)malloc((w+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[i][j].info=info; /* 有向 */
}
}
}
(*G).kind=DN;
return OK;
}
Status CreateAG(MGraph *G)
{ /* 采用数组(邻接矩阵)表示法,构造无向图G */
int i,j,k,l,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("请输入无向图G的顶点数,边数,边是否含其它信息(是:1,否:0): ");
scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i) /* 初始化邻接矩阵 */
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=0; /* 图 */
(*G).arcs[i][j].info=NULL;
}
printf("请输入%d条边的顶点1 顶点2(以空格作为间隔): \n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s%s%*c",va,vb); /* %*c吃掉回车符 */
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=1; /* 无向图 */
if(IncInfo)
{
printf("请输入该边的相关信息(<%d个字符): ",MAX_INFO);
gets(s);
l=strlen(s);
if(l)
{
info=(char*)malloc((l+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[i][j].info=(*G).arcs[j][i].info=info; /* 无向 */
}
}
}
(*G).kind=AG;
return OK;
}
Status CreateAN(MGraph *G)
{ /* 采用数组(邻接矩阵)表示法,构造无向网G。*/
int i,j,k,w,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("请输入无向网G的顶点数,边数,边是否含其它信息(是:1,否:0): ");
scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i) /* 初始化邻接矩阵 */
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=INFINITY; /* 网 */
(*G).arcs[i][j].info=NULL;
}
printf("请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): \n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s%s%d%*c",va,vb,&w); /* %*c吃掉回车符 */
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=w; /* 无向 */
if(IncInfo)
{
printf("请输入该边的相关信息(<%d个字符): ",MAX_INFO);
gets(s);
w=strlen(s);
if(w)
{
info=(char*)malloc((w+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[i][j].info=(*G).arcs[j][i].info=info; /* 无向 */
}
}
}
(*G).kind=AN;
return OK;
}
Status CreateGraph(MGraph *G)
{ /* 采用数组(邻接矩阵)表示法,构造图G。*/
printf("请输入图G的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");
scanf("%d",&(*G).kind);
switch((*G).kind)
{
case DG: return CreateDG(G); /* 构造有向图 */
case DN: return CreateDN(G); /* 构造有向网 */
case AG: return CreateAG(G); /* 构造无向图 */
case AN: return CreateAN(G); /* 构造无向网 */
default: return ERROR;
}
}
void DestroyGraph(MGraph *G)
{ /* 初始条件: 图G存在。操作结果: 销毁图G */
int i,j;
if((*G).kind<2) /* 有向 */
for(i=0;i<(*G).vexnum;i++) /* 释放弧的相关信息(如果有的话) */
{
for(j=0;j<(*G).vexnum;j++)
if((*G).arcs[i][j].adj==1&&(*G).kind==0||(*G).arcs[i][j].adj!=INFINITY&&(*G).kind==1) /* 有向图的弧||有向网的弧 */
if((*G).arcs[i][j].info) /* 有相关信息 */
{
free((*G).arcs[i][j].info);
(*G).arcs[i][j].info=NULL;
}
}
else /* 无向 */
for(i=0;i<(*G).vexnum;i++) /* 释放边的相关信息(如果有的话) */
for(j=i+1;j<(*G).vexnum;j++)
if((*G).arcs[i][j].adj==1&&(*G).kind==2||(*G).arcs[i][j].adj!=INFINITY&&(*G).kind==3) /* 无向图的边||无向网的边 */
if((*G).arcs[i][j].info) /* 有相关信息 */
{
free((*G).arcs[i][j].info);
(*G).arcs[i][j].info=(*G).arcs[j][i].info=NULL;
}
(*G).vexnum=0;
(*G).arcnum=0;
}
VertexType* GetVex(MGraph G,int v)
{ /* 初始条件: 图G存在，v是G中某个顶点的序号。操作结果: 返回v的值 */
if(v>=G.vexnum||v<0)
exit(ERROR);
return &G.vexs[v];
}
Status PutVex(MGraph *G,VertexType v,VertexType value)
{ /* 初始条件: 图G存在，v是G中某个顶点。操作结果: 对v赋新值value */
int k;
k=LocateVex(*G,v); /* k为顶点v在图G中的序号 */
if(k<0)
return ERROR;
strcpy((*G).vexs[k],value);
return OK;
}
int FirstAdjVex(MGraph G,VertexType v)
{ /* 初始条件: 图G存在,v是G中某个顶点 */
/* 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */
int i,j=0,k;
k=LocateVex(G,v); /* k为顶点v在图G中的序号 */
if(G.kind==DN||G.kind==AN) /* 网 */
j=INFINITY;
for(i=0;i<G.vexnum;i++)
if(G.arcs[k][i].adj!=j)
return i;
return -1;
}
int NextAdjVex(MGraph G,VertexType v,VertexType w)
{ /* 初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点 */
/* 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号, */
/* 若w是v的最后一个邻接顶点,则返回-1 */
int i,j=0,k1,k2;
k1=LocateVex(G,v); /* k1为顶点v在图G中的序号 */
k2=LocateVex(G,w); /* k2为顶点w在图G中的序号 */
if(G.kind==DN||G.kind==AN) /* 网 */
j=INFINITY;
for(i=k2+1;i<G.vexnum;i++)
if(G.arcs[k1][i].adj!=j)
return i;
return -1;
}
void InsertVex(MGraph *G,VertexType v)
{ /* 初始条件: 图G存在,v和图G中顶点有相同特征 */
/* 操作结果: 在图G中增添新顶点v(不增添与顶点相关的弧,留待InsertArc()去做) */
int i;
strcpy((*G).vexs[(*G).vexnum],v); /* 构造新顶点向量 */
for(i=0;i<=(*G).vexnum;i++)
{
if((*G).kind%2) /* 网 */
{
(*G).arcs[(*G).vexnum][i].adj=INFINITY; /* 初始化该行邻接矩阵的值(无边或弧) */
(*G).arcs[i][(*G).vexnum].adj=INFINITY; /* 初始化该列邻接矩阵的值(无边或弧) */
}
else /* 图 */
{
(*G).arcs[(*G).vexnum][i].adj=0; /* 初始化该行邻接矩阵的值(无边或弧) */
(*G).arcs[i][(*G).vexnum].adj=0; /* 初始化该列邻接矩阵的值(无边或弧) */
}
(*G).arcs[(*G).vexnum][i].info=NULL; /* 初始化相关信息指针 */
(*G).arcs[i][(*G).vexnum].info=NULL;
}
(*G).vexnum+=1; /* 图G的顶点数加1 */
}
Status DeleteVex(MGraph *G,VertexType v)
{ /* 初始条件: 图G存在,v是G中某个顶点。操作结果: 删除G中顶点v及其相关的弧 */
int i,j,k;
VRType m=0;
k=LocateVex(*G,v); /* k为待删除顶点v的序号 */
if(k<0) /* v不是图G的顶点 */
return ERROR;
if((*G).kind==DN||(*G).kind==AN) /* 网 */
m=INFINITY;
for(j=0;j<(*G).vexnum;j++)
if((*G).arcs[j][k].adj!=m) /* 有入弧或边 */
{
if((*G).arcs[j][k].info) /* 有相关信息 */
free((*G).arcs[j][k].info); /* 释放相关信息 */
(*G).arcnum--; /* 修改弧数 */
}
if((*G).kind==DG||(*G).kind==DN) /* 有向 */
for(j=0;j<(*G).vexnum;j++)
if((*G).arcs[k][j].adj!=m) /* 有出弧 */
{
if((*G).arcs[k][j].info) /* 有相关信息 */
free((*G).arcs[k][j].info); /* 释放相关信息 */
(*G).arcnum--; /* 修改弧数 */
}
for(j=k+1;j<(*G).vexnum;j++) /* 序号k后面的顶点向量依次前移 */
strcpy((*G).vexs[j-1],(*G).vexs[j]);
for(i=0;i<(*G).vexnum;i++)
for(j=k+1;j<(*G).vexnum;j++)
(*G).arcs[i][j-1]=(*G).arcs[i][j]; /* 移动待删除顶点之后的矩阵元素 */
for(i=0;i<(*G).vexnum;i++)
for(j=k+1;j<(*G).vexnum;j++)
(*G).arcs[j-1][i]=(*G).arcs[j][i]; /* 移动待删除顶点之下的矩阵元素 */
(*G).vexnum--; /* 更新图的顶点数 */
return OK;
}
Status InsertArc(MGraph *G,VertexType v,VertexType w)
{ /* 初始条件: 图G存在,v和W是G中两个顶点 */
/* 操作结果: 在G中增添弧<v,w>,若G是无向的,则还增添对称弧<w,v> */
int i,l,v1,w1;
char *info,s[MAX_INFO];
v1=LocateVex(*G,v); /* 尾 */
w1=LocateVex(*G,w); /* 头 */
if(v1<0||w1<0)
return ERROR;
(*G).arcnum++; /* 弧或边数加1 */
if((*G).kind%2) /* 网 */
{
printf("请输入此弧或边的权值: ");
scanf("%d",&(*G).arcs[v1][w1].adj);
}
else /* 图 */
(*G).arcs[v1][w1].adj=1;
printf("是否有该弧或边的相关信息(0:无 1:有): ");
scanf("%d%*c",&i);
if(i)
{
printf("请输入该弧或边的相关信息(<%d个字符)：",MAX_INFO);
gets(s);
l=strlen(s);
if(l)
{
info=(char*)malloc((l+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[v1][w1].info=info;
}
}
if((*G).kind>1) /* 无向 */
{
(*G).arcs[w1][v1].adj=(*G).arcs[v1][w1].adj;
(*G).arcs[w1][v1].info=(*G).arcs[v1][w1].info; /* 指向同一个相关信息 */
}
return OK;
}
Status DeleteArc(MGraph *G,VertexType v,VertexType w)
{ /* 初始条件: 图G存在,v和w是G中两个顶点 */
/* 操作结果: 在G中删除弧<v,w>,若G是无向的,则还删除对称弧<w,v> */
int v1,w1;
v1=LocateVex(*G,v); /* 尾 */
w1=LocateVex(*G,w); /* 头 */
if(v1<0||w1<0) /* v1、w1的值不合法 */
return ERROR;
if((*G).kind%2==0) /* 图 */
(*G).arcs[v1][w1].adj=0;
else /* 网 */
(*G).arcs[v1][w1].adj=INFINITY;
if((*G).arcs[v1][w1].info) /* 有其它信息 */
{
free((*G).arcs[v1][w1].info);
(*G).arcs[v1][w1].info=NULL;
}
if((*G).kind>=2) /* 无向,删除对称弧<w,v> */
{
(*G).arcs[w1][v1].adj=(*G).arcs[v1][w1].adj;
(*G).arcs[w1][v1].info=NULL;
}
(*G).arcnum--;
return OK;
}
Boolean visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */
Status(*VisitFunc)(VertexType); /* 函数变量 */
void DFS(MGraph G,int v)
{ /* 从第v个顶点出发递归地深度优先遍历图G。*/
VertexType w1,v1;
int w;
visited[v]=TRUE; /* 设置访问标志为TRUE(已访问) */
VisitFunc(G.vexs[v]); /* 访问第v个顶点 */
strcpy(v1,*GetVex(G,v));
for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w))))
if(!visited[w])
DFS(G,w); /* 对v的尚未访问的序号为w的邻接顶点递归调用DFS */
}
void DFSTraverse(MGraph G,Status(*Visit)(VertexType))
{ /* 初始条件: 图G存在,Visit是顶点的应用函数。*/
/* 操作结果: 从第1个顶点起,深度优先遍历图G,并对每个顶点调用函数Visit */
/* 一次且仅一次。一旦Visit()失败,则操作失败 */
int v;
VisitFunc=Visit; /* 使用全局变量VisitFunc,使DFS不必设函数指针参数 */
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE; /* 访问标志数组初始化(未被访问) */
for(v=0;v<G.vexnum;v++)
if(!visited[v])
DFS(G,v); /* 对尚未访问的顶点调用DFS */
printf("\n");
}
typedef VRType QElemType; /* 队列类型 */
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;
Status InitQueue(LinkQueue *Q)
{ /* 构造一个空队列Q */
(*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));
if(!(*Q).front)
exit(OVERFLOW);
(*Q).front->next=NULL;
return OK;
}
Status QueueEmpty(LinkQueue Q)
{ /* 若Q为空队列,则返回TRUE,否则返回FALSE */
if(Q.front==Q.rear)
return TRUE;
else
return FALSE;
}
Status EnQueue(LinkQueue *Q,QElemType e)
{ /* 插入元素e为Q的新的队尾元素 */
QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
if(!p) /* 存储分配失败 */
exit(OVERFLOW);
p->data=e;
p->next=NULL;
(*Q).rear->next=p;
(*Q).rear=p;
return OK;
}
Status DeQueue(LinkQueue *Q,QElemType *e)
{ /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
QueuePtr p;
if((*Q).front==(*Q).rear)
return ERROR;
p=(*Q).front->next;
*e=p->data;
(*Q).front->next=p->next;
if((*Q).rear==p)
(*Q).rear=(*Q).front;
free(p);
return OK;
}
void BFSTraverse(MGraph G,Status(*Visit)(VertexType))
{ /* 初始条件: 图G存在,Visit是顶点的应用函数。*/
/* 操作结果: 从第1个顶点起,按广度优先非递归遍历图G,并对每个顶点调用函数 */
/* Visit一次且仅一次。一旦Visit()失败,则操作失败。 */
/* 使用辅助队列Q和访问标志数组visited */
int v,u,w;
VertexType w1,u1;
LinkQueue Q;
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE; /* 置初值 */
InitQueue(&Q); /* 置空的辅助队列Q */
for(v=0;v<G.vexnum;v++)
if(!visited[v]) /* v尚未访问 */
{
visited[v]=TRUE; /* 设置访问标志为TRUE(已访问) */
Visit(G.vexs[v]);
EnQueue(&Q,v); /* v入队列 */
while(!QueueEmpty(Q)) /* 队列不空 */
{
DeQueue(&Q,&u); /* 队头元素出队并置为u */
strcpy(u1,*GetVex(G,u));
for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w))))
if(!visited[w]) /* w为u的尚未访问的邻接顶点的序号 */
{
visited[w]=TRUE;
Visit(G.vexs[w]);
EnQueue(&Q,w);
}
}
}
printf("\n");
}
void Display(MGraph G)
{ /* 输出邻接矩阵G */
int i,j;
char s[7],s1[3];
switch(G.kind)
{
case DG: strcpy(s,"有向图\0");
strcpy(s1,"弧\0");
break;
case DN: strcpy(s,"有向网\0");
strcpy(s1,"弧\0");
break;
case AG: strcpy(s,"无向图\0");
strcpy(s1,"边\0");
break;
case AN: strcpy(s,"无向网\0");
strcpy(s1,"边\0");
}
printf("%d个顶点%d条%s的%s\n",G.vexnum,G.arcnum,s1,s);
for(i=0;i<G.vexnum;++i) /* 输出G.vexs */
printf("G.vexs[%d]=%s\n",i,G.vexs[i]);
printf("G.arcs.adj:\n"); /* 输出G.arcs.adj */
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++)
printf("%6d",G.arcs[i][j].adj);
printf("\n");
}
printf("G.arcs.info:\n"); /* 输出G.arcs.info */
printf("顶点1(弧尾) 顶点2(弧头) 该%s信息：\n",s1);
if(G.kind<2) /* 有向 */
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
{
if(G.arcs[i][j].info)
printf("%5s %11s %s\n",G.vexs[i],G.vexs[j],G.arcs[i][j].info);
}
else /* 无向 */
{
for(i=0;i<G.vexnum;i++)
for(j=i+1;j<G.vexnum;j++)
if(G.arcs[i][j].info)
printf("%5s %11s %s\n",G.vexs[i],G.vexs[j],G.arcs[i][j].info);
}
}
Status visit(VertexType i)
{
printf("%s ",i);
return OK;
}
void main()
{
int i,j,k,n;
VertexType v1,v2;
MGraph g;
CreateFAG(&g);
Display(g);
printf("修改顶点的值，请输入原值 新值: ");
scanf("%s%s",v1,v2);
PutVex(&g,v1,v2);
printf("深度优先搜索的结果:\n");
DFSTraverse(g,visit);
printf("广度优先搜索的结果:\n");
BFSTraverse(g,visit);
printf("删除一条边或弧，请输入待删除边或弧的弧尾 弧头：");
scanf("%s%s",v1,v2);
DeleteArc(&g,v1,v2);
Display(g);
DestroyGraph(&g);
printf("请顺序选择有向图,有向网,无向图,无向网\n");
for(i=0;i<4;i++) /* 验证4种情况 */
{
CreateGraph(&g);
Display(g);
printf("插入新顶点，请输入顶点的值: ");
scanf("%s",v1);
InsertVex(&g,v1);
printf("插入与新顶点有关的弧或边，请输入弧或边数: ");
scanf("%d",&n);
for(k=0;k<n;k++)
{
printf("请输入另一顶点的值: ");
scanf("%s",v2);
if(g.kind<=1) /* 有向 */
{
printf("对于有向图或网，请输入另一顶点的方向(0:弧头 1:弧尾): ");
scanf("%d",&j);
if(j)
InsertArc(&g,v2,v1);
else
InsertArc(&g,v1,v2);
}
else /* 无向 */
InsertArc(&g,v1,v2);
}
Display(g);
printf("删除顶点及相关的弧或边，请输入顶点的值: ");
scanf("%s",v1);
DeleteVex(&g,v1);
Display(g);
DestroyGraph(&g);
}
}运行结果:
1.7.2 图的邻接表存储表示
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<math.h> /* floor(),ceil(),abs() */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
#define MAX_NAME 3 /* 顶点字符串的最大长度+1 */
typedef int InfoType; /* 存放网的权值 */
typedef char VertexType[MAX_NAME]; /* 字符串类型 */
/*图的邻接表存储表示 */
#define MAX_VERTEX_NUM 20
typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */
typedef struct ArcNode
{
int adjvex; /* 该弧所指向的顶点的位置 */
struct ArcNode *nextarc; /* 指向下一条弧的指针 */
InfoType *info; /* 网的权值指针） */
}ArcNode; /* 表结点 */
typedef struct
{
VertexType data; /* 顶点信息 */
ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针 */
}VNode,AdjList[MAX_VERTEX_NUM]; /* 头结点 */
typedef struct
{
AdjList vertices;
int vexnum,arcnum; /* 图的当前顶点数和弧数 */
int kind; /* 图的种类标志 */
}ALGraph;
/* 图的邻接表存储的基本操作*/
int LocateVex(ALGraph G,VertexType u)
{ /* 初始条件: 图G存在,u和G中顶点有相同特征 */
/* 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vertices[i].data)==0)
return i;
return -1;
}
Status CreateGraph(ALGraph *G)
{ /* 采用邻接表存储结构,构造没有相关信息的图G*/
int i,j,k;
int w; /* 权值 */
VertexType va,vb;
ArcNode *p;
printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");
scanf("%d",&(*G).kind);
printf("请输入图的顶点数,边数: ");
scanf("%d,%d",&(*G).vexnum,&(*G).arcnum);
printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
{
scanf("%s",(*G).vertices[i].data);
(*G).vertices[i].firstarc=NULL;
}
if((*G).kind==1||(*G).kind==3) /* 网 */
printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n");
else /* 图 */
printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n");
for(k=0;k<(*G).arcnum;++k) /* 构造表结点链表 */
{
if((*G).kind==1||(*G).kind==3) /* 网 */
scanf("%d%s%s",&w,va,vb);
else /* 图 */
scanf("%s%s",va,vb);
i=LocateVex(*G,va); /* 弧尾 */
j=LocateVex(*G,vb); /* 弧头 */
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
if((*G).kind==1||(*G).kind==3) /* 网 */
{
p->info=(int *)malloc(sizeof(int));
*(p->info)=w;
}
else
p->info=NULL; /* 图 */
p->nextarc=(*G).vertices[i].firstarc; /* 插在表头 */
(*G).vertices[i].firstarc=p;
if((*G).kind>=2) /* 无向图或网,产生第二个表结点 */
{
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=i;
if((*G).kind==3) /* 无向网 */
{
p->info=(int*)malloc(sizeof(int));
*(p->info)=w;
}
else
p->info=NULL; /* 无向图 */
p->nextarc=(*G).vertices[j].firstarc; /* 插在表头 */
(*G).vertices[j].firstarc=p;
}
}
return OK;
}
void DestroyGraph(ALGraph *G)
{ /* 初始条件: 图G存在。操作结果: 销毁图G */
int i;
ArcNode *p,*q;
(*G).vexnum=0;
(*G).arcnum=0;
for(i=0;i<(*G).vexnum;++i)
{
p=(*G).vertices[i].firstarc;
while(p)
{
q=p->nextarc;
if((*G).kind%2) /* 网 */
free(p->info);
free(p);
p=q;
}
}
}
VertexType* GetVex(ALGraph G,int v)
{ /* 初始条件: 图G存在,v是G中某个顶点的序号。操作结果: 返回v的值 */
if(v>=G.vexnum||v<0)
exit(ERROR);
return &G.vertices[v].data;
}
Status PutVex(ALGraph *G,VertexType v,VertexType value)
{ /* 初始条件: 图G存在,v是G中某个顶点 */
/* 操作结果: 对v赋新值value */
int i;
i=LocateVex(*G,v);
if(i>-1) /* v是G的顶点 */
{
strcpy((*G).vertices[i].data,value);
return OK;
}
return ERROR;
}
int FirstAdjVex(ALGraph G,VertexType v)
{ /* 初始条件: 图G存在,v是G中某个顶点 */
/* 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */
ArcNode *p;
int v1;
v1=LocateVex(G,v); /* v1为顶点v在图G中的序号 */
p=G.vertices[v1].firstarc;
if(p)
return p->adjvex;
else
return -1;
}
int NextAdjVex(ALGraph G,VertexType v,VertexType w)
{ /* 初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点 */
/* 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号。 */
/* 若w是v的最后一个邻接点,则返回-1 */
ArcNode *p;
int v1,w1;
v1=LocateVex(G,v); /* v1为顶点v在图G中的序号 */
w1=LocateVex(G,w); /* w1为顶点w在图G中的序号 */
p=G.vertices[v1].firstarc;
while(p&&p->adjvex!=w1) /* 指针p不空且所指表结点不是w */
p=p->nextarc;
if(!p||!p->nextarc) /* 没找到w或w是最后一个邻接点 */
return -1;
else /* p->adjvex==w */
return p->nextarc->adjvex; /* 返回v的(相对于w的)下一个邻接顶点的序号 */
}
void InsertVex(ALGraph *G,VertexType v)
{ /* 初始条件: 图G存在,v和图中顶点有相同特征 */
/* 操作结果: 在图G中增添新顶点v(不增添与顶点相关的弧,留待InsertArc()去做) */
strcpy((*G).vertices[(*G).vexnum].data,v); /* 构造新顶点向量 */
(*G).vertices[(*G).vexnum].firstarc=NULL;
(*G).vexnum++; /* 图G的顶点数加1 */
}
Status DeleteVex(ALGraph *G,VertexType v)
{ /* 初始条件: 图G存在,v是G中某个顶点 */
/* 操作结果: 删除G中顶点v及其相关的弧 */
int i,j;
ArcNode *p,*q;
j=LocateVex(*G,v); /* j是顶点v的序号 */
if(j<0) /* v不是图G的顶点 */
return ERROR;
p=(*G).vertices[j].firstarc; /* 删除以v为出度的弧或边 */
while(p)
{
q=p;
p=p->nextarc;
if((*G).kind%2) /* 网 */
free(q->info);
free(q);
(*G).arcnum--; /* 弧或边数减1 */
}
(*G).vexnum--; /* 顶点数减1 */
for(i=j;i<(*G).vexnum;i++) /* 顶点v后面的顶点前移 */
(*G).vertices[i]=(*G).vertices[i+1];
for(i=0;i<(*G).vexnum;i++) /* 删除以v为入度的弧或边且必要时修改表结点的顶点位置值 */
{
p=(*G).vertices[i].firstarc; /* 指向第1条弧或边 */
while(p) /* 有弧 */
{
if(p->adjvex==j)
{
if(p==(*G).vertices[i].firstarc) /* 待删结点是第1个结点 */
{
(*G).vertices[i].firstarc=p->nextarc;
if((*G).kind%2) /* 网 */
free(p->info);
free(p);
p=(*G).vertices[i].firstarc;
if((*G).kind<2) /* 有向 */
(*G).arcnum--; /* 弧或边数减1 */
}
else
{
q->nextarc=p->nextarc;
if((*G).kind%2) /* 网 */
free(p->info);
free(p);
p=q->nextarc;
if((*G).kind<2) /* 有向 */
(*G).arcnum--; /* 弧或边数减1 */
}
}
else
{
if(p->adjvex>j)
p->adjvex--; /* 修改表结点的顶点位置值(序号) */
q=p;
p=p->nextarc;
}
}
}
return OK;
}
Status InsertArc(ALGraph *G,VertexType v,VertexType w)
{ /* 初始条件: 图G存在,v和w是G中两个顶点 */
/* 操作结果: 在G中增添弧<v,w>,若G是无向的,则还增添对称弧<w,v> */
ArcNode *p;
int w1,i,j;
i=LocateVex(*G,v); /* 弧尾或边的序号 */
j=LocateVex(*G,w); /* 弧头或边的序号 */
if(i<0||j<0)
return ERROR;
(*G).arcnum++; /* 图G的弧或边的数目加1 */
if((*G).kind%2) /* 网 */
{
printf("请输入弧(边)%s→%s的权值: ",v,w);
scanf("%d",&w1);
}
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
if((*G).kind%2) /* 网 */
{
p->info=(int*)malloc(sizeof(int));
*(p->info)=w1;
}
else
p->info=NULL;
p->nextarc=(*G).vertices[i].firstarc; /* 插在表头 */
(*G).vertices[i].firstarc=p;
if((*G).kind>=2) /* 无向,生成另一个表结点 */
{
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=i;
if((*G).kind==3) /* 无向网 */
{
p->info=(int*)malloc(sizeof(int));
*(p->info)=w1;
}
else
p->info=NULL;
p->nextarc=(*G).vertices[j].firstarc; /* 插在表头 */
(*G).vertices[j].firstarc=p;
}
return OK;
}
Status DeleteArc(ALGraph *G,VertexType v,VertexType w)
{ /* 初始条件: 图G存在,v和w是G中两个顶点 */
/* 操作结果: 在G中删除弧<v,w>,若G是无向的,则还删除对称弧<w,v> */
ArcNode *p,*q;
int i,j;
i=LocateVex(*G,v); /* i是顶点v(弧尾)的序号 */
j=LocateVex(*G,w); /* j是顶点w(弧头)的序号 */
if(i<0||j<0||i==j)
return ERROR;
p=(*G).vertices[i].firstarc; /* p指向顶点v的第一条出弧 */
while(p&&p->adjvex!=j) /* p不空且所指之弧不是待删除弧<v,w> */
{ /* p指向下一条弧 */
q=p;
p=p->nextarc;
}
if(p&&p->adjvex==j) /* 找到弧<v,w> */
{
if(p==(*G).vertices[i].firstarc) /* p所指是第1条弧 */
(*G).vertices[i].firstarc=p->nextarc; /* 指向下一条弧 */
else
q->nextarc=p->nextarc; /* 指向下一条弧 */
if((*G).kind%2) /* 网 */
free(p->info);
free(p); /* 释放此结点 */
(*G).arcnum--; /* 弧或边数减1 */
}
if((*G).kind>=2) /* 无向,删除对称弧<w,v> */
{
p=(*G).vertices[j].firstarc; /* p指隙サ鉾的第一条出弧 */
while(p&&p->adjvex!=i) /* p不空且所指之弧不是待删除弧<w,v> */
{ /* p指向下一条弧 */
q=p;
p=p->nextarc;
}
if(p&&p->adjvex==i) /* 找到弧<w,v> */
{
if(p==(*G).vertices[j].firstarc) /* p所指是第1条弧 */
(*G).vertices[j].firstarc=p->nextarc; /* 指向下一条弧 */
else
q->nextarc=p->nextarc; /* 指向下一条弧 */
if((*G).kind==3) /* 无向网 */
free(p->info);
free(p); /* 释放此结点 */
}
}
return OK;
}
Boolean visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */
void(*VisitFunc)(char* v); /* 函数变量(全局量) */
void DFS(ALGraph G,int v)
{ /* 从第v个顶点出发递归地深度优先遍历图G。*/
int w;
VertexType v1,w1;
strcpy(v1,*GetVex(G,v));
visited[v]=TRUE; /* 设置访问标志为TRUE(已访问) */
VisitFunc(G.vertices[v].data); /* 访问第v个顶点 */
for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w))))
if(!visited[w])
DFS(G,w); /* 对v的尚未访问的邻接点w递归调用DFS */
}
void DFSTraverse(ALGraph G,void(*Visit)(char*))
{ /* 对图G作深度优先遍历。*/
int v;
VisitFunc=Visit; /* 使用全局变量VisitFunc,使DFS不必设函数指针参数 */
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE; /* 访问标志数组初始化 */
for(v=0;v<G.vexnum;v++)
if(!visited[v])
DFS(G,v); /* 对尚未访问的顶点调用DFS */
printf("\n");
}
typedef int QElemType; /* 队列类型 */
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;
Status InitQueue(LinkQueue *Q)
{ /* 构造一个空队列Q */
(*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));
if(!(*Q).front)
exit(OVERFLOW);
(*Q).front->next=NULL;
return OK;
}
Status QueueEmpty(LinkQueue Q)
{ /* 若Q为空队列,则返回TRUE,否则返回FALSE */
if(Q.front==Q.rear)
return TRUE;
else
return FALSE;
}
Status EnQueue(LinkQueue *Q,QElemType e)
{ /* 插入元素e为Q的新的队尾元素 */
QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
if(!p) /* 存储分配失败 */
exit(OVERFLOW);
p->data=e;
p->next=NULL;
(*Q).rear->next=p;
(*Q).rear=p;
return OK;
}
Status DeQueue(LinkQueue *Q,QElemType *e)
{ /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
QueuePtr p;
if((*Q).front==(*Q).rear)
return ERROR;
p=(*Q).front->next;
*e=p->data;
(*Q).front->next=p->next;
if((*Q).rear==p)
(*Q).rear=(*Q).front;
free(p);
return OK;
}
void BFSTraverse(ALGraph G,void(*Visit)(char*))
{/*按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。*/
int v,u,w;
VertexType u1,w1;
LinkQueue Q;
for(v=0;v<G.vexnum;++v)
visited[v]=FALSE; /* 置初值 */
InitQueue(&Q); /* 置空的辅助队列Q */
for(v=0;v<G.vexnum;v++) /* 如果是连通图,只v=0就遍历全图 */
if(!visited[v]) /* v尚未访问 */
{
visited[v]=TRUE;
Visit(G.vertices[v].data);
EnQueue(&Q,v); /* v入队列 */
while(!QueueEmpty(Q)) /* 队列不空 */
{
DeQueue(&Q,&u); /* 队头元素出队并置为u */
strcpy(u1,*GetVex(G,u));
for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w))))
if(!visited[w]) /* w为u的尚未访问的邻接顶点 */
{
visited[w]=TRUE;
Visit(G.vertices[w].data);
EnQueue(&Q,w); /* w入队 */
}
}
}
printf("\n");
}
void Display(ALGraph G)
{ /* 输出图的邻接矩阵G */
int i;
ArcNode *p;
switch(G.kind)
{
case DG: printf("有向图\n");
break;
case DN: printf("有向网\n");
break;
case AG: printf("无向图\n");
break;
case AN: printf("无向网\n");
}
printf("%d个顶点：\n",G.vexnum);
for(i=0;i<G.vexnum;++i)
printf("%s ",G.vertices[i].data);
printf("\n%d条弧(边):\n",G.arcnum);
for(i=0;i<G.vexnum;i++)
{
p=G.vertices[i].firstarc;
while(p)
{
if(G.kind<=1) /* 有向 */
{
printf("%s→%s ",G.vertices[i].data,G.vertices[p->adjvex].data);
if(G.kind==DN) /* 网 */
printf(":%d ",*(p->info));
}
else /* 无向(避免输出两次) */
{
if(i<p->adjvex)
{
printf("%s－%s ",G.vertices[i].data,G.vertices[p->adjvex].data);
if(G.kind==AN) /* 网 */
printf(":%d ",*(p->info));
}
}
p=p->nextarc;
}
printf("\n");
}
}
void print(char *i)
{
printf("%s ",i);
}
void main()
{
int i,j,k,n;
ALGraph g;
VertexType v1,v2;
printf("请选择有向图\n");
CreateGraph(&g);
Display(g);
printf("删除一条边或弧，请输入待删除边或弧的弧尾 弧头：");
scanf("%s%s",v1,v2);
DeleteArc(&g,v1,v2);
printf("修改顶点的值，请输入原值 新值: ");
scanf("%s%s",v1,v2);
PutVex(&g,v1,v2);
printf("插入新顶点，请输入顶点的值: ");
scanf("%s",v1);
InsertVex(&g,v1);
printf("插入与新顶点有关的弧或边，请输入弧或边数: ");
scanf("%d",&n);
for(k=0;k<n;k++)
{
printf("请输入另一顶点的值: ");
scanf("%s",v2);
printf("对于有向图，请输入另一顶点的方向(0:弧头 1:弧尾): ");
scanf("%d",&j);
if(j)
InsertArc(&g,v2,v1);
else
InsertArc(&g,v1,v2);
}
Display(g);
printf("删除顶点及相关的弧或边，请输入顶点的值: ");
scanf("%s",v1);
DeleteVex(&g,v1);
Display(g);
printf("深度优先搜索的结果:\n");
DFSTraverse(g,print);
printf("广度优先搜索的结果:\n");
BFSTraverse(g,print);
DestroyGraph(&g);
printf("请顺序选择有向网,无向图,无向网\n");
for(i=0;i<3;i++) /* 验证另外3种情况 */
{
CreateGraph(&g);
Display(g);
printf("插入新顶点，请输入顶点的值: ");
scanf("%s",v1);
InsertVex(&g,v1);
printf("插入与新顶点有关的弧或边，请输入弧或边数: ");
scanf("%d",&n);
for(k=0;k<n;k++)
{
printf("请输入另一顶点的值: ");
scanf("%s",v2);
if(g.kind<=1) /* 有向 */
{
printf("对于有向图或网，请输入另一顶点的方向(0:弧头 1:弧尾): ");
scanf("%d",&j);
if(j)
InsertArc(&g,v2,v1);
else
InsertArc(&g,v1,v2);
}
else /* 无向 */
InsertArc(&g,v1,v2);
}
Display(g);
printf("删除顶点及相关的弧或边，请输入顶点的值: ");
scanf("%s",v1);
DeleteVex(&g,v1);
Display(g);
DestroyGraph(&g);
}
}运行结果:
1.7.3 有向图的十字链表存储表示
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<math.h> /* floor(),ceil(),abs() */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
typedef char InfoType;
#define MAX_Info 80 /* 信息字符串最大长度+1 */
#define MAX_VERTEX_NAME 3 /* 顶点字符串最大长度+1 */
typedef char VertexType[MAX_VERTEX_NAME];
/* c7-3.h 有向图的十字链表存储表示 */
#define MAX_VERTEX_NUM 20
typedef struct ArcBox
{
int tailvex,headvex; /* 该弧的尾和头顶点的位置 */
struct ArcBox *hlink,*tlink; /* 分别为弧头相同和弧尾相同的弧的链域 */
InfoType *info; /* 该弧相关信息的指针(可无) */
}ArcBox; /* 弧结点 */
typedef struct
{
VertexType data;
ArcBox *firstin,*firstout; /* 分别指向该顶点第一条入弧和出弧 */
}VexNode; /* 顶点结点 */
typedef struct
{
VexNode xlist[MAX_VERTEX_NUM]; /* 表头向量(数组) */
int vexnum,arcnum; /* 有向图的当前顶点数和弧数 */
}OLGraph;
/* bo7-3.c 有向图的十字链表存储(存储结构由c7-3.h定义)的基本函数(15个) */
int LocateVex(OLGraph G,VertexType u)
{ /* 返回顶点u在有向图G中的位置(序号),如不存在则返回-1 */
int i;
for(i=0;i<G.vexnum;++i) /* 用循环查找该结点 */
if(!strcmp(G.xlist[i].data,u))
return i;
return -1;
}
Status CreateDG(OLGraph *G)
{ /* 采用十字链表存储表示,构造有向图G。算法7.3 */
int i,j,k;
int IncInfo;
char str[MAX_Info];
ArcBox *p;
VertexType v1,v2;
printf("请输入有向图的顶点数,弧数,弧是否含其它信息(是:1，否:0): ");
scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_VERTEX_NAME);
for(i=0;i<(*G).vexnum;++i)
{ /* 构造表头向量 */
scanf("%s",&(*G).xlist[i].data); /* 输入顶点值 */
(*G).xlist[i].firstin=NULL; /* 初始化指针 */
(*G).xlist[i].firstout=NULL;
}
printf("请输入%d条弧的弧尾和弧头(空格为间隔):\n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{ /* 输入各弧并构造十字链表 */
scanf("%s%s",&v1,&v2);
i=LocateVex(*G,v1); /* 确定v1和v2在G中的位置 */
j=LocateVex(*G,v2);
p=(ArcBox *)malloc(sizeof(ArcBox)); /* 产生弧结点(假定有足够空间) */
p->tailvex=i; /* 对弧结点赋值 */
p->headvex=j;
p->hlink=(*G).xlist[j].firstin; /* 完成在入弧和出弧链表表头的插入 */
p->tlink=(*G).xlist[i].firstout;
(*G).xlist[j].firstin=(*G).xlist[i].firstout=p;
if(IncInfo)
{ /* 若弧含有相关信息，则输入 */
printf("请输入该弧的相关信息(<%d个字符): ",MAX_Info);
scanf("%s",str);
p->info=(InfoType *)malloc((strlen(str)+1)*sizeof(InfoType));
strcpy(p->info,str);
}
else /* 弧不含有相关信息 */
p->info=NULL;
}
return OK;
}
void DestroyGraph(OLGraph *G)
{ /* 初始条件: 有向图G存在 */
/* 操作结果: 销毁有向图G */
int j;
ArcBox *p,*q;
for(j=0;j<(*G).vexnum;j++) /* 对所有顶点 */
{
p=(*G).xlist[j].firstout; /* 仅处理出弧 */
while(p)
{
q=p;
p=p->tlink;
if(q->info)
free(q->info);
free(q);
}
}
(*G).arcnum=0;
(*G).vexnum=0;
}
VertexType* GetVex(OLGraph G,int v)
{ /* 初始条件:有向图G存在,v是G中某个顶点的序号。操作结果:返回v的值 */
if(v>=G.vexnum||v<0)
exit(ERROR);
return &G.xlist[v].data;
}
Status PutVex(OLGraph *G,VertexType v,VertexType value)
{ /* 初始条件: 有向图G存在,v是G中某个顶点 */
/* 操作结果: 对v赋新值value */
int i;
i=LocateVex(*G,v);
if(i<0) /* v不是G的顶点 */
return ERROR;
strcpy((*G).xlist[i].data,value);
return OK;
}
int FirstAdjVex(OLGraph G,VertexType v)
{ /* 初始条件: 有向图G存在,v是G中某个顶点 */
/* 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */
int i;
ArcBox *p;
i=LocateVex(G,v);
p=G.xlist[i].firstout; /* p指向顶点v的第1个出弧 */
if(p)
return p->headvex;
else
return -1;
}
int NextAdjVex(OLGraph G,VertexType v,VertexType w)
{ /* 初始条件: 有向图G存在,v是G中某个顶点,w是v的邻接顶点 */
/* 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号, */
/* 若w是v的最后一个邻接顶点,则返回-1 */
int i,j;
ArcBox *p;
i=LocateVex(G,v); /* i是顶点v的序号 */
j=LocateVex(G,w); /* j是顶点w的序号 */
p=G.xlist[i].firstout; /* p指向顶点v的第1个出弧 */
while(p&&p->headvex!=j)
p=p->tlink;
if(p) /* w不是v的最后一个邻接顶点 */
p=p->tlink; /* p指向相对于w的下一个邻接顶点 */
if(p) /* 有下一个邻接顶点 */
return p->headvex;
else
return -1;
}
void InsertVex(OLGraph *G,VertexType v)
{ /* 初始条件: 有向图G存在,v和有向图G中顶点有相同特征 */
/* 操作结果: 在有向图G中增添新顶点v(不增添与顶点相关的弧,留待InsertArc()去做) */
strcpy((*G). xlist[(*G). vexnum].data,v);
(*G). xlist[(*G). vexnum].firstin=(*G). xlist[(*G). vexnum].firstout=NULL;
(*G). vexnum++;
}
Status DeleteVex(OLGraph *G,VertexType v)
{ /* 初始条件: 有向图G存在,v是G中某个顶点 */
/* 操作结果: 删除G中顶点v及其相关的弧 */
int j,k;
ArcBox *p,*q;
k=LocateVex(*G,v); /* k是顶点v的序号 */
if(k<0) /* v不是图G的顶点 */
return ERROR;
/* 以下删除顶点v的出弧 */
for(j=0;j<(*G). vexnum;j++) /* 顶点v的出弧是其它顶点的入弧 */
{
if(j==k)
continue;
p=(*G). xlist[j].firstin; /* 在其它顶点的入弧链表中删除顶点v的出弧 */
while(p)
if(p->tailvex==k&&p==(*G). xlist[j].firstin) /* 待删结点为首结点 */
{
(*G). xlist[j].firstin=p->hlink;
break;
}
else if(p->tailvex!=k) /* 没找到待删结点 */
{
q=p;
p=p->hlink;
}
else /* 找到待删结点且不是首结点 */
{
q->hlink=p->hlink;
break;
}
}
p=(*G). xlist[k].firstout; /* 删除与顶点v有关的出弧 */
while(p)
{
q=p->tlink; /* q指向p的下一个出弧 */
if(p->info) /* 释放p */
free(p->info);
free(p);
(*G). arcnum--;
p=q;
}
/* 以下删除顶点v的入弧 */
for(j=0;j<(*G). vexnum;j++) /* 顶点v的入弧是其它顶点的出弧 */
{
if(j==k)
continue;
p=(*G). xlist[j].firstout; /* 在其它顶点的出弧链表中删除顶点v的入弧 */
while(p)
if(p->headvex==k&&p==(*G). xlist[j].firstout) /* 待删结点为首结点 */
{
(*G). xlist[j].firstout=p->tlink;
break;
}
else if(p->headvex!=k) /* 没找到待删结点 */
{
q=p;
p=p->tlink;
}
else /* 找到待删结点且不是首结点 */
{
q->tlink=p->tlink;
break;
}
}
p=(*G). xlist[k].firstin; /* 删除与顶点v有关的入弧 */
while(p)
{
q=p->hlink; /* q指向p的下一个入弧 */
if(p->info) /* 释放p */
free(p->info);
free(p);
(*G). arcnum--;
p=q;
}
for(j=k+1;j<(*G). vexnum;j++) /* 序号>k的顶点依次向前移 */
(*G). xlist[j-1]=(*G). xlist[j];
(*G). vexnum--; /* 顶点数减1 */
for(j=0;j<(*G). vexnum;j++) /* 结点序号>k的要减1 */
{
p=(*G). xlist[j].firstout; /* 处理出弧 */
while(p)
{
if(p->tailvex>k)
p->tailvex--; /* 序号-1 */
if(p->headvex>k)
p->headvex--; /* 序号-1 */
p=p->tlink;
}
}
return OK;
}
Status InsertArc(OLGraph *G,VertexType v,VertexType w)
{ /* 初始条件: 有向图G存在,v和w是G中两个顶点 */
/* 操作结果: 在G中增添弧<v,w> */
int i,j;
int IncInfo;
char str[MAX_Info];
ArcBox *p;
i=LocateVex(*G,v); /* 弧尾的序号 */
j=LocateVex(*G,w); /* 弧头的序号 */
if(i<0||j<0)
return ERROR;
p=(ArcBox *)malloc(sizeof(ArcBox)); /* 生成新结点 */
p->tailvex=i; /* 给新结点赋值 */
p->headvex=j;
p->hlink=(*G). xlist[j].firstin; /* 插在入弧和出弧的链头 */
p->tlink=(*G). xlist[i].firstout;
(*G). xlist[j].firstin=(*G). xlist[i].firstout=p;
(*G). arcnum++; /* 弧数加1 */
printf("要插入的弧是否含有其它信息(是: 1,否: 0): ");
scanf("%d",&IncInfo);
if(IncInfo)
{
printf("请输入该弧的相关信息(<%d个字符): ",MAX_Info);
scanf("%s",str);
p->info=(InfoType *)malloc((strlen(str)+1)*sizeof(InfoType));
strcpy(p->info,str);
}
else
p->info=NULL;
return OK;
}
Status DeleteArc(OLGraph *G,VertexType v,VertexType w)
{ /* 初始条件: 有向图G存在,v和w是G中两个顶点 */
/* 操作结果: 在G中删除弧<v,w> */
int i,j;
ArcBox *p1,*p2;
i=LocateVex(*G,v); /* 弧尾的序号 */
j=LocateVex(*G,w); /* 弧头的序号 */
if(i<0||j<0||i==j)
return ERROR;
p2=(*G). xlist[i].firstout; /* 将弧结点从出弧链表中删去 */
if(p2&&p2->headvex==j) /* 第1个结点为待删除结点 */
(*G). xlist[i].firstout=p2->tlink;
else
{
while(p2&&p2->headvex!=j) /* 向后找 */
{
p1=p2;
p2=p2->tlink;
}
if(p2) /* 没到表尾 */
p1->tlink=p2->tlink;
}
p2=(*G). xlist[j].firstin; /* 将弧结点从入弧链表中删去 */
if(p2&&p2->tailvex==i)
(*G). xlist[j].firstin=p2->hlink;
else
{
while(p2&&p2->tailvex!=i)
{
p1=p2;
p2=p2->hlink;
}
if(p2) /* 没到表尾 */
p1->hlink=p2->hlink;
}
if(p2->info) /* 释放弧结点 */
free(p2->info);
free(p2);
(*G). arcnum--; /* 弧数减1 */
return OK;
}
Boolean visited[MAX_VERTEX_NUM]; /* 访问标志数组 */
Status(*VisitFunc)(VertexType); /* 函数变量 */
void DFS(OLGraph G,int i) /* DFSTraverse()调用 */
{
ArcBox *p;
visited[i]=TRUE; /* 访问标志数组置1(已被访问) */
VisitFunc(G.xlist[i].data); /* 遍历第i个顶点 */
p=G.xlist[i].firstout; /* p指向第i个顶点的出度 */
while(p&&visited[p->headvex]) /* p没到表尾且该弧的头顶点已被访问 */
p=p->tlink; /* 查找下一个结点 */
if(p&&!visited[p->headvex]) /* 该弧的头顶点未被访问 */
DFS(G,p->headvex); /* 递归调用DFS() */
}
void DFSTraverse(OLGraph G,Status(*Visit)(VertexType))
{ /* 初始条件: 有向图G存在,v是G中某个顶点,Visit是顶点的应用函数 */
/* 操作结果: 从第1个顶点起,按深度优先递归遍历有向图G,并对每个顶点调用 */
/* 函数Visit一次且仅一次。一旦Visit()失败,则操作失败 */
int i;
for(i=0;i<G.vexnum;i++)
visited[i]=FALSE; /* 访问标志数组置初值(未被访问) */
VisitFunc=Visit;
for(i=0;i<G.vexnum;i++) /* 由序号0开始,继续查找未被访问过的顶点 */
if(!visited[i])
DFS(G,i);
printf("\n");
}
typedef int QElemType;
/* c3-3.h 队列的顺序存储结构(可用于循环队列和非循环队列) */
#define MAXQSIZE 5 /* 最大队列长度(对于循环队列，最大队列长度要减1) */
typedef struct
{
QElemType *base; /* 初始化的动态分配存储空间 */
int front; /* 头指针,若队列不空,指向队列头元素 */
int rear; /* 尾指针,若队列不空,指向队列尾元素的下一个位置 */
}SqQueue;
/* bo3-3.c 循环队列(存储结构由c3-3.h定义)的基本操作(9个) */
Status InitQueue(SqQueue *Q)
{ /* 构造一个空队列Q */
(*Q).base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));
if(!(*Q).base) /* 存储分配失败 */
exit(OVERFLOW);
(*Q).front=(*Q).rear=0;
return OK;
}
Status QueueEmpty(SqQueue Q)
{ /* 若队列Q为空队列,则返回TRUE,否则返回FALSE */
if(Q.front==Q.rear) /* 队列空的标志 */
return TRUE;
else
return FALSE;
}
Status EnQueue(SqQueue *Q,QElemType e)
{ /* 插入元素e为Q的新的队尾元素 */
if(((*Q).rear+1)%MAXQSIZE==(*Q).front) /* 队列满 */
return ERROR;
(*Q).base[(*Q).rear]=e;
(*Q).rear=((*Q).rear+1)%MAXQSIZE;
return OK;
}
Status DeQueue(SqQueue *Q,QElemType *e)
{ /* 若队列不空,则删除Q的队头元素,用e返回其值,并返回OK;否则返回ERROR */
if((*Q).front==(*Q).rear) /* 队列空 */
return ERROR;
*e=(*Q).base[(*Q).front];
(*Q).front=((*Q).front+1)%MAXQSIZE;
return OK;
}
void BFSTraverse(OLGraph G,Status(*Visit)(VertexType))
{ /* 初始条件: 有向图G存在,Visit是顶点的应用函数。算法7.6 */
/* 操作结果: 从第1个顶点起,按广度优先非递归遍历有向图G,并对每个顶点调用 */
/* 函数Visit一次且仅一次。一旦Visit()失败,则操作失败。 */
/* 使用辅助队列Q和访问标志数组visited */
int v,u,w;
VertexType u1,w1;
SqQueue Q;
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE;
InitQueue(&Q);
for(v=0;v<G.vexnum;v++)
if(!visited[v])
{
visited[v]=TRUE;
Visit(G.xlist[v].data);
EnQueue(&Q,v);
while(!QueueEmpty(Q))
{
DeQueue(&Q,&u);
strcpy(u1,*GetVex(G,u));
for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w))))
if(!visited[w]) /* w为u的尚未访问的邻接顶点的序号 */
{
visited[w]=TRUE;
Visit(G.xlist[w].data);
EnQueue(&Q,w);
}
}
}
printf("\n");
}
void Display(OLGraph G)
{ /* 输出有向图G */
int i;
ArcBox *p;
printf("共%d个顶点,%d条弧:\n",G.vexnum,G.arcnum);
for(i=0;i<G.vexnum;i++)
{
printf("顶点%s: 入度: ",G.xlist[i].data);
p=G.xlist[i].firstin;
while(p)
{
printf("%s ",G.xlist[p->tailvex].data);
p=p->hlink;
}
printf("出度: ");
p=G.xlist[i].firstout;
while(p)
{
printf("%s ",G.xlist[p->headvex].data);
if(p->info) /* 该弧有相关信息 */
printf("弧信息: %s ",p->info);
p=p->tlink;
}
printf("\n");
}
}
Status visit(VertexType v)
{
printf("%s ",v);
return OK;
}
void main()
{
int j,k,n;
OLGraph g;
VertexType v1,v2;
CreateDG(&g);
Display(g);
printf("修改顶点的值，请输入原值 新值: ");
scanf("%s%s",v1,v2);
PutVex(&g,v1,v2);
printf("插入新顶点，请输入顶点的值: ");
scanf("%s",v1);
InsertVex(&g,v1);
printf("插入与新顶点有关的弧，请输入弧数: ");
scanf("%d",&n);
for(k=0;k<n;k++)
{
printf("请输入另一顶点的值 另一顶点的方向(0:弧头 1:弧尾): ");
scanf("%s%d",v2,&j);
if(j)
InsertArc(&g,v2,v1);
else
InsertArc(&g,v1,v2);
}
Display(g);
printf("删除一条弧，请输入待删除弧的弧尾 弧头：");
scanf("%s%s",v1,v2);
DeleteArc(&g,v1,v2);
Display(g);
printf("删除顶点及相关的弧，请输入顶点的值: ");
scanf("%s",v1);
DeleteVex(&g,v1);
Display(g);
printf("深度优先搜索的结果:\n");
DFSTraverse(g,visit);
printf("广度优先搜索的结果:\n");
BFSTraverse(g,visit);
DestroyGraph(&g);
}运行结果:
1.7.4 无向图的邻接多重表存储表示
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<math.h> /* floor(),ceil(),abs() */
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
#define MAX_NAME 3 /* 顶点字符串的最大长度+1 */
#define MAX_INFO 80 /* 相关信息字符串的最大长度+1 */
typedef char InfoType;
typedef char VertexType[MAX_NAME]; /* 字符串类型 */
#define MAX_VERTEX_NUM 20
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;
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;
}
Status CreateGraph(AMLGraph *G)
{ /* 采用邻接多重表存储结构,构造无向图G */
int i,j,k,l,IncInfo;
char s[MAX_INFO];
VertexType va,vb;
EBox *p;
printf("请输入无向图G的顶点数,边数,边是否含其它信息(是:1，否:0): ");
scanf("%d,%d,%d",&(*G).vexnum,&(*G).edgenum,&IncInfo);
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%*c",va,vb); /* %*c吃掉回车符 */
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;
if(IncInfo) /* 边有相关信息 */
{
printf("请输入该弧的相关信息(<%d个字符)：",MAX_INFO);
gets(s);
l=strlen(s);
if(l)
{
p->info=(char*)malloc((l+1)*sizeof(char));
strcpy(p->info,s);
}
}
}
return OK;
}
VertexType* GetVex(AMLGraph G,int v)
{ /* 初始条件: 无向图G存在,v是G中某个顶点的序号。操作结果: 返回v的值 */
if(v>=G.vexnum||v<0)
exit(ERROR);
return &G.adjmulist[v].data;
}
Status PutVex(AMLGraph *G,VertexType v,VertexType value)
{ /* 初始条件: 无向图G存在,v是G中某个顶点 */
/* 操作结果: 对v赋新值value */
int i;
i=LocateVex(*G,v);
if(i<0) /* v不是G的顶点 */
return ERROR;
strcpy((*G).adjmulist[i].data,value);
return OK;
}
int FirstAdjVex(AMLGraph G,VertexType v)
{ /* 初始条件: 无向图G存在,v是G中某个顶点 */
/* 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */
int i;
i=LocateVex(G,v);
if(i<0)
return -1;
if(G.adjmulist[i].firstedge) /* v有邻接顶点 */
if(G.adjmulist[i].firstedge->ivex==i)
return G.adjmulist[i].firstedge->jvex;
else
return G.adjmulist[i].firstedge->ivex;
else
return -1;
}
int NextAdjVex(AMLGraph G,VertexType v,VertexType w)
{ /* 初始条件: 无向图G存在,v是G中某个顶点,w是v的邻接顶点 */
/* 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号。 */
/* 若w是v的最后一个邻接点,则返回-1 */
int i,j;
EBox *p;
i=LocateVex(G,v); /* i是顶点v的序号 */
j=LocateVex(G,w); /* j是顶点w的序号 */
if(i<0||j<0) /* v或w不是G的顶点 */
return -1;
p=G.adjmulist[i].firstedge; /* p指向顶点v的第1条边 */
while(p)
if(p->ivex==i&&p->jvex!=j) /* 不是邻接顶点w(情况1) */
p=p->ilink; /* 找下一个邻接顶点 */
else if(p->jvex==i&&p->ivex!=j) /* 不是邻接顶点w(情况2) */
p=p->jlink; /* 找下一个邻接顶点 */
else /* 是邻接顶点w */
break;
if(p&&p->ivex==i&&p->jvex==j) /* 找到邻接顶点w(情况1) */
{
p=p->ilink;
if(p&&p->ivex==i)
return p->jvex;
else if(p&&p->jvex==i)
return p->ivex;
}
if(p&&p->ivex==j&&p->jvex==i) /* 找到邻接顶点w(情况2) */
{
p=p->jlink;
if(p&&p->ivex==i)
return p->jvex;
else if(p&&p->jvex==i)
return p->ivex;
}
return -1;
}
Status InsertVex(AMLGraph *G,VertexType v)
{ /* 初始条件: 无向图G存在,v和G中顶点有相同特征 */
/* 操作结果: 在G中增添新顶点v(不增添与顶点相关的弧,留待InsertArc()去做) */
if((*G).vexnum==MAX_VERTEX_NUM) /* 结点已满，不能插入 */
return ERROR;
if(LocateVex(*G,v)>=0) /* 结点已存在,不能插入 */
return ERROR;
strcpy((*G).adjmulist[(*G).vexnum].data,v);
(*G).adjmulist[(*G).vexnum].firstedge=NULL;
(*G).vexnum++;
return OK;
}
Status DeleteArc(AMLGraph *G,VertexType v,VertexType w)
{ /* 初始条件: 无向图G存在,v和w是G中两个顶点 */
/* 操作结果: 在G中删除弧<v,w> */
int i,j;
EBox *p,*q;
i=LocateVex(*G,v);
j=LocateVex(*G,w);
if(i<0||j<0||i==j)
return ERROR; /* 图中没有该点或弧 */
/* 以下使指向待删除边的第1个指针绕过这条边 */
p=(*G).adjmulist[i].firstedge; /* p指向顶点v的第1条边 */
if(p&&p->jvex==j) /* 第1条边即为待删除边(情况1) */
(*G).adjmulist[i].firstedge=p->ilink;
else if(p&&p->ivex==j) /* 第1条边即为待删除边(情况2) */
(*G).adjmulist[i].firstedge=p->jlink;
else /* 第1条边不是待删除边 */
{
while(p) /* 向后查找弧<v,w> */
{
if(p->ivex==i&&p->jvex!=j) /* 不是待删除边 */
{
q=p;
p=p->ilink; /* 找下一个邻接顶点 */
}
else if(p->jvex==i&&p->ivex!=j) /* 不是待删除边 */
{
q=p;
p=p->jlink; /* 找下一个邻接顶点 */
}
else /* 是邻接顶点w */
break;
}
if(!p) /* 没找到该边 */
return ERROR;
if(p->ivex==i&&p->jvex==j) /* 找到弧<v,w>(情况1) */
if(q->ivex==i)
q->ilink=p->ilink;
else
q->jlink=p->ilink;
else if(p->ivex==j&&p->jvex==i) /* 找到弧<v,w>(情况2) */
if(q->ivex==i)
q->ilink=p->jlink;
else
q->jlink=p->jlink;
}
/* 以下由另一顶点起找待删除边且删除之 */
p=(*G).adjmulist[j].firstedge; /* p指向顶点w的第1条边 */
if(p->jvex==i) /* 第1条边即为待删除边(情况1) */
{
(*G).adjmulist[j].firstedge=p->ilink;
if(p->info) /* 有相关信息 */
free(p->info);
free(p);
}
else if(p->ivex==i) /* 第1条边即为待删除边(情况2) */
{
(*G).adjmulist[j].firstedge=p->jlink;
if(p->info) /* 有相关信息 */
free(p->info);
free(p);
}
else /* 第1条边不是待删除边 */
{
while(p) /* 向后查找弧<v,w> */
if(p->ivex==j&&p->jvex!=i) /* 不是待删除边 */
{
q=p;
p=p->ilink; /* 找下一个邻接顶点 */
}
else if(p->jvex==j&&p->ivex!=i) /* 不是待删除边 */
{
q=p;
p=p->jlink; /* 找下一个邻接顶点 */
}
else /* 是邻接顶点v */
break;
if(p->ivex==i&&p->jvex==j) /* 找到弧<v,w>(情况1) */
{
if(q->ivex==j)
q->ilink=p->jlink;
else
q->jlink=p->jlink;
if(p->info) /* 有相关信息 */
free(p->info);
free(p);
}
else if(p->ivex==j&&p->jvex==i) /* 找到弧<v,w>(情况2) */
{
if(q->ivex==j)
q->ilink=p->ilink;
else
q->jlink=p->ilink;
if(p->info) /* 有相关信息 */
free(p->info);
free(p);
}
}
(*G).edgenum--;
return OK;
}
Status DeleteVex(AMLGraph *G,VertexType v)
{ /* 初始条件: 无向图G存在,v是G中某个顶点 */
/* 操作结果: 删除G中顶点v及其相关的边 */
int i,j;
VertexType w;
EBox *p;
i=LocateVex(*G,v); /* i为待删除顶点的序号 */
if(i<0)
return ERROR;
for(j=0;j<(*G).vexnum;j++) /* 删除与顶点v相连的边(如果有的话) */
{
if(j==i)
continue;
strcpy(w,*GetVex(*G,j)); /* w是第j个顶点的值 */
DeleteArc(G,v,w);
}
for(j=i+1;j<(*G).vexnum;j++) /* 排在顶点v后面的顶点的序号减1 */
(*G).adjmulist[j-1]=(*G).adjmulist[j];
(*G).vexnum--; /* 顶点数减1 */
for(j=i;j<(*G).vexnum;j++) /* 修改顶点的序号 */
{
p=(*G).adjmulist[j].firstedge;
if(p)
{
if(p->ivex==j+1)
{
p->ivex--;
p=p->ilink;
}
else
{
p->jvex--;
p=p->jlink;
}
}
}
return OK;
}
void DestroyGraph(AMLGraph *G)
{
int i;
for(i=(*G).vexnum-1;i>=0;i--)
DeleteVex(G,(*G).adjmulist[i].data);
}
Status InsertArc(AMLGraph *G,VertexType v,VertexType w)
{ /* 初始条件: 无向图G存在,v和W是G中两个顶点 */
/* 操作结果: 在G中增添弧<v,w> */
int i,j,l,IncInfo;
char s[MAX_INFO];
EBox *p;
i=LocateVex(*G,v); /* 一端 */
j=LocateVex(*G,w); /* 另一端 */
if(i<0||j<0)
return ERROR;
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;
printf("该边是否有相关信息(1:有 0:无): ");
scanf("%d%*c",&IncInfo); /* 吃掉回车符 */
if(IncInfo) /* 边有相关信息 */
{
printf("请输入该边的相关信息(<%d个字符)：",MAX_INFO);
gets(s);
l=strlen(s);
if(l)
{
p->info=(char*)malloc((l+1)*sizeof(char));
strcpy(p->info,s);
}
}
(*G).edgenum++;
return OK;
}
Boolean visite[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */
Status(*VisitFunc)(VertexType v);
void DFS(AMLGraph G,int v)
{
int j;
EBox *p;
VisitFunc(G.adjmulist[v].data);
visite[v]=TRUE;
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,Status(*visit)(VertexType))
{ /* 初始条件: 图G存在,Visit是顶点的应用函数。*/
/* 操作结果: 从第1个顶点起,深度优先遍历图G,并对每个顶点调用函数Visit */
/* 一次且仅一次。一旦Visit()失败,则操作失败 */
int v;
VisitFunc=visit;
for(v=0;v<G.vexnum;v++)
visite[v]=FALSE;
for(v=0;v<G.vexnum;v++)
if(!visite[v])
DFS(G,v);
printf("\n");
}
typedef int QElemType; /* 队列类型 */
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;
Status InitQueue(LinkQueue *Q)
{ /* 构造一个空队列Q */
(*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));
if(!(*Q).front)
exit(OVERFLOW);
(*Q).front->next=NULL;
return OK;
}
Status QueueEmpty(LinkQueue Q)
{ /* 若Q为空队列,则返回TRUE,否则返回FALSE */
if(Q.front==Q.rear)
return TRUE;
else
return FALSE;
}
Status EnQueue(LinkQueue *Q,QElemType e)
{ /* 插入元素e为Q的新的队尾元素 */
QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
if(!p) /* 存储分配失败 */
exit(OVERFLOW);
p->data=e;
p->next=NULL;
(*Q).rear->next=p;
(*Q).rear=p;
return OK;
}
Status DeQueue(LinkQueue *Q,QElemType *e)
{ /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
QueuePtr p;
if((*Q).front==(*Q).rear)
return ERROR;
p=(*Q).front->next;
*e=p->data;
(*Q).front->next=p->next;
if((*Q).rear==p)
(*Q).rear=(*Q).front;
free(p);
return OK;
}
void BFSTraverse(AMLGraph G,Status(*Visit)(VertexType))
{ /* 初始条件: 图G存在,Visit是顶点的应用函数。*/
/* 操作结果: 从第1个顶点起,按广度优先非递归遍历图G,并对每个顶点调用函数 */
/* Visit一次且仅一次。一旦Visit()失败,则操作失败。 */
/* 使用辅助队列Q和访问标志数组visite */
int v,u,w;
VertexType w1,u1;
LinkQueue Q;
for(v=0;v<G.vexnum;v++)
visite[v]=FALSE; /* 置初值 */
InitQueue(&Q); /* 置空的辅助队列Q */
for(v=0;v<G.vexnum;v++)
if(!visite[v]) /* v尚未访问 */
{
visite[v]=TRUE; /* 设置访问标志为TRUE(已访问) */
Visit(G.adjmulist[v].data);
EnQueue(&Q,v); /* v入队列 */
while(!QueueEmpty(Q)) /* 队列不空 */
{
DeQueue(&Q,&u); /* 队头元素出队并置为u */
strcpy(u1,*GetVex(G,u));
for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w))))
if(!visite[w]) /* w为u的尚未访问的邻接顶点的序号 */
{
visite[w]=TRUE;
Visit(G.adjmulist[w].data);
EnQueue(&Q,w);
}
}
}
printf("\n");
}
void MarkUnvizited(AMLGraph G)
{ /* 置边的访问标记为未被访问 */
int i;
EBox *p;
for(i=0;i<G.vexnum;i++)
{
p=G.adjmulist[i].firstedge;
while(p)
{
p->mark=unvisited;
if(p->ivex==i)
p=p->ilink;
else
p=p->jlink;
}
}
}
void Display(AMLGraph G)
{ /* 输出无向图的邻接多重表G */
int i;
EBox *p;
MarkUnvizited(G); /* 置边的访问标记为未被访问 */
printf("%d个顶点：\n",G.vexnum);
for(i=0;i<G.vexnum;++i)
printf("%s ",G.adjmulist[i].data);
printf("\n%d条边:\n",G.edgenum);
for(i=0;i<G.vexnum;i++)
{
p=G.adjmulist[i].firstedge;
while(p)
if(p->ivex==i) /* 边的i端与该顶点有关 */
{
if(!p->mark) /* 只输出一次 */
{
printf("%s－%s ",G.adjmulist[i].data,G.adjmulist[p->jvex].data);
p->mark=visited;
if(p->info) /* 输出附带信息 */
printf("相关信息: %s ",p->info);
}
p=p->ilink;
}
else /* 边的j端与该顶点有关 */
{
if(!p->mark) /* 只输出一次 */
{
printf("%s－%s ",G.adjmulist[p->ivex].data,G.adjmulist[i].data);
p->mark=visited;
if(p->info) /* 输出附带信息 */
printf("相关信息: %s ",p->info);
}
p=p->jlink;
}
printf("\n");
}
}
Status visit(VertexType v)
{
printf("%s ",v);
return OK;
}
void main()
{
int k,n;
AMLGraph g;
VertexType v1,v2;
CreateGraph(&g);
Display(g);
printf("修改顶点的值，请输入原值 新值: ");
scanf("%s%s",v1,v2);
PutVex(&g,v1,v2);
printf("插入新顶点，请输入顶点的值: ");
scanf("%s",v1);
InsertVex(&g,v1);
printf("插入与新顶点有关的边，请输入边数: ");
scanf("%d",&n);
for(k=0;k<n;k++)
{
printf("请输入另一顶点的值: ");
scanf("%s",v2);
InsertArc(&g,v1,v2);
}
Display(g);
printf("深度优先搜索的结果:\n");
DFSTraverse(g,visit);
printf("广度优先搜索的结果:\n");
BFSTraverse(g,visit);
DestroyGraph(&g);
}运行结果:
1.7.5 最小生成树
#include<limits.h> /* INT_MAX等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<math.h> /* floor(),ceil(),abs() */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int VRType;
typedef char InfoType;
#define MAX_NAME 3 /* 顶点字符串的最大长度+1 */
#define MAX_INFO 20 /* 相关信息字符串的最大长度+1 */
typedef char VertexType[MAX_NAME];
#define INFINITY INT_MAX /* 用整型最大值代替∞ */
#define MAX_VERTEX_NUM 20 /* 最大顶点个数 */
typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */
typedef struct
{
VRType adj; /* 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否； */
/* 对带权图，c则为权值类型 */
InfoType *info; /* 该弧相关信息的指针(可无) */
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM]; /* 顶点向量 */
AdjMatrix arcs; /* 邻接矩阵 */
int vexnum,arcnum; /* 图的当前顶点数和弧数 */
GraphKind kind; /* 图的种类标志 */
}MGraph;
/*图的数组(邻接矩阵)存储(存储结构由c7-1.h定义)的基本操作*/
int LocateVex(MGraph G,VertexType u)
{ /* 初始条件:图G存在,u和G中顶点有相同特征 */
/* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vexs[i])==0)
return i;
return -1;
}
Status CreateAN(MGraph *G)
{ /* 采用数组(邻接矩阵)表示法,构造无向网G。*/
int i,j,k,w,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("请输入无向网G的顶点数,边数,边是否含其它信息(是:1,否:0): ");
scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i) /* 初始化邻接矩阵 */
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=INFINITY; /* 网 */
(*G).arcs[i][j].info=NULL;
}
printf("请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): \n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s%s%d%*c",va,vb,&w); /* %*c吃掉回车符 */
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=w; /* 无向 */
if(IncInfo)
{
printf("请输入该边的相关信息(<%d个字符): ",MAX_INFO);
gets(s);
w=strlen(s);
if(w)
{
info=(char*)malloc((w+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[i][j].info=(*G).arcs[j][i].info=info; /* 无向 */
}
}
}
(*G).kind=AN;
return OK;
}
typedef struct
{ /* 记录从顶点集U到V-U的代价最小的边的辅助数组定义 */
VertexType adjvex;
VRType lowcost;
}minside[MAX_VERTEX_NUM];
int minimum(minside SZ,MGraph G)
{ /* 求closedge.lowcost的最小正值 */
int i=0,j,k,min;
while(!SZ[i].lowcost)
i++;
min=SZ[i].lowcost; /* 第一个不为0的值 */
k=i;
for(j=i+1;j<G.vexnum;j++)
if(SZ[j].lowcost>0)
if(min>SZ[j].lowcost)
{
min=SZ[j].lowcost;
k=j;
}
return k;
}
void MiniSpanTree_PRIM(MGraph G,VertexType u)
{ /* 用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边*/
int i,j,k;
minside closedge;
k=LocateVex(G,u);
for(j=0;j<G.vexnum;++j) /* 辅助数组初始化 */
{
if(j!=k)
{
strcpy(closedge[j].adjvex,u);
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
closedge[k].lowcost=0; /* 初始,U={u} */
printf("最小代价生成树的各条边为:\n");
for(i=1;i<G.vexnum;++i)
{ /* 选择其余G.vexnum-1个顶点 */
k=minimum(closedge,G); /* 求出T的下一个结点：第K顶点 */
printf("(%s-%s)\n",closedge[k].adjvex,G.vexs[k]); /* 输出生成树的边 */
closedge[k].lowcost=0; /* 第K顶点并入U集 */
for(j=0;j<G.vexnum;++j)
if(G.arcs[k][j].adj<closedge[j].lowcost)
{ /* 新顶点并入U集后重新选择最小边 */
strcpy(closedge[j].adjvex,G.vexs[k]);
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
}
void main()
{
MGraph G;
CreateAN(&G);
MiniSpanTree_PRIM(G,G.vexs[0]);
}运行结果:
1.7.6 关节点和重连通分量
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<math.h> /* floor(),ceil(),abs() */
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
#define MAX_NAME 2 /* 顶点字符串的最大长度+1 */
typedef int InfoType;
typedef char VertexType[MAX_NAME]; /* 字符串类型 */
#define MAX_VERTEX_NUM 20
typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */
typedef struct ArcNode
{
int adjvex; /* 该弧所指向的顶点的位置 */
struct ArcNode *nextarc; /* 指向下一条弧的指针 */
InfoType *info; /* 网的权值指针） */
}ArcNode; /* 表结点 */
typedef struct
{
VertexType data; /* 顶点信息 */
ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针 */
}VNode,AdjList[MAX_VERTEX_NUM]; /* 头结点 */
typedef struct
{
AdjList vertices;
int vexnum,arcnum; /* 图的当前顶点数和弧数 */
int kind; /* 图的种类标志 */
}ALGraph;
int LocateVex(ALGraph G,VertexType u)
{ /* 初始条件: 图G存在,u和G中顶点有相同特征 */
/* 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vertices[i].data)==0)
return i;
return -1;
}
Status CreateGraph(ALGraph *G)
{ /* 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图) */
int i,j,k;
int w; /* 权值 */
VertexType va,vb;
ArcNode *p;
printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");
scanf("%d",&(*G).kind);
printf("请输入图的顶点数,边数: ");
scanf("%d,%d",&(*G).vexnum,&(*G).arcnum);
printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
{
scanf("%s",(*G).vertices[i].data);
(*G).vertices[i].firstarc=NULL;
}
if((*G).kind==1||(*G).kind==3) /* 网 */
printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n");
else /* 图 */
printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n");
for(k=0;k<(*G).arcnum;++k) /* 构造表结点链表 */
{
if((*G).kind==1||(*G).kind==3) /* 网 */
scanf("%d%s%s",&w,va,vb);
else /* 图 */
scanf("%s%s",va,vb);
i=LocateVex(*G,va); /* 弧尾 */
j=LocateVex(*G,vb); /* 弧头 */
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
if((*G).kind==1||(*G).kind==3) /* 网 */
{
p->info=(int *)malloc(sizeof(int));
*(p->info)=w;
}
else
p->info=NULL; /* 图 */
p->nextarc=(*G).vertices[i].firstarc; /* 插在表头 */
(*G).vertices[i].firstarc=p;
if((*G).kind>=2) /* 无向图或网,产生第二个表结点 */
{
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=i;
if((*G).kind==3) /* 无向网 */
{
p->info=(int*)malloc(sizeof(int));
*(p->info)=w;
}
else
p->info=NULL; /* 无向图 */
p->nextarc=(*G).vertices[j].firstarc; /* 插在表头 */
(*G).vertices[j].firstarc=p;
}
}
return OK;
}
VertexType* GetVex(ALGraph G,int v)
{ /* 初始条件: 图G存在,v是G中某个顶点的序号。操作结果: 返回v的值 */
if(v>=G.vexnum||v<0)
exit(ERROR);
return &G.vertices[v].data;
}
int FirstAdjVex(ALGraph G,VertexType v)
{ /* 初始条件: 图G存在,v是G中某个顶点 */
/* 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */
ArcNode *p;
int v1;
v1=LocateVex(G,v); /* v1为顶点v在图G中的序号 */
p=G.vertices[v1].firstarc;
if(p)
return p->adjvex;
else
return -1;
}
int NextAdjVex(ALGraph G,VertexType v,VertexType w)
{ /* 初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点 */
/* 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号。 */
/* 若w是v的最后一个邻接点,则返回-1 */
ArcNode *p;
int v1,w1;
v1=LocateVex(G,v); /* v1为顶点v在图G中的序号 */
w1=LocateVex(G,w); /* w1为顶点w在图G中的序号 */
p=G.vertices[v1].firstarc;
while(p&&p->adjvex!=w1) /* 指针p不空且所指表结点不是w */
p=p->nextarc;
if(!p||!p->nextarc) /* 没找到w或w是最后一个邻接点 */
return -1;
else /* p->adjvex==w */
return p->nextarc->adjvex; /* 返回v的(相对于w的)下一个邻接顶点的序号 */
}
Boolean visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */
void(*VisitFunc)(char* v); /* 函数变量(全局量) */
void DFS(ALGraph G,int v)
{ /* 从第v个顶点出发递归地深度优先遍历图G。*/
int w;
VertexType v1,w1;
strcpy(v1,*GetVex(G,v));
visited[v]=TRUE; /* 设置访问标志为TRUE(已访问) */
VisitFunc(G.vertices[v].data); /* 访问第v个顶点 */
for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w))))
if(!visited[w])
DFS(G,w); /* 对v的尚未访问的邻接点w递归调用DFS */
}
typedef int QElemType; /* 队列类型 */
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;
Status InitQueue(LinkQueue *Q)
{ /* 构造一个空队列Q */
(*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));
if(!(*Q).front)
exit(OVERFLOW);
(*Q).front->next=NULL;
return OK;
}
Status QueueEmpty(LinkQueue Q)
{ /* 若Q为空队列,则返回TRUE,否则返回FALSE */
if(Q.front==Q.rear)
return TRUE;
else
return FALSE;
}
Status EnQueue(LinkQueue *Q,QElemType e)
{ /* 插入元素e为Q的新的队尾元素 */
QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
if(!p) /* 存储分配失败 */
exit(OVERFLOW);
p->data=e;
p->next=NULL;
(*Q).rear->next=p;
(*Q).rear=p;
return OK;
}
Status DeQueue(LinkQueue *Q,QElemType *e)
{ /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
QueuePtr p;
if((*Q).front==(*Q).rear)
return ERROR;
p=(*Q).front->next;
*e=p->data;
(*Q).front->next=p->next;
if((*Q).rear==p)
(*Q).rear=(*Q).front;
free(p);
return OK;
}
void BFSTraverse(ALGraph G,void(*Visit)(char*))
{/*按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。*/
int v,u,w;
VertexType u1,w1;
LinkQueue Q;
for(v=0;v<G.vexnum;++v)
visited[v]=FALSE; /* 置初值 */
InitQueue(&Q); /* 置空的辅助队列Q */
for(v=0;v<G.vexnum;v++) /* 如果是连通图,只v=0就遍历全图 */
if(!visited[v]) /* v尚未访问 */
{
visited[v]=TRUE;
Visit(G.vertices[v].data);
EnQueue(&Q,v); /* v入队列 */
while(!QueueEmpty(Q)) /* 队列不空 */
{
DeQueue(&Q,&u); /* 队头元素出队并置为u */
strcpy(u1,*GetVex(G,u));
for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w))))
if(!visited[w]) /* w为u的尚未访问的邻接顶点 */
{
visited[w]=TRUE;
Visit(G.vertices[w].data);
EnQueue(&Q,w); /* w入队 */
}
}
}
printf("\n");
}
void Display(ALGraph G)
{ /* 输出图的邻接矩阵G */
int i;
ArcNode *p;
switch(G.kind)
{
case DG: printf("有向图\n");
break;
case DN: printf("有向网\n");
break;
case AG: printf("无向图\n");
break;
case AN: printf("无向网\n");
}
printf("%d个顶点：\n",G.vexnum);
for(i=0;i<G.vexnum;++i)
printf("%s ",G.vertices[i].data);
printf("\n%d条弧(边):\n",G.arcnum);
for(i=0;i<G.vexnum;i++)
{
p=G.vertices[i].firstarc;
while(p)
{
if(G.kind<=1) /* 有向 */
{
printf("%s→%s ",G.vertices[i].data,G.vertices[p->adjvex].data);
if(G.kind==DN) /* 网 */
printf(":%d ",*(p->info));
}
else /* 无向(避免输出两次) */
{
if(i<p->adjvex)
{
printf("%s－%s ",G.vertices[i].data,G.vertices[p->adjvex].data);
if(G.kind==AN) /* 网 */
printf(":%d ",*(p->info));
}
}
p=p->nextarc;
}
printf("\n");
}
}
int count; /* 全局量count对访问计数 */
int low[MAX_VERTEX_NUM];
void DFSArticul(ALGraph G,int v0)
{ /* 从第v0个顶点出发深度优先遍历图G，查找并输出关节点。*/
int min,w;
ArcNode *p;
visited[v0]=min=++count; /* v0是第count个访问的顶点 */
for(p=G.vertices[v0].firstarc;p;p=p->nextarc) /* 对v0的每个邻接顶点检查 */
{
w=p->adjvex; /* w为v0的邻接顶点 */
if(visited[w]==0) /* w未曾访问，是v0的孩子 */
{
DFSArticul(G,w); /* 返回前求得low[w] */
if(low[w]<min)
min=low[w];
if(low[w]>=visited[v0])
printf("%d %s\n",v0,G.vertices[v0].data); /* 关节点 */
}
else if(visited[w]<min)
min=visited[w]; /* w已访问，w是v0在生成树上的祖先 */
}
low[v0]=min;
}
void FindArticul(ALGraph G)
{ /* 连通图G以邻接表作存储结构，查找并输出G上全部关节点。*/
/* 全局量count对访问计数。 */
int i,v;
ArcNode *p;
count=1;
low[0]=visited[0]=1; /* 设定邻接表上0号顶点为生成树的根 */
for(i=1;i<G.vexnum;++i)
visited[i]=0; /* 其余顶点尚未访问 */
p=G.vertices[0].firstarc;
v=p->adjvex;
DFSArticul(G,v); /* 从第v顶点出发深度优先查找关节点 */
if(count<G.vexnum) /* 生成树的根有至少两棵子树 */
{
printf("%d %s\n",0,G.vertices[0].data); /* 根是关节点，输出 */
while(p->nextarc)
{
p=p->nextarc;
v=p->adjvex;
if(visited[v]==0)
DFSArticul(G,v);
}
}
}
void main()
{
int i;
ALGraph g;
printf("请选择无向图\n");
CreateGraph(&g);
printf("输出关节点：\n");
FindArticul(g);
printf(" i G.vertices[i].data visited[i] low[i]\n");
for(i=0;i<g.vexnum;++i)
printf("%2d %9s %14d %8d\n",i,g.vertices[i].data,visited[i],low[i]);
}运行结果:
1.7.7 拓扑排序
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<math.h> /* floor(),ceil(),abs() */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
#define MAX_NAME 5 /* 顶点字符串的最大长度 */
typedef int InfoType;
typedef char VertexType[MAX_NAME]; /* 字符串类型 */
#define MAX_VERTEX_NUM 20
typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */
typedef struct ArcNode
{
int adjvex; /* 该弧所指向的顶点的位置 */
struct ArcNode *nextarc; /* 指向下一条弧的指针 */
InfoType *info; /* 网的权值指针） */
}ArcNode; /* 表结点 */
typedef struct
{
VertexType data; /* 顶点信息 */
ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针 */
}VNode,AdjList[MAX_VERTEX_NUM]; /* 头结点 */
typedef struct
{
AdjList vertices;
int vexnum,arcnum; /* 图的当前顶点数和弧数 */
int kind; /* 图的种类标志 */
}ALGraph;
int LocateVex(ALGraph G,VertexType u)
{ /* 初始条件: 图G存在,u和G中顶点有相同特征 */
/* 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vertices[i].data)==0)
return i;
return -1;
}
Status CreateGraph(ALGraph *G)
{ /* 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图) */
int i,j,k;
int w; /* 权值 */
VertexType va,vb;
ArcNode *p;
printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");
scanf("%d",&(*G).kind);
printf("请输入图的顶点数,边数: ");
scanf("%d,%d",&(*G).vexnum,&(*G).arcnum);
printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
{
scanf("%s",(*G).vertices[i].data);
(*G).vertices[i].firstarc=NULL;
}
if((*G).kind==1||(*G).kind==3) /* 网 */
printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n");
else /* 图 */
printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n");
for(k=0;k<(*G).arcnum;++k) /* 构造表结点链表 */
{
if((*G).kind==1||(*G).kind==3) /* 网 */
scanf("%d%s%s",&w,va,vb);
else /* 图 */
scanf("%s%s",va,vb);
i=LocateVex(*G,va); /* 弧尾 */
j=LocateVex(*G,vb); /* 弧头 */
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
if((*G).kind==1||(*G).kind==3) /* 网 */
{
p->info=(int *)malloc(sizeof(int));
*(p->info)=w;
}
else
p->info=NULL; /* 图 */
p->nextarc=(*G).vertices[i].firstarc; /* 插在表头 */
(*G).vertices[i].firstarc=p;
if((*G).kind>=2) /* 无向图或网,产生第二个表结点 */
{
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=i;
if((*G).kind==3) /* 无向网 */
{
p->info=(int*)malloc(sizeof(int));
*(p->info)=w;
}
else
p->info=NULL; /* 无向图 */
p->nextarc=(*G).vertices[j].firstarc; /* 插在表头 */
(*G).vertices[j].firstarc=p;
}
}
return OK;
}
VertexType* GetVex(ALGraph G,int v)
{ /* 初始条件: 图G存在,v是G中某个顶点的序号。操作结果: 返回v的值 */
if(v>=G.vexnum||v<0)
exit(ERROR);
return &G.vertices[v].data;
}
int FirstAdjVex(ALGraph G,VertexType v)
{ /* 初始条件: 图G存在,v是G中某个顶点 */
/* 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */
ArcNode *p;
int v1;
v1=LocateVex(G,v); /* v1为顶点v在图G中的序号 */
p=G.vertices[v1].firstarc;
if(p)
return p->adjvex;
else
return -1;
}
int NextAdjVex(ALGraph G,VertexType v,VertexType w)
{ /* 初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点 */
/* 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号。 */
/* 若w是v的最后一个邻接点,则返回-1 */
ArcNode *p;
int v1,w1;
v1=LocateVex(G,v); /* v1为顶点v在图G中的序号 */
w1=LocateVex(G,w); /* w1为顶点w在图G中的序号 */
p=G.vertices[v1].firstarc;
while(p&&p->adjvex!=w1) /* 指针p不空且所指表结点不是w */
p=p->nextarc;
if(!p||!p->nextarc) /* 没找到w或w是最后一个邻接点 */
return -1;
else /* p->adjvex==w */
return p->nextarc->adjvex; /* 返回v的(相对于w的)下一个邻接顶点的序号 */
}
Boolean visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */
void(*VisitFunc)(char* v); /* 函数变量(全局量) */
void DFS(ALGraph G,int v)
{ /* 从第v个顶点出发递归地深度优先遍历图G。*/
int w;
VertexType v1,w1;
strcpy(v1,*GetVex(G,v));
visited[v]=TRUE; /* 设置访问标志为TRUE(已访问) */
VisitFunc(G.vertices[v].data); /* 访问第v个顶点 */
for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w))))
if(!visited[w])
DFS(G,w); /* 对v的尚未访问的邻接点w递归调用DFS */
}
typedef int QElemType; /* 队列类型 */
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;
Status InitQueue(LinkQueue *Q)
{ /* 构造一个空队列Q */
(*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));
if(!(*Q).front)
exit(OVERFLOW);
(*Q).front->next=NULL;
return OK;
}
Status QueueEmpty(LinkQueue Q)
{ /* 若Q为空队列,则返回TRUE,否则返回FALSE */
if(Q.front==Q.rear)
return TRUE;
else
return FALSE;
}
Status EnQueue(LinkQueue *Q,QElemType e)
{ /* 插入元素e为Q的新的队尾元素 */
QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
if(!p) /* 存储分配失败 */
exit(OVERFLOW);
p->data=e;
p->next=NULL;
(*Q).rear->next=p;
(*Q).rear=p;
return OK;
}
Status DeQueue(LinkQueue *Q,QElemType *e)
{ /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
QueuePtr p;
if((*Q).front==(*Q).rear)
return ERROR;
p=(*Q).front->next;
*e=p->data;
(*Q).front->next=p->next;
if((*Q).rear==p)
(*Q).rear=(*Q).front;
free(p);
return OK;
}
void BFSTraverse(ALGraph G,void(*Visit)(char*))
{/*按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。算法7.6 */
int v,u,w;
VertexType u1,w1;
LinkQueue Q;
for(v=0;v<G.vexnum;++v)
visited[v]=FALSE; /* 置初值 */
InitQueue(&Q); /* 置空的辅助队列Q */
for(v=0;v<G.vexnum;v++) /* 如果是连通图,只v=0就遍历全图 */
if(!visited[v]) /* v尚未访问 */
{
visited[v]=TRUE;
Visit(G.vertices[v].data);
EnQueue(&Q,v); /* v入队列 */
while(!QueueEmpty(Q)) /* 队列不空 */
{
DeQueue(&Q,&u); /* 队头元素出队并置为u */
strcpy(u1,*GetVex(G,u));
for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w))))
if(!visited[w]) /* w为u的尚未访问的邻接顶点 */
{
visited[w]=TRUE;
Visit(G.vertices[w].data);
EnQueue(&Q,w); /* w入队 */
}
}
}
printf("\n");
}
void Display(ALGraph G)
{ /* 输出图的邻接矩阵G */
int i;
ArcNode *p;
switch(G.kind)
{
case DG: printf("有向图\n");
break;
case DN: printf("有向网\n");
break;
case AG: printf("无向图\n");
break;
case AN: printf("无向网\n");
}
printf("%d个顶点：\n",G.vexnum);
for(i=0;i<G.vexnum;++i)
printf("%s ",G.vertices[i].data);
printf("\n%d条弧(边):\n",G.arcnum);
for(i=0;i<G.vexnum;i++)
{
p=G.vertices[i].firstarc;
while(p)
{
if(G.kind<=1) /* 有向 */
{
printf("%s→%s ",G.vertices[i].data,G.vertices[p->adjvex].data);
if(G.kind==DN) /* 网 */
printf(":%d ",*(p->info));
}
else /* 无向(避免输出两次) */
{
if(i<p->adjvex)
{
printf("%s－%s ",G.vertices[i].data,G.vertices[p->adjvex].data);
if(G.kind==AN) /* 网 */
printf(":%d ",*(p->info));
}
}
p=p->nextarc;
}
printf("\n");
}
}
void FindInDegree(ALGraph G,int indegree[])
{ /* 求顶点的入度*/
int i;
ArcNode *p;
for(i=0;i<G.vexnum;i++)
indegree[i]=0; /* 赋初值 */
for(i=0;i<G.vexnum;i++)
{
p=G.vertices[i].firstarc;
while(p)
{
indegree[p->adjvex]++;
p=p->nextarc;
}
}
}
typedef int SElemType; /* 栈类型 */
#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */
#define STACKINCREMENT 2 /* 存储空间分配增量 */
typedef struct SqStack
{
SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */
SElemType *top; /* 栈顶指针 */
int stacksize; /* 当前已分配的存储空间，以元素为单位 */
}SqStack; /* 顺序栈 */
Status InitStack(SqStack *S)
{ /* 构造一个空栈S */
(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!(*S).base)
exit(OVERFLOW); /* 存储分配失败 */
(*S).top=(*S).base;
(*S).stacksize=STACK_INIT_SIZE;
return OK;
}
Status StackEmpty(SqStack S)
{ /* 若栈S为空栈，则返回TRUE，否则返回FALSE */
if(S.top==S.base)
return TRUE;
else
return FALSE;
}
Status Push(SqStack *S,SElemType e)
{ /* 插入元素e为新的栈顶元素 */
if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */
{
(*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!(*S).base)
exit(OVERFLOW); /* 存储分配失败 */
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;
}
*((*S).top)++=e;
return OK;
}
Status Pop(SqStack *S,SElemType *e)
{ /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
if((*S).top==(*S).base)
return ERROR;
*e=*--(*S).top;
return OK;
}
Status TopologicalSort(ALGraph G)
{ /* 有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序列并返回OK, */
/* 否则返回ERROR。*/
int i,k,count,indegree[MAX_VERTEX_NUM];
SqStack S;
ArcNode *p;
FindInDegree(G,indegree); /* 对各顶点求入度indegree[0..vernum-1] */
InitStack(&S); /* 初始化栈 */
for(i=0;i<G.vexnum;++i) /* 建零入度顶点栈S */
if(!indegree[i])
Push(&S,i); /* 入度为0者进栈 */
count=0; /* 对输出顶点计数 */
while(!StackEmpty(S))
{ /* 栈不空 */
Pop(&S,&i);
printf("%s ",G.vertices[i].data); /* 输出i号顶点并计数 */
++count;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{ /* 对i号顶点的每个邻接点的入度减1 */
k=p->adjvex;
if(!(--indegree[k])) /* 若入度减为0,则入栈 */
Push(&S,k);
}
}
if(count<G.vexnum)
{
printf("此有向图有回路\n");
return ERROR;
}
else
{
printf("为一个拓扑序列。\n");
return OK;
}
}
void main()
{
ALGraph f;
printf("请选择有向图\n");
CreateGraph(&f);
Display(f);
TopologicalSort(f);
}运行结果:
1.7.8 关键路径
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<math.h> /* floor(),ceil(),abs() */
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
#define MAX_NAME 5 /* 顶点字符串的最大长度+1 */
typedef int InfoType;
typedef char VertexType[MAX_NAME]; /* 字符串类型 */
/* c7-2.h 图的邻接表存储表示 */
#define MAX_VERTEX_NUM 20
typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */
typedef struct ArcNode
{
int adjvex; /* 该弧所指向的顶点的位置 */
struct ArcNode *nextarc; /* 指向下一条弧的指针 */
InfoType *info; /* 网的权值指针） */
}ArcNode; /* 表结点 */
typedef struct
{
VertexType data; /* 顶点信息 */
ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针 */
}VNode,AdjList[MAX_VERTEX_NUM]; /* 头结点 */
typedef struct
{
AdjList vertices;
int vexnum,arcnum; /* 图的当前顶点数和弧数 */
int kind; /* 图的种类标志 */
}ALGraph;
int LocateVex(ALGraph G,VertexType u)
{ /* 初始条件: 图G存在,u和G中顶点有相同特征 */
/* 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vertices[i].data)==0)
return i;
return -1;
}
Status CreateGraph(ALGraph *G)
{ /* 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图) */
int i,j,k;
int w; /* 权值 */
VertexType va,vb;
ArcNode *p;
printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");
scanf("%d",&(*G).kind);
printf("请输入图的顶点数,边数: ");
scanf("%d,%d",&(*G).vexnum,&(*G).arcnum);
printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
{
scanf("%s",(*G).vertices[i].data);
(*G).vertices[i].firstarc=NULL;
}
if((*G).kind==1||(*G).kind==3) /* 网 */
printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n");
else /* 图 */
printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n");
for(k=0;k<(*G).arcnum;++k) /* 构造表结点链表 */
{
if((*G).kind==1||(*G).kind==3) /* 网 */
scanf("%d%s%s",&w,va,vb);
else /* 图 */
scanf("%s%s",va,vb);
i=LocateVex(*G,va); /* 弧尾 */
j=LocateVex(*G,vb); /* 弧头 */
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
if((*G).kind==1||(*G).kind==3) /* 网 */
{
p->info=(int *)malloc(sizeof(int));
*(p->info)=w;
}
else
p->info=NULL; /* 图 */
p->nextarc=(*G).vertices[i].firstarc; /* 插在表头 */
(*G).vertices[i].firstarc=p;
if((*G).kind>=2) /* 无向图或网,产生第二个表结点 */
{
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=i;
if((*G).kind==3) /* 无向网 */
{
p->info=(int*)malloc(sizeof(int));
*(p->info)=w;
}
else
p->info=NULL; /* 无向图 */
p->nextarc=(*G).vertices[j].firstarc; /* 插在表头 */
(*G).vertices[j].firstarc=p;
}
}
return OK;
}
VertexType* GetVex(ALGraph G,int v)
{ /* 初始条件: 图G存在,v是G中某个顶点的序号。操作结果: 返回v的值 */
if(v>=G.vexnum||v<0)
exit(ERROR);
return &G.vertices[v].data;
}
int FirstAdjVex(ALGraph G,VertexType v)
{ /* 初始条件: 图G存在,v是G中某个顶点 */
/* 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */
ArcNode *p;
int v1;
v1=LocateVex(G,v); /* v1为顶点v在图G中的序号 */
p=G.vertices[v1].firstarc;
if(p)
return p->adjvex;
else
return -1;
}
int NextAdjVex(ALGraph G,VertexType v,VertexType w)
{ /* 初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点 */
/* 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号。 */
/* 若w是v的最后一个邻接点,则返回-1 */
ArcNode *p;
int v1,w1;
v1=LocateVex(G,v); /* v1为顶点v在图G中的序号 */
w1=LocateVex(G,w); /* w1为顶点w在图G中的序号 */
p=G.vertices[v1].firstarc;
while(p&&p->adjvex!=w1) /* 指针p不空且所指表结点不是w */
p=p->nextarc;
if(!p||!p->nextarc) /* 没找到w或w是最后一个邻接点 */
return -1;
else /* p->adjvex==w */
return p->nextarc->adjvex; /* 返回v的(相对于w的)下一个邻接顶点的序号 */
}
Boolean visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */
void(*VisitFunc)(char* v); /* 函数变量(全局量) */
void DFS(ALGraph G,int v)
{ /* 从第v个顶点出发递归地深度优先遍历图G。*/
int w;
VertexType v1,w1;
strcpy(v1,*GetVex(G,v));
visited[v]=TRUE; /* 设置访问标志为TRUE(已访问) */
VisitFunc(G.vertices[v].data); /* 访问第v个顶点 */
for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w))))
if(!visited[w])
DFS(G,w); /* 对v的尚未访问的邻接点w递归调用DFS */
}
void DFSTraverse(ALGraph G,void(*Visit)(char*))
{ /* 对图G作深度优先遍历。*/
int v;
VisitFunc=Visit; /* 使用全局变量VisitFunc,使DFS不必设函数指针参数 */
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE; /* 访问标志数组初始化 */
for(v=0;v<G.vexnum;v++)
if(!visited[v])
DFS(G,v); /* 对尚未访问的顶点调用DFS */
printf("\n");
}
typedef int QElemType; /* 队列类型 */
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;
Status InitQueue(LinkQueue *Q)
{ /* 构造一个空队列Q */
(*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));
if(!(*Q).front)
exit(OVERFLOW);
(*Q).front->next=NULL;
return OK;
}
Status QueueEmpty(LinkQueue Q)
{ /* 若Q为空队列,则返回TRUE,否则返回FALSE */
if(Q.front==Q.rear)
return TRUE;
else
return FALSE;
}
Status EnQueue(LinkQueue *Q,QElemType e)
{ /* 插入元素e为Q的新的队尾元素 */
QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
if(!p) /* 存储分配失败 */
exit(OVERFLOW);
p->data=e;
p->next=NULL;
(*Q).rear->next=p;
(*Q).rear=p;
return OK;
}
Status DeQueue(LinkQueue *Q,QElemType *e)
{ /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
QueuePtr p;
if((*Q).front==(*Q).rear)
return ERROR;
p=(*Q).front->next;
*e=p->data;
(*Q).front->next=p->next;
if((*Q).rear==p)
(*Q).rear=(*Q).front;
free(p);
return OK;
}
void BFSTraverse(ALGraph G,void(*Visit)(char*))
{/*按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。*/
int v,u,w;
VertexType u1,w1;
LinkQueue Q;
for(v=0;v<G.vexnum;++v)
visited[v]=FALSE; /* 置初值 */
InitQueue(&Q); /* 置空的辅助队列Q */
for(v=0;v<G.vexnum;v++) /* 如果是连通图,只v=0就遍历全图 */
if(!visited[v]) /* v尚未访问 */
{
visited[v]=TRUE;
Visit(G.vertices[v].data);
EnQueue(&Q,v); /* v入队列 */
while(!QueueEmpty(Q)) /* 队列不空 */
{
DeQueue(&Q,&u); /* 队头元素出队并置为u */
strcpy(u1,*GetVex(G,u));
for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w))))
if(!visited[w]) /* w为u的尚未访问的邻接顶点 */
{
visited[w]=TRUE;
Visit(G.vertices[w].data);
EnQueue(&Q,w); /* w入队 */
}
}
}
printf("\n");
}
void Display(ALGraph G)
{ /* 输出图的邻接矩阵G */
int i;
ArcNode *p;
switch(G.kind)
{
case DG: printf("有向图\n");
break;
case DN: printf("有向网\n");
break;
case AG: printf("无向图\n");
break;
case AN: printf("无向网\n");
}
printf("%d个顶点：\n",G.vexnum);
for(i=0;i<G.vexnum;++i)
printf("%s ",G.vertices[i].data);
printf("\n%d条弧(边):\n",G.arcnum);
for(i=0;i<G.vexnum;i++)
{
p=G.vertices[i].firstarc;
while(p)
{
if(G.kind<=1) /* 有向 */
{
printf("%s→%s ",G.vertices[i].data,G.vertices[p->adjvex].data);
if(G.kind==DN) /* 网 */
printf(":%d ",*(p->info));
}
else /* 无向(避免输出两次) */
{
if(i<p->adjvex)
{
printf("%s－%s ",G.vertices[i].data,G.vertices[p->adjvex].data);
if(G.kind==AN) /* 网 */
printf(":%d ",*(p->info));
}
}
p=p->nextarc;
}
printf("\n");
}
}
int ve[MAX_VERTEX_NUM];
void FindInDegree(ALGraph G,int indegree[])
{ /* 求顶点的入度*/
int i;
ArcNode *p;
for(i=0;i<G.vexnum;i++)
indegree[i]=0; /* 赋初值 */
for(i=0;i<G.vexnum;i++)
{
p=G.vertices[i].firstarc;
while(p)
{
indegree[p->adjvex]++;
p=p->nextarc;
}
}
}
typedef int SElemType; /* 栈类型 */
#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */
#define STACKINCREMENT 2 /* 存储空间分配增量 */
typedef struct SqStack
{
SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */
SElemType *top; /* 栈顶指针 */
int stacksize; /* 当前已分配的存储空间，以元素为单位 */
}SqStack; /* 顺序栈 */
/* bo3-1.c 顺序栈（存储结构由c3-1.h定义）的基本操作（9个） */
Status InitStack(SqStack *S)
{ /* 构造一个空栈S */
(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!(*S).base)
exit(OVERFLOW); /* 存储分配失败 */
(*S).top=(*S).base;
(*S).stacksize=STACK_INIT_SIZE;
return OK;
}
Status StackEmpty(SqStack S)
{ /* 若栈S为空栈，则返回TRUE，否则返回FALSE */
if(S.top==S.base)
return TRUE;
else
return FALSE;
}
Status Push(SqStack *S,SElemType e)
{ /* 插入元素e为新的栈顶元素 */
if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */
{
(*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!(*S).base)
exit(OVERFLOW); /* 存储分配失败 */
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;
}
*((*S).top)++=e;
return OK;
}
Status Pop(SqStack *S,SElemType *e)
{ /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
if((*S).top==(*S).base)
return ERROR;
*e=*--(*S).top;
return OK;
}
Status TopologicalOrder(ALGraph G,SqStack *T)
/* (全局变量)。T为拓扑序列顶点栈,S为零入度顶点栈。若G无回路,则用栈T */
/* 返回G的一个拓扑序列,且函数值为OK,否则为ERROR */
int j,k,count,indegree[MAX_VERTEX_NUM];
SqStack S;
ArcNode *p;
FindInDegree(G,indegree);/*对各顶点求入度indegree[0..vernum-1] */
InitStack(&S); /* 初始化栈 */
for(j=0;j<G.vexnum;++j) /* 建零入度顶点栈S */
if(!indegree[j])
Push(&S,j); /* 入度为0者进栈 */
InitStack(T); /* 初始化拓扑序列顶点栈 */
count=0; /* 对输出顶点计数 */
for(j=0;j<G.vexnum;++j) /* 初始化ve[]=0 (最小值) */
ve[j]=0;
while(!StackEmpty(S))
{ /* 栈不空 */
Pop(&S,&j);
Push(T,j); /* j号顶点入T栈并计数 */
++count;
for(p=G.vertices[j].firstarc;p;p=p->nextarc)
{ /* 对j号顶点的每个邻接点的入度减1 */
k=p->adjvex;
if(--indegree[k]==0) /* 若入度减为0,则入栈 */
Push(&S,k);
if(ve[j]+*(p->info)>ve[k])
ve[k]=ve[j]+*(p->info);
}
}
if(count<G.vexnum)
{
printf("此有向网有回路\n");
return ERROR;
}
else
return OK;
}
Status CriticalPath(ALGraph G)
int vl[MAX_VERTEX_NUM];
SqStack T;
int i,j,k,ee,el;
ArcNode *p;
char dut,tag;
if(!TopologicalOrder(G,&T)) /* 产生有向环 */
return ERROR;
j=ve[0];
for(i=1;i<G.vexnum;i++) /* j=Max(ve[]) 完成点的值 */
if(ve[i]>j)
j=ve[i];
for(i=0;i<G.vexnum;i++) /* 初始化顶点事件的最迟发生时间(最大值) */
vl[i]=j; /* 完成点的最早发生时间 */
while(!StackEmpty(T)) /* 按拓扑逆序求各顶点的vl值 */
for(Pop(&T,&j),p=G.vertices[j].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
dut=*(p->info); /* dut<j,k> */
if(vl[k]-dut<vl[j])
vl[j]=vl[k]-dut;
}
printf(" j k dut ee el tag\n");
for(j=0;j<G.vexnum;++j) /* 求ee,el和关键活动 */
for(p=G.vertices[j].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
dut=*(p->info);
ee=ve[j];
el=vl[k]-dut;
tag=(ee==el)?'*':' ';
printf("%2d %2d %3d %3d %3d %c\n",j,k,dut,ee,el,tag); /* 输出关键活动 */
}
printf("关键活动为:\n");
for(j=0;j<G.vexnum;++j) /* 同上 */
for(p=G.vertices[j].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
dut=*(p->info);
if(ve[j]==vl[k]-dut)
printf("%s→%s\n",G.vertices[j].data,G.vertices[k].data); /* 输出关键活动 */
}
return OK;
}
void main()
{
ALGraph h;
printf("请选择有向网\n");
CreateGraph(&h);
Display(h);
CriticalPath(h);
}运行结果:
1.7.9 最短路径
#include<limits.h> /* INT_MAX等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
#define MAX_NAME 5 /* 顶点字符串的最大长度+1 */
#define MAX_INFO 20 /* 相关信息字符串的最大长度+1 */
typedef int VRType;
typedef char InfoType;
typedef char VertexType[MAX_NAME];
#define INFINITY INT_MAX /* 用整型最大值代替∞ */
#define MAX_VERTEX_NUM 20 /* 最大顶点个数 */
typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */
typedef struct
{
VRType adj; /* 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否； */
/* 对带权图，c则为权值类型 */
InfoType *info; /* 该弧相关信息的指针(可无) */
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM]; /* 顶点向量 */
AdjMatrix arcs; /* 邻接矩阵 */
int vexnum,arcnum; /* 图的当前顶点数和弧数 */
GraphKind kind; /* 图的种类标志 */
}MGraph;
typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int ShortPathTable[MAX_VERTEX_NUM];
int LocateVex(MGraph G,VertexType u)
{ /* 初始条件:图G存在,u和G中顶点有相同特征 */
/* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vexs[i])==0)
return i;
return -1;
}
Status CreateDN(MGraph *G)
{ /* 采用数组(邻接矩阵)表示法,构造有向网G */
int i,j,k,w,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("请输入有向网G的顶点数,弧数,弧是否含其它信息(是:1,否:0): ");
scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i) /* 初始化邻接矩阵 */
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=INFINITY; /* 网 */
(*G).arcs[i][j].info=NULL;
}
printf("请输入%d条弧的弧尾 弧头 权值(以空格作为间隔): \n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s%s%d%*c",va,vb,&w); /* %*c吃掉回车符 */
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=w; /* 有向网 */
if(IncInfo)
{
printf("请输入该弧的相关信息(<%d个字符): ",MAX_INFO);
gets(s);
w=strlen(s);
if(w)
{
info=(char*)malloc((w+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[i][j].info=info; /* 有向 */
}
}
}
(*G).kind=DN;
return OK;
}
void ShortestPath_DIJ(MGraph G,int v0,PathMatrix *P,ShortPathTable *D)
{ /* 用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度 */
/* D[v]。若P[v][w]为TRUE,则w是从v0到v当前求得最短路径上的顶点。 */
/* final[v]为TRUE当且仅当v∈S*/
int v,w,i,j,min;
Status final[MAX_VERTEX_NUM];
for(v=0;v<G.vexnum;++v)
{
final[v]=FALSE;
(*D)[v]=G.arcs[v0][v].adj;
for(w=0;w<G.vexnum;++w)
(*P)[v][w]=FALSE; /* 设空路径 */
if((*D)[v]<INFINITY)
{
(*P)[v][v0]=TRUE;
(*P)[v][v]=TRUE;
}
}
(*D)[v0]=0;
final[v0]=TRUE; /* 初始化,v0顶点属于S集 */
for(i=1;i<G.vexnum;++i) /* 其余G.vexnum-1个顶点 */
{ /* 开始主循环,每次求得v0到某个v顶点的最短路径,并加v到S集 */
min=INFINITY; /* 当前所知离v0顶点的最近距离 */
for(w=0;w<G.vexnum;++w)
if(!final[w]) /* w顶点在V-S中 */
if((*D)[w]<min)
{
v=w;
min=(*D)[w];
} /* w顶点离v0顶点更近 */
final[v]=TRUE; /* 离v0顶点最近的v加入S集 */
for(w=0;w<G.vexnum;++w) /* 更新当前最短路径及距离 */
{
if(!final[w]&&min<INFINITY&&G.arcs[v][w].adj<INFINITY&&(min+G.arcs[v][w].adj<(*D)[w]))
{ /* 修改D[w]和P[w],w∈V-S */
(*D)[w]=min+G.arcs[v][w].adj;
for(j=0;j<G.vexnum;++j)
(*P)[w][j]=(*P)[v][j];
(*P)[w][w]=TRUE;
}
}
}
}
void main()
{
int i,j,v0=0; /* v0为源点 */
MGraph g;
PathMatrix p;
ShortPathTable d;
CreateDN(&g);
ShortestPath_DIJ(g,v0,&p,&d);
printf("最短路径数组p[i][j]如下:\n");
for(i=0;i<g.vexnum;++i)
{
for(j=0;j<g.vexnum;++j)
printf("%2d",p[i][j]);
printf("\n");
}
printf("%s到各顶点的最短路径长度为：\n",g.vexs[0]);
for(i=1;i<g.vexnum;++i)
printf("%s-%s:%d\n",g.vexs[0],g.vexs[i],d[i]);
}运行结果:
1.7.10 每一对顶点之间的最短路径
#define MAX_NAME 5 /* 顶点字符串的最大长度+1 */
#define MAX_INFO 20 /* 相关信息字符串的最大长度+1 */
typedef int VRType;
typedef char VertexType[MAX_NAME];
typedef char InfoType;
#include<limits.h> /* INT_MAX等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
#define INFINITY INT_MAX /* 用整型最大值代替∞ */
#define MAX_VERTEX_NUM 20 /* 最大顶点个数 */
typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */
typedef struct
{
VRType adj; /* 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否； */
/* 对带权图，c则为权值类型 */
InfoType *info; /* 该弧相关信息的指针(可无) */
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM]; /* 顶点向量 */
AdjMatrix arcs; /* 邻接矩阵 */
int vexnum,arcnum; /* 图的当前顶点数和弧数 */
GraphKind kind; /* 图的种类标志 */
}MGraph;
int LocateVex(MGraph G,VertexType u)
{ /* 初始条件:图G存在,u和G中顶点有相同特征 */
/* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vexs[i])==0)
return i;
return -1;
}
Status CreateFAG(MGraph *G)
{ /* 采用数组(邻接矩阵)表示法,由文件构造没有相关信息的无向图G */
int i,j,k;
char filename[13];
VertexType va,vb;
FILE *graphlist;
printf("请输入数据文件名(f7-1.dat)：");
scanf("%s",filename);
graphlist=fopen(filename,"r");
fscanf(graphlist,"%d",&(*G).vexnum);
fscanf(graphlist,"%d",&(*G).arcnum);
for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
fscanf(graphlist,"%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i) /* 初始化邻接矩阵 */
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=0; /* 图 */
(*G).arcs[i][j].info=NULL; /* 没有相关信息 */
}
for(k=0;k<(*G).arcnum;++k)
{
fscanf(graphlist,"%s%s",va,vb);
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=1; /* 无向图 */
}
fclose(graphlist);
(*G).kind=AG;
return OK;
}
Status CreateDG(MGraph *G)
{ /* 采用数组(邻接矩阵)表示法,构造有向图G */
int i,j,k,l,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("请输入有向图G的顶点数,弧数,弧是否含其它信息(是:1,否:0): ");
scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i) /* 初始化邻接矩阵 */
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=0; /* 图 */
(*G).arcs[i][j].info=NULL;
}
printf("请输入%d条弧的弧尾 弧头(以空格作为间隔): \n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s%s%*c",va,vb); /* %*c吃掉回车符 */
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=1; /* 有向图 */
if(IncInfo)
{
printf("请输入该弧的相关信息(<%d个字符): ",MAX_INFO);
gets(s);
l=strlen(s);
if(l)
{
info=(char*)malloc((l+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[i][j].info=info; /* 有向 */
}
}
}
(*G).kind=DG;
return OK;
}
Status CreateDN(MGraph *G)
{ /* 采用数组(邻接矩阵)表示法,构造有向网G */
int i,j,k,w,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("请输入有向网G的顶点数,弧数,弧是否含其它信息(是:1,否:0): ");
scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i) /* 初始化邻接矩阵 */
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=INFINITY; /* 网 */
(*G).arcs[i][j].info=NULL;
}
printf("请输入%d条弧的弧尾 弧头 权值(以空格作为间隔): \n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s%s%d%*c",va,vb,&w); /* %*c吃掉回车符 */
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=w; /* 有向网 */
if(IncInfo)
{
printf("请输入该弧的相关信息(<%d个字符): ",MAX_INFO);
gets(s);
w=strlen(s);
if(w)
{
info=(char*)malloc((w+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[i][j].info=info; /* 有向 */
}
}
}
(*G).kind=DN;
return OK;
}
Status CreateAG(MGraph *G)
{ /* 采用数组(邻接矩阵)表示法,构造无向图G */
int i,j,k,l,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("请输入无向图G的顶点数,边数,边是否含其它信息(是:1,否:0): ");
scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i) /* 初始化邻接矩阵 */
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=0; /* 图 */
(*G).arcs[i][j].info=NULL;
}
printf("请输入%d条边的顶点1 顶点2(以空格作为间隔): \n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s%s%*c",va,vb); /* %*c吃掉回车符 */
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=1; /* 无向图 */
if(IncInfo)
{
printf("请输入该边的相关信息(<%d个字符): ",MAX_INFO);
gets(s);
l=strlen(s);
if(l)
{
info=(char*)malloc((l+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[i][j].info=(*G).arcs[j][i].info=info; /* 无向 */
}
}
}
(*G).kind=AG;
return OK;
}
Status CreateAN(MGraph *G)
{ /* 采用数组(邻接矩阵)表示法,构造无向网G。算法7.2 */
int i,j,k,w,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("请输入无向网G的顶点数,边数,边是否含其它信息(是:1,否:0): ");
scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i) /* 初始化邻接矩阵 */
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=INFINITY; /* 网 */
(*G).arcs[i][j].info=NULL;
}
printf("请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): \n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s%s%d%*c",va,vb,&w); /* %*c吃掉回车符 */
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=w; /* 无向 */
if(IncInfo)
{
printf("请输入该边的相关信息(<%d个字符): ",MAX_INFO);
gets(s);
w=strlen(s);
if(w)
{
info=(char*)malloc((w+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[i][j].info=(*G).arcs[j][i].info=info; /* 无向 */
}
}
}
(*G).kind=AN;
return OK;
}
Status CreateGraph(MGraph *G)
{ /* 采用数组(邻接矩阵)表示法,构造图G。*/
printf("请输入图G的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");
scanf("%d",&(*G).kind);
switch((*G).kind)
{
case DG: return CreateDG(G); /* 构造有向图 */
case DN: return CreateDN(G); /* 构造有向网 */
case AG: return CreateAG(G); /* 构造无向图 */
case AN: return CreateAN(G); /* 构造无向网 */
default: return ERROR;
}
}
void DestroyGraph(MGraph *G)
{ /* 初始条件: 图G存在。操作结果: 销毁图G */
int i,j;
if((*G).kind<2) /* 有向 */
for(i=0;i<(*G).vexnum;i++) /* 释放弧的相关信息(如果有的话) */
{
for(j=0;j<(*G).vexnum;j++)
if((*G).arcs[i][j].adj==1&&(*G).kind==0||(*G).arcs[i][j].adj!=INFINITY&&(*G).kind==1) /* 有向图的弧||有向网的弧 */
if((*G).arcs[i][j].info) /* 有相关信息 */
{
free((*G).arcs[i][j].info);
(*G).arcs[i][j].info=NULL;
}
}
else /* 无向 */
for(i=0;i<(*G).vexnum;i++) /* 释放边的相关信息(如果有的话) */
for(j=i+1;j<(*G).vexnum;j++)
if((*G).arcs[i][j].adj==1&&(*G).kind==2||(*G).arcs[i][j].adj!=INFINITY&&(*G).kind==3) /* 无向图的边||无向网的边 */
if((*G).arcs[i][j].info) /* 有相关信息 */
{
free((*G).arcs[i][j].info);
(*G).arcs[i][j].info=(*G).arcs[j][i].info=NULL;
}
(*G).vexnum=0;
(*G).arcnum=0;
}
VertexType* GetVex(MGraph G,int v)
{ /* 初始条件: 图G存在，v是G中某个顶点的序号。操作结果: 返回v的值 */
if(v>=G.vexnum||v<0)
exit(ERROR);
return &G.vexs[v];
}
Status PutVex(MGraph *G,VertexType v,VertexType value)
{ /* 初始条件: 图G存在，v是G中某个顶点。操作结果: 对v赋新值value */
int k;
k=LocateVex(*G,v); /* k为顶点v在图G中的序号 */
if(k<0)
return ERROR;
strcpy((*G).vexs[k],value);
return OK;
}
typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int DistancMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
void ShortestPath_FLOYD(MGraph G,PathMatrix *P,DistancMatrix *D)
{ /* 用Floyd算法求有向网G中各对顶点v和w之间的最短路径P[v][w]及其 */
/* 带权长度D[v][w]。若P[v][w][u]为TRUE,则u是从v到w当前求得最短 */
/* 路径上的顶点。算法7.16 */
int u,v,w,i;
for(v=0;v<G.vexnum;v++) /* 各对结点之间初始已知路径及距离 */
for(w=0;w<G.vexnum;w++)
{
(*D)[v][w]=G.arcs[v][w].adj;
for(u=0;u<G.vexnum;u++)
(*P)[v][w][u]=FALSE;
if((*D)[v][w]<INFINITY) /* 从v到w有直接路径 */
{
(*P)[v][w][v]=TRUE;
(*P)[v][w][w]=TRUE;
}
}
for(u=0;u<G.vexnum;u++)
for(v=0;v<G.vexnum;v++)
for(w=0;w<G.vexnum;w++)
if((*D)[v][u]+(*D)[u][w]<(*D)[v][w]) /* 从v经u到w的一条路径更短 */
{
(*D)[v][w]=(*D)[v][u]+(*D)[u][w];
for(i=0;i<G.vexnum;i++)
(*P)[v][w][i]=(*P)[v][u][i]||(*P)[u][w][i];
}
}
void main()
{
MGraph g;
int i,j,k,l,m,n;
PathMatrix p;
DistancMatrix d;
CreateDN(&g);
for(i=0;i<g.vexnum;i++)
g.arcs[i][i].adj=0; /* ShortestPath_FLOYD()要求对角元素值为0 */
printf("邻接矩阵:\n");
for(i=0;i<g.vexnum;i++)
{
for(j=0;j<g.vexnum;j++)
printf("%11d",g.arcs[i][j]);
printf("\n");
}
ShortestPath_FLOYD(g,&p,&d);
printf("d矩阵:\n");
for(i=0;i<g.vexnum;i++)
{
for(j=0;j<g.vexnum;j++)
printf("%6d",d[i][j]);
printf("\n");
}
for(i=0;i<g.vexnum;i++)
for(j=0;j<g.vexnum;j++)
printf("%s到%s的最短距离为%d\n",g.vexs[i],g.vexs[j],d[i][j]);
printf("p矩阵:\n");
l=strlen(g.vexs[0]); /* 顶点向量字符串的长度 */
for(i=0;i<g.vexnum;i++)
{
for(j=0;j<g.vexnum;j++)
{
if(i!=j)
{
m=0; /* 占位空格 */
for(k=0;k<g.vexnum;k++)
if(p[i][j][k]==1)
printf("%s",g.vexs[k]);
else
m++;
for(n=0;n<m*l;n++) /* 输出占位空格 */
printf(" ");
}
else
for(k=0;k<g.vexnum*l;k++) /* 输出占位空格 */
printf(" ");
printf(" "); /* 输出矩阵元素之间的间距 */
}
printf("\n");
}
}运行结果: