jl.〃鄰接矩陣存儲(chǔ)圖

112.#include<iostream>

3.usingnamespacestd;

4.

5.〃定義最大頂點(diǎn)數(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];//頂點(diǎn)集因?yàn)轫旤c(diǎn)存儲(chǔ)序號(hào)范圍為1?MVNum

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

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

19.intvexnum?arcnum;

20.JAMGraph;

21.

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

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

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

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

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

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

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;〃一條邊依附的兩個(gè)頂點(diǎn)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.〃定義打印無(wú)向圖函數(shù)

45.voidprintUDN(AMGraphgraph){

46.for(inti=0;i<=graph.vexnum;i++){〃在第一行打印頂點(diǎn)信息

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

48.}

49.cout<<endl;

50.for(inti=1;i<=graph.vexnum;i++){〃輸出邊的信息(每行第一個(gè)數(shù)字為頂點(diǎn))(注意0號(hào)頂點(diǎn)不輸出)

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

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

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

54.}

55.cout<<endl;

56.}

57.〃輸出結(jié)束

58.}

59.

60.intLocateVex(AMGraphG,intv){〃判斷頂點(diǎn)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.〃增加一個(gè)新頂點(diǎn)v,InsertVexCG,v)；

69.〃在以鄰接矩陣形式存儲(chǔ)的無(wú)向圖G上插入頂點(diǎn)v

70.StatusInsertVex(AMGraph&G,intv){

71.if(LocateVex(G,v)>=0)returnEXISTED;〃判斷該頂點(diǎn)是否已存在

72.if((G.vexnum+1)>MVNum)returnINFEASIBLE;〃判斷頂點(diǎn)數(shù)量是否已超過(guò)數(shù)組最大存儲(chǔ)容量

73.G.vexnum++;

74.G.vexs[G.vexnum]=v;//將頂點(diǎn)信息插入圖的頂點(diǎn)數(shù)組中同時(shí)頂點(diǎn)數(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.〃刪除頂點(diǎn)v及其相關(guān)的邊，DeleteVex(G,v)；

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

83.StatusDeleteVex(AMGraph&G>intv){

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

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

86.returnERROR;

87.inttemp=G.vexs[m];〃將待刪除頂點(diǎn)交換到最后一個(gè)頂點(diǎn)

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

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

100.)

101.

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

103.〃在以鄰接矩陣形式存儲(chǔ)的無(wú)向圖G上增加一條依附于頂點(diǎn)v和頂點(diǎn)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;〃依附于頂點(diǎn)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.〃在以鄰接矩陣形式存儲(chǔ)的無(wú)向圖G上刪除一條依附于頂點(diǎn)v和頂點(diǎn)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;〃待刪除的邊不存在，返回非法錯(cuò)誤

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個(gè)頂點(diǎn)和m條邊

131.cout<<”請(qǐng)輸入頂點(diǎn)的數(shù)量n和邊的數(shù)量m(空格分隔，下同)：\b";

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

133.AMGraphG;

134.cout””請(qǐng)依次輸入m條邊所依附的兩端頂點(diǎn)：\n";

135.createUDN(G,n,m);

136.〃打印圖的信息

137.printUDN(G);

138.intv,w;

139.//開(kāi)始添加新頂點(diǎn)測(cè)試

140.couty”請(qǐng)輸入待添加新頂點(diǎn)編號(hào)：\b"<<endl;

141.cin>>v;

142.InsertVex(G,v);〃插入頂點(diǎn)v

143.〃打印圖的信息

144.printUDN(G);

，145?//開(kāi)始刪除頂點(diǎn)測(cè)試

146.cout<<"請(qǐng)輸入待刪除新頂點(diǎn)編號(hào)：\b"<<endl;

147.cin>>v:

148.DeleteVex(G^v);

149.〃打印圖的信息

150.printUDN(G);

151?〃開(kāi)始添加邊的信息

152.couty”請(qǐng)輸入待添加新邊兩端頂點(diǎn)的編號(hào)：\b"<<endl;

153.cin>>v>>w;

154.InsertArc(G,v,w);

155.〃打印圖的信息

156.printUDN(G);

157.〃開(kāi)始刪除邊的信息

158.cout請(qǐng)輸入待刪除新邊兩