一. 问题说明
1.问题的简单描述
将图和网的的创建和基本操作分封装到class
用来熟悉此种数据结构和基于这种数据结构上的基本算法
采用VS2010编译环境
2.工作安排
二. 源代码
1.文件stdafx.h
1 #pragma once
2 #include "targetver.h"
3 #include <stdio.h>
4 #include <tchar.h>
5 #include<iostream>
6 #include<string>
7 #include<string.h>
8 using namespace std;
9 /*
10 以下完成图的存储结构
11 (
12 关键在于结构体的组合
13 )
14 */
15 #define INFINITY INT_MAX // 用整形最大值代替∞
16 const int MAX_VERTEX_NUM=26;// 最大顶点个数
17 #define VRType int //顶点关系类型
18 #define InfoType string//弧相关信息
19 #define VertexType string//顶点类型
20 enum GraphKind{DG,DN,UDG,UDN};// 有向图,有向网,无向图,无向网
21 typedef struct
22 {
23 VRType adj; //adjacency 邻接
24 // 对图来说1(是),0(否)表示相邻关系
25 // 对网来说为权值
26 InfoType info; //Info 信息
27 //该弧相关信息的指针
28 }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
29 //Arc 弧(边)
30 struct MGraph
31 {
32 VertexType vex[MAX_VERTEX_NUM]; //顶点向量
33 AdjMatrix arcs; //邻接矩阵
34 int vexnum,arcnum ;
35 GraphKind kind; //图的种类
36 };
37 class Graph
38 {
39 private:
40 MGraph G;
41 public:
42 Graph();
43 void CreateUDG();//创建无向图
44 void CreateUDN();//创建无向网
45 void CreateDG(); //创建有向图
46 void CreateDN(); //创建有向网
47 void CreateUDG_BYFile();//创建无向图,通过文件
48 void CreateUDN_BYFile();//创建无向网,通过文件
49 void CreateDG_BYFile(); //创建有向图,通过文件
50 void CreateDN_BYFile(); //创建有向网,通过文件
51 int LocateVex(VertexType u); //以顶点名称确定其邻接矩阵中的位置
52 void Display();//展示图或网的顶点向量,和邻接矩阵
53 };
2.文件Graph_Matrix.cpp
1 #include "stdafx.h"
2 Graph::Graph()
3 {
4 cout<<"请输入图G的类型( 有向图:0; 有向网:1; 无向图 :2; 无向网 3;)"<<endl;
5 scanf("%d",&G.kind);
6 switch(G.kind)
7 {
8 case UDG: CreateUDG();
9 break;
10 case UDN: CreateUDN();
11 break;
12 case DG: CreateDG();
13 break;
14 case DN: CreateDN();
15 break;
16 }
17 }
18 void Graph::CreateUDG()
19 {
20 /*采用数组(邻接矩阵)表示法,构造无向图G
21 以边为输入单位,即输入边的俩个顶点
22 关键在于判断输入顶点是否存在,返回其位置
23 */
24 int i,j,IncInfo;//是否包含边或弧的相关信息
25 VertexType va,vb;
26 cout<<"请输入无向图的顶点数,边数,变是否包含其他信息(是:1; 否;0;)"<<endl;
27 cin>>G.vexnum;//顶点数
28 cin>>G.arcnum;//边数
29 cin>>IncInfo;//是否具有相关信息的判断条件
30 cout<<"请输入"<<G.vexnum<<"个顶点的的值"<<endl;
31 for(i=0; i<G.vexnum; i++)//构造顶点向量
32 {
33 cin>>G.vex[i];
34 }
35 for(i=0; i<G.vexnum; i++)//初始化邻接矩阵
36 {
37 for(j=0; j<G.vexnum; j++)
38 {
39 G.arcs[i][j].adj=0;//图
40 G.arcs[i][j].info="NULL";//初始化为空串
41 }
42 }
43 cout<<"请输入"<<G.arcnum<<"条边的顶点1,顶点2:"<<endl;
44 for(int k=0; k<G.arcnum; k++)//按边录入信息
45 {
46 cin>>va;
47 i=LocateVex(va);//查询下标,va所在的行坐标
48 cin>>vb;
49 j=LocateVex(vb);//查询下标,vb所在的行坐标
50 G.arcs[i][j].adj=1; //表示va 与 vb 相连 无向图
51 G.arcs[j][i].adj=1; //表示va与vb相连 无向图
52 if(IncInfo)
53 {
54 cout<<"请输入该边相关信息"<<endl;
55 cin>>G.arcs[i][j].info; //输入字符串
56 G.arcs[j][i].info=G.arcs[i][j].info;//对称阵
57 }
58 }
59 G.kind=UDG; //创建成功
60 }
61 void Graph::CreateUDN()
62 {
63 /*
64 原理和UDG相同,只是增加了权值的输入
65 */
66 int i,j,IncInfo;//是否包含边或弧的相关信息
67 VertexType va,vb;
68 cout<<"请输入无向网的顶点数,边数,变是否包含其他信息(是:1; 否;0;)"<<endl;
69 cin>>G.vexnum;//顶点数
70 cin>>G.arcnum;//边数
71 cin>>IncInfo;//是否具有相关信息的判断条件
72 cout<<"请输入"<<G.vexnum<<"个顶点的的值"<<endl;
73 for(i=0; i<G.vexnum; i++)//构造顶点向量
74 {
75 cin>>G.vex[i];
76 }
77 for(i=0; i<G.vexnum; i++)//初始化邻接矩阵
78 {
79 for(j=0; j<G.vexnum; j++)
80 {
81 G.arcs[i][j].adj=INFINITY;//网,无穷大表示不连接
82 G.arcs[i][j].info="NULL";//初始化为空串
83 }
84 }
85 for(int k=0; k<G.arcnum; k++)//按边录入信息
86 {
87 cout<<"请输入第"<<k+1<<"条边的顶点1,顶点2:"<<endl;
88 cin>>va;
89 i=LocateVex(va);//查询下标,va所在的行坐标
90 cin>>vb;
91 j=LocateVex(vb);//查询下标,vb所在的行坐标
92 cout<<"请输入权值"<<endl;
93 cin>>G.arcs[i][j].adj;
94 G.arcs[j][i].adj=G.arcs[i][j].adj;
95 if(IncInfo)
96 {
97 cout<<"请输入该边相关信息"<<endl;
98 cin>>G.arcs[i][j].info; //输入字符串
99 G.arcs[j][i].info=G.arcs[i][j].info;//对称阵
100 }
101 }
102 G.kind=UDN; //创建成功
103 }
104 void Graph::CreateDG()
105 {
106 /*
107 原理与UDG相同,邻接矩阵略有区别
108 */
109 int i,j,IncInfo;//是否包含边或弧的相关信息
110 VertexType va,vb;
111 cout<<"请输入有向图的顶点数,边数,变是否包含其他信息(是:1; 否;0;)"<<endl;
112 cin>>G.vexnum;//顶点数
113 cin>>G.arcnum;//边数
114 cin>>IncInfo;//是否具有相关信息的判断条件
115 cout<<"请输入"<<G.vexnum<<"个顶点的的值"<<endl;
116 for(i=0; i<G.vexnum; i++)//构造顶点向量
117 {
118 cin>>G.vex[i];
119 }
120 for(i=0; i<G.vexnum; i++)//初始化邻接矩阵
121 {
122 for(j=0; j<G.vexnum; j++)
123 {
124 G.arcs[i][j].adj=0;//图
125 G.arcs[i][j].info="NULL";//初始化为空串
126 }
127 }
128 cout<<"请输入"<<G.arcnum<<"条弧的弧头,弧尾:"<<endl;
129 for(int k=0; k<G.arcnum; k++)//按边录入信息
130 {
131 cin>>va;
132 i=LocateVex(va);//查询下标,va所在的行坐标
133 cin>>vb;
134 j=LocateVex(vb);//查询下标,vb所在的行坐标
135 G.arcs[j][i].adj=1; //表示vb(弧尾) 与 vb(弧头) 相连,也就是说vb可以到达va,反之不一定 有向图 vb——>va
136 if(IncInfo)
137 {
138 cout<<"请输入该弧相关信息"<<endl;
139 cin>>G.arcs[i][j].info; //输入字符串
140 G.arcs[j][i].info=G.arcs[i][j].info;//对称阵
141 }
142 }
143 G.kind=DG; //创建成功
144 }
145 void Graph::CreateDN()
146 {
147 /*
148 原理和DG相同,只是增加了权值的输入
149 */
150 int i,j,IncInfo;//是否包含边或弧的相关信息
151 VertexType va,vb;
152 cout<<"请输入有向网的顶点数,边数,变是否包含其他信息(是:1; 否;0;)"<<endl;
153 cin>>G.vexnum;//顶点数
154 cin>>G.arcnum;//边数
155 cin>>IncInfo;//是否具有相关信息的判断条件
156 cout<<"请输入"<<G.vexnum<<"个顶点的的值"<<endl;
157 for(i=0; i<G.vexnum; i++)//构造顶点向量
158 {
159 cin>>G.vex[i];
160 }
161 for(i=0; i<G.vexnum; i++)//初始化邻接矩阵
162 {
163 for(j=0; j<G.vexnum; j++)
164 {
165 G.arcs[i][j].adj=INFINITY;//网,无穷大表示不连接
166 G.arcs[i][j].info="NULL";//初始化为空串
167 }
168 }
169 for(int k=0; k<G.arcnum; k++)//按边录入信息
170 {
171 cout<<"请输入第"<<k+1<<"条弧的弧头,弧尾:"<<endl;
172 cin>>va;
173 i=LocateVex(va);//查询下标,va所在的行坐标
174 cin>>vb;
175 j=LocateVex(vb);//查询下标,vb所在的行坐标
176 cout<<"请输入权值"<<endl;
177 cin>>G.arcs[j][i].adj;
178 if(IncInfo)
179 {
180 cout<<"请输入该弧相关信息"<<endl;
181 cin>>G.arcs[i][j].info; //输入字符串
182 G.arcs[j][i].info=G.arcs[i][j].info;//对称阵
183 }
184 }
185 G.kind=DN; //创建成功
186 }
187 int Graph::LocateVex(VertexType u)//给定顶点值,返回顶点在顶点数组中的下标,方便按边录入信息
188 {
189 for(int i=0; i<G.vexnum; i++)
190 {
191 if(G.vex[i]==u)
192 {
193 return i;
194 }
195 }
196 return -1;
197 }
198 void Graph::Display()
199 {
200 cout<<"顶点向量"<<endl;
201 for(int i=0; i<G.vexnum; i++)
202 {
203 cout<<"顶点"<<G.vex[i]<<endl;
204 }
205 cout<<"邻接矩阵"<<endl;
206 for(int i=0; i<G.vexnum; i++)
207 {
208 for(int j=0;j<G.vexnum;j++)
209 {
210 cout<<G.arcs[i][j].adj<<"t";
211 }
212 cout<<endl;
213 }
214 cout<<"顶点1 顶点2 信息"<<endl;
215 if(G.kind>1) //对于无向图或者无向网来说,邻接矩阵是对称的
216 {
217 for(int i=0; i<G.vexnum; i++)
218 {
219 for(int j=0;j<i;j++)
220 {
221 if(G.arcs[i][j].adj!=0&&G.arcs[i][j].adj!=INFINITY)
222 {
223 cout<<G.vex[i]<<"t";
224 cout<<G.vex[j]<<"t";
225 cout<<G.arcs[i][j].info<<endl;
226 }
227 }
228 }
229 }
230 else//对于有向图或者有向网来说,邻接矩阵必须要全部输出
231 {
232 for(int i=0; i<G.vexnum; i++)
233 {
234 for(int j=0;j<G.vexnum;j++)
235 {
236 if(G.arcs[i][j].adj!=0&&G.arcs[i][j].adj!=INFINITY)
237 {
238 cout<<G.vex[i]<<"t";
239 cout<<G.vex[j]<<"t";
240 cout<<G.arcs[i][j].info<<endl;
241 }
242 }
243 }
244 }
245 }
246 int _tmain(int argc, _TCHAR* argv[])
247 {
248 Graph g;
249 g.Display();
250 return 0;
251 }
原文链接: https://www.cnblogs.com/Howbin/p/8994317.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/273355
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!