数据结构C语言版 无向图的邻接多重表存储表示和实现

数据结构C语言版 无向图的邻接多重表存储表示和实现

数据结构C语言版 无向图的邻接多重表存储表示和实现

P166

编译环境：Dev-C++ 4.9.9.2

日期：2011年2月15日

*/

#include <stdio.h>

#include <malloc.h>

#define MAX_NAME 3 // 顶点字符串的最大长度+1

#define MAX_INFO 80 // 相关信息字符串的最大长度+1

typedef char InfoType;

typedef char VertexType[MAX_NAME]; // 字符串类型

// AMLGraph.h 无向图的邻接多重表存储表示

#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;

typedef int QElemType;

// 单链队列－－队列的链式存储结构

typedef struct QNode

数据结构C语言版 无向图的邻接多重表存储表示和实现

QElemType data; //数据域

struct QNode *next; //指针域

}QNode,*QueuePtr;

typedef struct

{

QueuePtr front,//队头指针，指针域指向队头元素

rear; //队尾指针，指向队尾元素

}LinkQueue;

// 若G中存在顶点u,则返回该顶点在无向图中位置;否则返回-1

int LocateVex(AMLGraph G,VertexType u)

{

int i;

for(i=0;i<G.vexnum;++i)

if(strcmp(u,G.adjmulist[i].data)==0)

return i;

return -1;

}

// 采用邻接多重表存储结构,构造无向图G

int CreateGraph(AMLGraph *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); // 一端

数据结构C语言版 无向图的邻接多重表存储表示和实现

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 1;

}

// 返回v的值

VertexType* GetVex(AMLGraph G,int v)

{

if(v>=G.vexnum||v<0)

exit(0);

return &G.adjmulist[v].data;

}

// 对v赋新值value

int PutVex(AMLGraph *G,VertexType v,VertexType value)

{

int i;

i=LocateVex(*G,v);

if(i<0) // v不是G的顶点

return 0;

strcpy((*G).adjmulist[i].data,value);

数据结构C语言版 无向图的邻接多重表存储表示和实现

return 1;

}

// 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1

int FirstAdjVex(AMLGraph G,VertexType v)

{

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;

}

// 返回v的(相对于w的)下一个邻接顶点的序号。若w是v的最后一个邻接点,则返回-1 int NextAdjVex(AMLGraph G,VertexType v,VertexType w)

{

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;

数据结构C语言版 无向图的邻接多重表存储表示和实现

}

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;

}

// 在G中增添新顶点v(不增添与顶点相关的弧,留待InsertArc()去做)

int InsertVex(AMLGraph *G,VertexType v)

{

if((*G).vexnum==MAX_VERTEX_NUM) // 结点已满，不能插入

return 0;

if(LocateVex(*G,v)>=0) // 结点已存在,不能插入

return 0;

strcpy((*G).adjmulist[(*G).vexnum].data,v);

(*G).adjmulist[(*G).vexnum].firstedge=NULL;

(*G).vexnum++;

return 1;

}

// 在G中删除弧<v,w>

int DeleteArc(AMLGraph *G,VertexType v,VertexType w)

{

int i,j;

EBox *p,*q;

i=LocateVex(*G,v);

j=LocateVex(*G,w);

if(i<0||j<0||i==j)

return 0; // 图中没有该点或弧

// 以下使指向待删除边的第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;

数据结构C语言版 无向图的邻接多重表存储表示和实现

{ 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 0; 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) // 有相关信息

数据结构C语言版 无向图的邻接多重表存储表示和实现

}

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 1;

数据结构C语言版 无向图的邻接多重表存储表示和实现

// 删除G中顶点v及其相关的边

int DeleteVex(AMLGraph *G,VertexType v)

{

int i,j;

VertexType w;

EBox *p;

i=LocateVex(*G,v); // i为待删除顶点的序号

if(i<0)

return 0;

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 1;

}

void DestroyGraph(AMLGraph *G)

{

int i;

数据结构C语言版 无向图的邻接多重表存储表示和实现

for(i=(*G).vexnum-1;i>=0;i--)

DeleteVex(G,(*G).adjmulist[i].data);

}

// 在G中增添弧<v,w>

int InsertArc(AMLGraph *G,VertexType v,VertexType 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 0;

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 1;

}

