第7章图(算法设计)习题练习答案

试在无向图的邻接矩阵和邻接链表上实现如下算法

()往图中插入一个顶点

()往图中插入一条边

()删去图中某顶点

()删去图中某条边

解

(一)用邻接矩阵表示

#define MaxVertexNum l //最大顶点数应由用户定义

typedef char VertexType //顶点类型应由用户定义

typedef int EdgeType //边上的权值类型应由用户定义

typedef struct{

VextexType vexs[MaxVertexNum] //顶点表

EdeType edges[MaxVertexNum][MaxVertexNum];

//邻接矩阵可看作边表

int ne //图中当前的顶点数和边数

}MGragh

()往图中插入一个顶点

void AddVertexMGraph(MGraph *GVertexType x)

{//往无向图的邻接矩阵中插入顶点

if (G>n>=MaxVertexNum)

Error(顶点数太多)

G>vexs[G>n]=x;//将新顶点输入顶点表

G>n++//顶点数加

}

()往图中插入一条边

void AddedgeMGraph(MGraph *GVertexType xVertexType y)

{//往无向图的邻接矩阵中插入边(xy)

int ijk;

i=;j=;

for(k=;k<G>n;k++)//查找XY的编号

{ if (g>vexs[k]===x) i=k;

if (g>vexs[k]==y) j=k;

}

if (i==||j==) Error(结点不存在);

else {//插入边(xy)

g>vex[i][j]=;

g>vex[j][i]=;

G>e++;//边数加

}

}

()删去图中某顶点

void DeleteVertexMGraph(MGraph *GVertexType x)

{//无向图的邻接矩阵中删除顶点x

int ikj;

i=;

for(k=;k<G>n;k++)//查找X的编号

if (g>vexs[k]=x) i=k;

if (i==) Error(结点不存在);

else {//删除顶点以及边

k=;//求出与x结点相关联的边数k

for (j=;j<G>n;j++)

if (g>vexs[i][j]==) k++;

G>e=G>ek;//设置新的边数

for (k=i+;k<G>n;k++)//在邻接矩阵中删除第i行

for(j=;j<G>n;j++)

g>vexs[k][j]=g>vexs[k][j];

for (k=i+;k<G>n;k++)//在邻接矩阵中删除第i列

for(j=;j<G>n;j++)

g>vexs[j][k]=g>vexs[j][k];

G>n;//总结点数

}

}

()删去图中某条边

void DeleteedgeMGraph(MGraph *GVertexType xVertexType y)

{//无向图的邻接矩阵中删除边(xy)

int ijk;

i=;j=;

for(k=;k<G>n;k++)//查找XY的编号

{ if (g>vexs[k]=x) i=k;

if (g>vexs[k]=y) j=k;

}

if (i==||j==) Error(结点不存在);

else if (g>vexs[i][j]!=)

{//删除边(xy)

g>vex[i][j]=;

g>vex[j][i]=;

G>e;//边数加

}

}

(二)用邻接表表示

typedef struct node{//边表结点

int adjvex //邻接点域

struct node *next //链域

//若要表示边上的权则应增加一个数据域

}EdgeNode;

typedef struct vnode{ //顶点表结点

VertexType vertex //顶点域

EdgeNode *firstedge//边表头指针

}VertexNode

typedef VertexNode AdjList[MaxVertexNum]//AdjList是邻接表类型

typedef struct{

AdjList adjlist//邻接表

int ne 图中当前顶点数和边数

}ALGraph //对于简单的应用无须定义此类型可直接使用AdjList类型

()往图中插入一个顶点

void AddVertexALGraPh(ALGrahp *GVertexType x)

{//往无向图的邻接表表示中插入一个顶点

if (G>n>=MaxVertexNum)

Error(顶点数太多)

G>adjlist[G>n]vertex=x;//将新顶点输入顶点表

G>adjlist[G>n]firstedge=NULL;//边表置为空表

G>n++//顶点数加

}

()往图中插入一条边

void AddedgeALGraPh(ALGrahp *GVertexType xVertexType y)

{//往无向图的邻接表中插入边(xy)

int ijk;

EdgeNode *s

i=;j=;

for(k=;k<G>n;k++)//查找XY的编号

{ if (G>adjlist[k]vertex==x) i=k;

if (G>adjlist[k]vertex==y) j=k;

}

if (i==||j==) Error(结点不存在);

else {

s=G>adjlist[i]firstedge;

while ((s)&&(s>adjvex!=j)//查看邻接表中有无(xy)

s=s>next;

if (!s)//当邻接表中无边(xy)插入边(xy)

{

s=(EdgeNode *)malloc(sizeof(EdgeNode)) //生成边表结点

s>adjvex=j; //邻接点序号为j

s>next=G>adjlist[i]firstedge

G>adjlist[i]firstedge=s//将新结点*s插入顶点x的边表头部

s=(EdgeNode *)malloc(sizeof(EdgeNode))

s>adjvex=i; //邻接点序号为i

s>next=G>adjlist[j]firstedge

G>adjlist[j]firstedge=s //将新结点*s插入顶点x的边表头部

G>e++;//边数加

}

}

}

()删去图中某顶点

void DeleteVertexALGraPh(ALGrahp *GVertexType x)

{//无向图的邻接表中删除顶点x

int ikj;

EdgeNode *s*p*q

i=;

for(k=;k<G>n;k++)//查找X的编号

if (G>adjlist[k]vertex==x) i=k;

if (i==) Error(结点不存在);

else {//删除与x相关联的边

s=G>adjlist[i]firstedge;

while (s)

{p=G>adjlist[s>adjvex]firstedge;//删除与i相关联的其他结点边表中表结点

if (p)&&(p>adjvex==i)//是第一个边表结点修改头指针

{G>adjlist[s>adjvex]firstedge=p>next;

free(p);

}

else//不是第一个 边表结点查找并删除

{while (p)&&(p>next)&&(p>next>adjvex==i)

p=p>next;

q=p>next;

p>next=q>next;free(q);

}

q=s;s=s>next;free(q);//在i结点的边表中删除表结点

G>e;

}

//调整顶点表

for (j=i;j<G>n;j++)

{G>adjlist[j]firstedge=G>adjlist[j+]firstedge;

G>adjlist[j]vertex=G>adjlist[j+]vertex;

}

G>n;

}

}

()删去图中某条边

void DeleteedgeALGraPh(ALGraph *GVertexType xVertexType y)

{//往无向图的邻接表中删除边(xy)

int ijk;

EdgeNode *s*p

i=;j=;

for(k=;k<G>n;k++)//查找XY的编号

{ if (G>adjlist[k]vertex==x) i=k;

if (G>adjlist[k]vertex==y) j=k;

}

if (i==||j==) Error(结点不存在);

else {

s=G>adjlist[i]firstedge;//在i的边表中删除值为j的边表结点

if (s)&&(s>adjvex==j)

{G>adjlist[i]firstedge=s>next;

free(s);

}

else{

while (s)&&(s>next)&&(s>next>adjvex!=j)

s=s>next;

if (!s>next) Error(无此边);