數(shù)據(jù)結(jié)構(gòu)習(xí)題集（李冬梅 第2版）C語言版源程序習(xí)題源代碼 習(xí)題集-算法6-1（鄰接矩陣）

jl.〃鄰接矩陣存儲圖

112.#include<iostream>

3.usingnamespacestd;

4.

5.〃定義最大頂點數(shù)

6.#defineMVNum128

7.//定義狀態(tài)類型

8.#defineStatusint

9.〃函數(shù)結(jié)果狀態(tài)代碼

10.#defineOK1

11.#defineERROR0

12.#defineINFEASIBLE0

13.#defineEXISTED2

14.

15.//定義圖的結(jié)構(gòu)體類型

16.typedefstruct{

17.intvexs[MVNum+1];//頂點集因為頂點存儲序號范圍為1?MVNum

18.intarcs[MVNum+1][MVNum+1];〃鄰接矩陣

〃圖當(dāng)前的頂點數(shù)和邊數(shù)

19.intvexnum?arcnum;

20.JAMGraph;

21.

22.〃采用鄰接矩陣表示法，創(chuàng)建無向圖graph

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

24.graph.vexnum=vexnum;〃初始化圖的總頂點數(shù)

25.graph.arcnum=arcnum;〃初始化圖的總邊數(shù)

26.if(graph.vexnum>=MVNum)returnERROR;//頂點、數(shù)超過最大允許范圍，返回錯誤代碼。(注意數(shù)組下標(biāo)從。開始)

27.for(inti=0;i<=graph.vexnum;i++){〃依次輸入頂點信息

28.graph.vexs[i]=i;

29.)

30.for(inti=0；i<=graph.vexnum;i++){〃初始化所有邊的權(quán)值為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++){〃循環(huán)輸入arcnum條邊的信息

37.cin>>vex_one>>vex_two;

38.graph.arcs[vex_one][vex_two]=1;〃表權(quán)值為1,表示邊存在

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

40.)

41.returnOK;//創(chuàng)建成功，返回成功代碼。

42.}

43.

44.〃定義打印無向圖函數(shù)

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++){〃輸出邊的信息(每行第一個數(shù)字為頂點)(注意0號頂點不輸出)

51.cout<<graph.vexs[i]<<"〃輸出該行對應(yīng)的頂點

52.for(intj=1;j<=graph.vexnum;j++){〃輸出該行頂點對應(yīng)所有邊信息

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

54.}

55.cout<<endl;

56.}

57.〃輸出結(jié)束

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;〃判斷頂點數(shù)量是否已超過數(shù)組最大存儲容量

73.G.vexnum++;

74.G.vexs[G.vexnum]=v;//將頂點信息插入圖的頂點數(shù)組中同時頂點數(shù)量自增加一

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

76.G.arcs[G.vexnum][k]=G.arcs[k][G.vexnum]=0;〃鄰接矩陣中相應(yīng)邊的信息置為0

77.}

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

79.}

80.

81.〃刪除頂點v及其相關(guān)的邊，DeleteVex(G,v)；

82.〃在以鄰接矩陣形式存儲的無向圖G上刪除頂點v以及和頂點相關(guān)的邊

83.StatusDeleteVex(AMGraph&G>intv){

84.intn=G.vexnum,m;〃m用于記錄頂點v的數(shù)組存儲下標(biāo)位置

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++){〃將邊的關(guān)系也隨之變換

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--;〃頂點總數(shù)減一

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的邊已經(jīng)存在

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

111.G.arcnum++;〃圖的邊數(shù)量加一

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++;〃圖的邊數(shù)量加一

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

126.}

127.

128.

129.intmain(){

130.intn,m;〃n個頂點和m條邊

131.cout<<”請輸入頂點的數(shù)量n和邊的數(shù)量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請輸入待刪除新邊兩