int visite[MAX_VERTEX_NUM]; // 访问标志数组(全局量)

数据结构C语言版 无向图的邻接多重表存储表示和实现

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;

}

}

// 算法7.4

// 从第1个顶点起,深度优先遍历图G,并对每个顶点调用函数Visit

void DFSTraverse(AMLGraph G,int(*visit)(VertexType))

{

int v;

VisitFunc=visit;

for(v=0;v<G.vexnum;v++)

visite[v]=0;

for(v=0;v<G.vexnum;v++)

if(!visite[v])

DFS(G,v);

printf("\n");

}

// 构造一个空队列Q

int InitQueue(LinkQueue *Q)

{

(*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode)); //动态分配一个空间 if(!(*Q).front)

exit(0);

(*Q).front->next=NULL; //队头指针指向空，无数据域，这样构成了一个空队列 return 1;

}

// 若Q为空队列,则返回1,否则返回0

数据结构C语言版 无向图的邻接多重表存储表示和实现

int QueueEmpty(LinkQueue Q)

{

if(Q.front==Q.rear)

return 1;

else

return 0;

}

// 插入元素e为Q的新的队尾元素

int EnQueue(LinkQueue *Q,QElemType e)

{

QueuePtr p=(QueuePtr)malloc(sizeof(QNode));

if(!p) // 存储分配失败

exit(0);

//生成一个以为e为数据域的队列元素

p->data=e;

p->next=NULL;

//将该新队列元素接在队尾的后面

(*Q).rear->next=p;

(*Q).rear=p;

return 1;

}

// 若队列不空,删除Q的队头元素,用e返回其值,并返回1,否则返回0

int DeQueue(LinkQueue *Q,QElemType *e)

{

QueuePtr p;

if((*Q).front==(*Q).rear)

return 0;

p=(*Q).front->next; //队头元素

*e=p->data;

(*Q).front->next=p->next;

if((*Q).rear==p)

(*Q).rear=(*Q).front;

free(p);

return 1;

}

// 从第1个顶点起,按广度优先非递归遍历图G,并对每个顶点调用函数

// Visit一次且仅一次。使用辅助队列Q和访问标志数组visite

void BFSTraverse(AMLGraph G,int(*Visit)(VertexType))

{

int v,u,w;

VertexType w1,u1;

数据结构C语言版 无向图的邻接多重表存储表示和实现

LinkQueue Q;

for(v=0;v<G.vexnum;v++)

visite[v]=0; // 置初值

InitQueue(&Q); // 置空的辅助队列Q

for(v=0;v<G.vexnum;v++)

if(!visite[v]) // v尚未访问

{

visite[v]=1; // 设置访问标志为1(已访问)

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]=1;

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

数据结构C语言版 无向图的邻接多重表存储表示和实现

p=p->jlink;

}

}

}

// 输出无向图的邻接多重表G

void Display(AMLGraph 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－",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－",G.adjmulist[p->ivex].data,G.adjmulist[i].data);

p->mark=visited;

if(p->info) // 输出附带信息

printf("相关信息: %s ",p->info); }

p=p->jlink;

} %s %s

数据结构C语言版 无向图的邻接多重表存储表示和实现

printf("\n");

}

}

int visit(VertexType v)

{

printf("%s ",v);

return 1;

}

int 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);

system("pause");

return 0;

}

/*

数据结构C语言版 无向图的邻接多重表存储表示和实现

输出效果：

请输入无向图G的顶点数,边数,边是否含其它信息(是:1，否:0): 3,2,0 请输入3个顶点的值(<3个字符):

a

b

c

请顺序输入每条边的两个端点(以空格作为间隔):

a b

a c

3个顶点：

a b c

2条边:

a－c a－b

修改顶点的值，请输入原值 新值: a d

插入新顶点，请输入顶点的值: e

插入与新顶点有关的边，请输入边数: 1

请输入另一顶点的值: b

该边是否有相关信息(1:有 0:无): 0

4个顶点：

d b c e

3条边:

d－c d－b

e－b

深度优先搜索的结果:

d c b e

广度优先搜索的结果:

d b e c

请按任意键继续. . .

*/

本文来源：https://www.bwwdw.com/article/cg4j.html