数据结构习题集（李冬梅 第2版）C语言版源程序习题源代码 习题集-算法6-1（邻接矩阵）

jl.〃邻接矩阵存储图

112.#include<iostream>

3.usingnamespacestd;

4.

5.〃定义最大顶点数

6.#defineMVNum128

7.//定义状态类型

8.#defineStatusint

9.〃函数结果状态代码

10.#defineOK1

11.#defineERROR0

12.#defineINFEASIBLE0

13.#defineEXISTED2

14.

15.//定义图的结构体类型

16.typedefstruct{

17.intvexs[MVNum+1];//顶点集因为顶点存储序号范围为1〜MVNum

18.intarcs[MVNum+1][MVNum+1];〃邻接矩阵

〃图当前的顶点数和边数

19.intvexnum?arcnum;

20.JAMGraph;

21.

22.〃采用邻接矩阵表示法，创建无向图graph

|；23.StatuscreateUDN(AMGraph&graph,intvexnum,intarcnum){

24.graph.vexnum=vexnum;〃初始化图的总顶点数

25.graph.arcnum=arcnum;〃初始化图的总边数

26.if(graph.vexnum>=MVNum)returnERROR;//顶点、数超过最大允许范围，返回错误代码。(注意数组下标从。开始)

27.for(inti=0;i<=graph.vexnum;i++){〃依次输入顶点信息

28.graph.vexs[i]=i;

29.)

30.for(inti=0；i<=graph.vexnum;i++){〃初始化所有边的权值为0,表示边不存在

31.for(intj=0;j<=graph.vexnum;j++){

32.graph.arcs[i][j]=0;

33.}

34.)

35.intvex_one,vex_two;〃一条边依附的两个顶点vex_one和vex_two

36.for(inti=0;i<graph.arcnum;i++){〃循环输入arcnum条边的信息

37.cin>>vex_one>>vex_two;

38.graph.arcs[vex_one][vex_two]=1;〃表权值为1,表示边存在

39.graph.arcs[vex_two][vex_one]=1;

40.)

41.returnOK;//创建成功，返回成功代码。

42.}

43.

44.〃定义打印无向图函数

45.voidprintUDN(AMGraphgraph){

46.for(inti=0;i<=graph.vexnum;i++){〃在第一行打印顶点信息

47.cout<<graph.vexs[i]<<"

48.}

49.cout<<endl;

50.for(inti=1;i<=graph.vexnum;i++){〃输出边的信息(每行第一个数字为顶点)(注意0号顶点不输出)

51.cout<<graph.vexs[i]<<"〃输出该行对应的顶点

52.for(intj=1;j<=graph.vexnum;j++){〃输出该行顶点对应所有边信息

53.cout<<graph.arcs[i][j]<<"<*;

54.}

55.cout<<endl;

56.}

57.〃输出结束

58.}

59.

60.intLocateVex(AMGraphG,intv){〃判断顶点v是否存在图G中

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

62.if(G.vexs[i]==v)

63.returni;

64.}

65.return-1;

66.}

67.

68.〃增加一个新顶点v,InsertVexCG,v)；

69.〃在以邻接矩阵形式存储的无向图G上插入顶点v

70.StatusInsertVex(AMGraph&G,intv){

71.if(LocateVex(G,v)>=0)returnEXISTED;〃判断该顶点是否已存在

72.if((G.vexnum+1)>MVNum)returnINFEASIBLE;〃判断顶点数量是否已超过数组最大存储容量

73.G.vexnum++;

74.G.vexs[G.vexnum]=v;//将顶点信息插入图的顶点数组中同时顶点数量自增加一

75.for(intk=0;k<=G.vexnum;k++){

76.G.arcs[G.vexnum][k]=G.arcs[k][G.vexnum]=0;〃邻接矩阵中相应边的信息置为0

77.}

78.returnOK;〃添加成功，返回成功代码

79.}

80.

81.〃删除顶点v及其相关的边，DeleteVex(G,v)；

82.〃在以邻接矩阵形式存储的无向图G上删除顶点v以及和顶点相关的边

83.StatusDeleteVex(AMGraph&G>intv){

84.intn=G.vexnum,m;〃m用于记录顶点v的数组存储下标位置

85.if((m=LocateVexCG,v))<0)〃判断删除操作是否合法，即v是否在G中

86.returnERROR;

87.inttemp=G.vexs[m];〃将待删除顶点交换到最后一个顶点

88.G.vexs[m]=G.vexs[n];

89.G.vexs[n]=temp;

90.for(inti=0;i<=n;i++){〃将边的关系也随之变换

91.temp=G.arcs[m][i];

92.G.arcs[m][i]=G.arcs[n][i];

93.G.arcs[n][i]=temp;

94.temp=G.arcs[i][m];

95.G.arcs[i][m]=G.arcs[i][n];

96.G.arcs[i][n]=temp;

97.}

98.G.vexnum--;〃顶点总数减一

99.returnOK;〃添加成功，返回成功代码

100.)

101.

102.〃增加一条边<v,w>,InsertArc(G,v,w)；

103.〃在以邻接矩阵形式存储的无向图G上增加一条依附于顶点v和顶点m的边

104.StatusInsertArc(AMGraph&G,intv>intw){

105.inti,j;

106.if((i=LocateVex(G,v))<0)returnERROR;〃判断插入位置是否合法

107.if((j=LocateVex(G,w))<0)returnERROR;

108.if(i==j)returnERROR;

109.if(G.arcs[i][j])returnEXISTED;〃依附于顶点v和w的边已经存在

110.G.arcs[i][j]=G.arcs[j][i]=1;

111.G.arcnum++;〃图的边数量加一

112.returnOK;〃添加成功，返I3成功代码

113.}

114.

115.〃删除一条边w>,DeleteArcCG,v,w)o

116.〃在以邻接矩阵形式存储的无向图G上删除一条依附于顶点v和顶点m的边

117.StatusDeleteArc(AMGraph&G,intv,intw){

118.inti,j;

119.if((i=LocateVex(G,v))<0)returnERROR;〃判断插入位置是否合法

120.if((j=LocateVex(G,w))<0)returnERROR;

121.if(i==j)returnERROR;

122.if(G.arcs[i][j]==0)returnINFEASIBLE;〃待删除的边不存在，返回非法错误

123.G.arcs[i][j]=G.arcs[j][i]=0;

124.G.arcnum++;〃图的边数量加一

125.returnOK;〃添加成功，返回成功代码

126.}

127.

128.

129.intmain(){

130.intn,m;〃n个顶点和m条边

131.cout<<”请输入顶点的数量n和边的数量m(空格分隔，下同)：\b";

132.cin>>n>>叫〃输入n和m的值

133.AMGraphG;

134.cout””请依次输入m条边所依附的两端顶点：\n";

135.createUDN(G,n,m);

136.〃打印图的信息

137.printUDN(G);

138.intv,w;

139.//开始添加新顶点测试

140.couty”请输入待添加新顶点编号：\b"<<endl;

141.cin>>v;

142.InsertVex(G,v);〃插入顶点v

143.〃打印图的信息

144.printUDN(G);

，145・//开始删除顶点测试

146.cout<<"请输入待删除新顶点编号：\b"<<endl;

147.cin>>v:

148.DeleteVex(G^v);

149.〃打印图的信息

150.printUDN(G);

151•〃开始添加边的信息

152.couty”请输入待添加新边两端顶点的编号：\b"<<endl;

153.cin>>v>>w;

154.InsertArc(G,v,w);

155.〃打印图的信息

156.printUDN(G);

157.〃开始删除边的信息

158.cout请输入待删除新边两