实验六 图
一、实验目的
（1）熟悉图的定义和存储结构。
（2）熟练掌握图的如下基本操作：图的创建，图的遍历操作（包括深度遍历和广度遍历）。
实验内容：
根据如下的有向图，分别用如下三种方式创建其存储结构：邻接矩阵，邻接表（出边），十字链表。(G->F为5)
对于1。中每种存储方式，实现对该图的两种遍历，并将输出结果显示在屏幕上。
三、实验要求：
（1）实验报告中需要显示所建立三种存储结构的示意图：即分别显示图的邻接矩阵，邻接表和十字链表示意图。
（2）按步骤将程序运行结果截图写入实验报告。
（3）实验需要在两周内按时完成。
学习资料:
图：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
typedef char InfoType;
typedef char VerTexType;
typedef int ArcType;
typedef int OhterInfo;
typedef int Status;
bool visited\[MVNum\];
using namespace std;
/***邻接矩阵存储结构***/
typedef struct
{
VerTexType vexs\[MVNum\];
ArcType arcs\[MVNum\]\[MVNum\];
int vexnum,arcnum;
}AMGraph;
/***邻接表存储结构***/
typedef struct ArcNode //边结点
{
int adjvex; //改变所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条边的指针
string info; //和边相关的信息
}ArcNode;
typedef struct VNode //顶点信息
{
VerTexType data;
ArcNode *firstarc; //指向第一条依附该顶点的边的指针
}VNode, AdjList\[MVNum\]; //AdList表示邻接表类型
typedef struct //邻接表
{
AdjList vertices;
int vexnum, arcnum; //图的当前顶点数和边数
}ALGraph;
/***十字链表储存结构***/
typedef struct ArcBox
{
int tailvex, headvex; //该弧的尾和头顶点的位置
struct ArcBox \*hlink, \*tlink; //分别为弧头相同和弧尾相同的弧的链域
InfoType *info; //改弧相关信息的指针
}ArcBox;
typedef struct
{
char data;
ArcBox \*firstin, \*firstout; //分别指向该顶点第一条入弧和出弧
}VexNode;
typedef struct
{
VexNode xlist\[MAX\_VERTEX\_NUM\]; //表头向量
int vexnum, arcnum; //有向图的当前顶点数和弧数
}OLGraph;
int createGraphByAdjMatrix(AMGraph &G);
int createGraphByAdjList(ALGraph &G);
int createGraphByOrthLkList(OLGraph &G);
int coutAMGraph(AMGraph &G);
int coutUDG(ALGraph G);
int Display(OLGraph G);
int main()
{
//邻接矩阵
AMGraph MG;
createGraphByAdjMatrix(MG);
coutAMGraph(MG);
cout<<"\\n"<<endl;
//邻接表
ALGraph LG;
createGraphByAdjList(LG);
coutUDG(LG);
cout<<"\\n"<<endl;
//十字链表
OLGraph KG;
createGraphByOrthLkList(KG);
Display(KG);
return 0;
}
/*****邻接矩阵*****/
int createGraphByAdjMatrix(AMGraph &G)
{
int i, j;
VerTexType vetices\[7\]={'A','B','C','D','E','F','G'};
ArcType arcs\[7\]\[7\]={MaxInt,7,MaxInt,18,MaxInt,MaxInt,
MaxInt,MaxInt,MaxInt,2,MaxInt,MaxInt,MaxInt,MaxInt,MaxInt,MaxInt,
MaxInt,MaxInt,MaxInt,9,MaxInt,MaxInt,MaxInt,MaxInt,
MaxInt,20,MaxInt,MaxInt,MaxInt,MaxInt,MaxInt,MaxInt,
MaxInt,MaxInt,MaxInt,MaxInt,MaxInt,MaxInt,3,MaxInt,
MaxInt,MaxInt,14,MaxInt,6,MaxInt,MaxInt,5,MaxInt
};
G.vexnum=7;
G.arcnum=9; //输入总顶点数、总边数
for (i = 0; i < G.vexnum; i++) //依次输入点的信息
{
G.vexs\[i\]=vetices\[i\];
}
for (i = 0; i < G.vexnum; i++) //初始化邻接矩阵，编的权值均为极大值MaxInt
for (j = 0; j < G.vexnum; j++)
G.arcs\[i\]\[j\] = arcs\[i\]\[j\];
return 0;
}
/***无向网的输出***/
int coutAMGraph(AMGraph &G)
{
int i, j;
cout << "该图的邻接矩阵为：" << endl;
cout << "\\t";
for (i = 0; i < G.vexnum; i++)
cout << G.vexs\[i\] << "\\t";
cout << endl;
for (i = 0; i < G.vexnum; i++)
{
cout << G.vexs\[i\] << "\\t";
for (j = 0; j < G.vexnum; j++)
{
cout << G.arcs\[i\]\[j\] << "\\t";
}
cout << endl;
}
}
/*****邻接表*****/
int LocateVex(ALGraph &G, char &v1) //定位函数
{
int i;
for (i = 0; i < G.vexnum; i++)
{
if (G.vertices\[i\].data == v1)
return i;
}
if (i >= G.vexnum)
return ERROR;
else
return 0;
}
/***创建无向图***/
int createGraphByAdjList(ALGraph &G)
{
ArcNode \*p1, \*p2;
int i, j, k;
char v1, v2;
VerTexType vetices\[7\]={'A','B','C','D','E','F','G'};
G.vexnum=7;
G.arcnum=9; //输入总顶点数、总边数
for (i = 0; i < G.vexnum; i++)
{
G.vertices\[i\].data=vetices\[i\]; //输入顶点值
G.vertices\[i\].firstarc = NULL; //初始化表头结点的指针域为NULL
}
char A\[50\]={'A','A','B','C','D','F','G','G','G'};
char B\[50\]={'B','D','C','F','E','D','A','F','C'};
for (k = 0; k < G.arcnum; k++)
{
v1=A\[k\];
v2=B\[k\]; //输入各边，构造邻接表
i = LocateVex(G, v1);
j = LocateVex(G, v2);
p1 = new ArcNode; //生成一个新结点*p1
p1->adjvex = j; //邻接点序号为j
p1->nextarc = G.vertices\[i\].firstarc;
G.vertices\[i\].firstarc = p1;
p2 = new ArcNode;
p2->adjvex = i;
p2->nextarc = G.vertices\[j\].firstarc;
G.vertices\[j\].firstarc = p2;
}
}
/***输出邻接表***/
int coutUDG(ALGraph G) //输出函数
{
int i, j;
cout << "该图邻接表为:" << endl;
for (i = 0; i<G.vexnum; i++)
{
cout << i;
ArcNode *p;
p = G.vertices\[i\].firstarc;
while (p != NULL)
{
cout << "-> " << p->adjvex;
p = p->nextarc;
}
cout << endl;
}
}
/*****十字链表*****/
int LocateVex(OLGraph G, char v) //// 返回顶点v在有向图G中的位置(序号),如不存在则返回-1
{
for (int u = 0; u<G.vexnum; u++)
if(G.xlist\[u\].data == v)
return u;
return -1;
}
/***十字链表存储表示*/
int createGraphByOrthLkList(OLGraph &G) // 采用十字链表存储表示,构造有向图G
{
int i, j, k;
int IncInfo;
ArcBox *p;
char v1, v2;
VerTexType vetices\[7\]={'A','B','C','D','E','F','G'};
G.vexnum=7;
G.arcnum=9; //输入总顶点数、总边数
for (i = 0; i<G.vexnum; ++i)
{
G.xlist\[i\].data=vetices\[i\];
G.xlist\[i\].firstin = NULL;
G.xlist\[i\].firstout = NULL;
}
char A\[50\]={'A','A','B','C','D','F','G','G','G'};
char B\[50\]={'B','D','C','F','E','D','A','F','C'};
for (k = 0; k<G.arcnum; ++k)
{
v1=A\[k\];
v2=B\[k\]; //输入各边
i = LocateVex(G, v1);
j = LocateVex(G, v2);
p = new ArcBox;
p->tailvex = i;
p->headvex = j;
p->hlink = G.xlist\[j\].firstin;
p->tlink = G.xlist\[i\].firstout;
G.xlist\[j\].firstin = G.xlist\[i\].firstout = p;
}
}
/***输出有向图***/
int Display(OLGraph G)
{
int i;
ArcBox *p;
cout << "该图十字链表为:" << endl;
cout << "共" << G.vexnum << "个顶点," << G.arcnum << "条弧:" << endl;
for (i = 0; i<G.vexnum; i++)
{
cout << "顶点" << G.xlist\[i\].data << ": 入度: ";
p = G.xlist\[i\].firstin;
while (p)
{
cout << G.xlist\[p->tailvex\].data<<" ";
p = p->hlink;
}
cout << "出度: ";
p = G.xlist\[i\].firstout;
while (p)
{
cout << G.xlist\[p->headvex\].data<<" ";
p = p->tlink;
}
cout << endl;
}
}
