初始化四个弧：
0 1
0 2
3 1
3 2
1
2 #include <iostream>
3 #include <queue>
4 using namespace std;
5
6 const int MAXSIZE = 10; //最多的顶点数
7
8 struct ArcNode
9 {
10 int adjvex; //结点在数组中的序号
11 ArcNode* next;
12 };
13 template<class T>
14 struct VertexNode
15 {
16 T vertex; //结点名字
17 ArcNode *firstedge;
18 };
19
20
21 template<class T>
22 class ALGraph
23 {
24 public:
25 ALGraph(){}
26 ALGraph(T a[], int n, int e); //构造函数，初始哈一个有n个顶点e条边的图
27 ~ALGraph(); //析构函数，释放邻接表中各边表结点的存储空间
28 T GetVex(int i); //取图中第i个顶点数据信息
29 void PutVex(int i, T value); //将图中第i个顶点的数据域置为value
30 void InsertVex(T value); //在图中插入一个顶点，值为value
31 void DeleteVex(int i); //删除结点序号为i的结点
32 void InsertArc(int i, int j); //在图中插入一条边，其依附的两个顶点标号为i和j
33 void DeleteArc(int i, int j); //删除一边，顶点编号i和j
34 void DFSTraverse(int v);
35 void BFSTraverse(int v);
36
37 private:
38 VertexNode<T> adjlist[MAXSIZE]; //存放顶点表的数组
39 int vertexNum, arcNum; //图的顶点数和边数
40 int visited[MAXSIZE];
41 };
42
43 int main()
44 {
45 char a[4] = { 'a','b','c','d' };
46 ALGraph<char> ag(a,4,4);
47 ag.BFSTraverse(0);
48 system("pause");
49 return 0;
50 }
51
52 template<class T>
53 ALGraph<T>::ALGraph(T a[], int n, int e)
54 {
55 int p1, p2;
56 ArcNode *s;
57
58 vertexNum = n, arcNum = e;
59 for (int i = 0; i < vertexNum; i++) //顶点信息存储在二维数组中，下标从0开始
60 {
61 adjlist[i].vertex = a[i];
62 adjlist[i].firstedge = NULL;
63 }
64 for (int i = 0; i < arcNum; i++)
65 {
66 cin >> p1 >> p2; //弧尾和弧头结点序号
67 s = new ArcNode;
68 s->adjvex = p2; //记录弧尾指向结点的序号
69 s->next = adjlist[p1].firstedge;//插入关联弧
70 adjlist[p1].firstedge = s;
71 }
72 for (int i = 0; i < MAXSIZE; i++)
73 visited[i] = 0;
74 }
75
76 template<class T>
77 ALGraph<T>::~ALGraph()
78 {
79 ArcNode *p, *s;
80 for (int i = 0; i < vertexNum; i++)
81 {
82 s = adjlist[i].firstedge;
83 while (NULL != s) {
84 p = s;
85 s = s->next;
86 delete p;
87 }
88 }
89 arcNum = vertexNum = 0;
90 }
91
92 template<class T>
93 T ALGraph<T>::GetVex(int i)
94 {
95 if (i < 0 || i >= vertexNum)
96 {
97 throw"顶点不存在";
98 }
99 else
100 {
101 return adjlist[i].vertex; //返回第i个顶点的数据信息
102 }
103 }
104
105 template<class T>
106 void ALGraph<T>::PutVex(int i, T value)
107 {
108 if (i < 0 || i >= vertexNum)
109 {
110 cout << "结点不存在" << endl;
111 return;
112 }
113 else
114 {
115 adjlist[i].vertex = value; //替换第i个顶点的数据信息
116 }
117 }
118
119 template<class T>
120 void ALGraph<T>::InsertVex(T value)
121 {
122 int flag = 0;
123 for (int i = 0; i < vertexNum; i++)
124 {
125 if (adjlist[i].vertex == value)
126 {
127 cout << "结点已存在" << endl;
128 flag = 1;
129 return;
130 }
131 }
132 if (!flag) //不在图中，则新增结点
133 {
134 adjlist[vertexNum].fisrtedge = NULL;
135 adjlist[vertexNum++].vertex = value;
136 }
137 }
138
139 template<class T>
140 void ALGraph<T>::DeleteVex(int i)
141 {
142 if (i < 0 || i >= vertexNum)
143 {
144 cout << "结点不存在" << endl;
145 return;
146 }
147
148 ArcNode *s, *d;
149 s = adjlist[i].firstedge;
150 while (s != NULL) {
151 d = s;
152 s = s->next;
153 delete d;
154 arcNum--;
155 }
156 //横移
157 if (i != vertexNum - 1)
158 {
159 for (int j = i + 1; j < vertexNum; j++)
160 {
161 adjlist[j - 1].vertex = adjlist[j].vertex;
162 adjlist[j - 1].firstedge = adjlist[j].firstedge;
163 }
164 }
165 vertexNum--;
166 }
167
168 template<class T>
169 void ALGraph<T>::InsertArc(int i, int j)
170 {
171 if (i < 0 || i >= vertexNum)
172 {
173 cout << "结点不存在" << endl;
174 return;
175 }
176 ArcNode *s, *p;
177 s = adjlist[i].firstedge;
178 p = adjlist[i].firstedge;
179 if (NULL == s) {
180 p = new ArcNode;
181 p->adjvex = j;
182 p->next = NULL;
183 arcNum++;
184 return;
185 }
186 while (NULL != s) {
187 if (j == s->adjvex) {
188 cout << "弧已存在" << endl;
189 return;
190 }
191 p = s; //最后一弧
192 s = s->next;
193 }
194 s = new ArcNode; //动态分配内存
195 p->next = s;
196 s->adjvex = j;
197 s->next = NULL;
198 arcNum++;
199 }
200
201 template<class T>
202 void ALGraph<T>::DeleteArc(int i, int j)
203 {
204 if (i < 0 || i >= vertexNum && j < 0 || j >= vertexNum)
205 {
206 cout << "顶点不存在" << endl;
207 return;
208 }
209
210 int flag = 0;
211 ArcNode *s, *r;
212 s = adjlist[i].firstedge;
213 r = adjlist[i].firstedge;
214 while (s != NULL)
215 {
216 if (s->adjvex == j) {
217 flag = 1;
218 if (s == r) {
219 if (NULL == s->next) {
220 delete s;
221 adjlist[i].firstedge = NULL;
222 arcNum--;
223 return;
224 }
225 else
226 {
227 adjlist[i].firstedge = r->next;
228 delete s;
229 arcNum--;
230 return;
231 }
232 }
233 else
234 {
235 if (NULL == s->next) {
236 delete s;
237 r->next = NULL;
238 arcNum--;
239 return;
240 }
241 else {
242 r->next = s->next;
243 delete s;
244 arcNum--;
245 return;
246 }
247 }
248 }
249 r = s;
250 s = s->next;
251 }
252 if (!flag) {
253 cout << "弧不存在" << endl;
254 }
255 }
256
257 template<class T>
258 void ALGraph<T>::DFSTraverse(int v)
259 {
260 cout << adjlist[v].vertex << '\t';
261 visited[v] = 1;
262 ArcNode *p = adjlist[v].firstedge;
263 while (p) {
264 int j = p->adjvex;
265 if (0 == visited[j]) {
266 DFSTraverse(j);
267 }
268 p = p->next;
269 }
270 }
271
272 template<class T>
273 void ALGraph<T>::BFSTraverse(int v)
274 {
275 int visited[MAXSIZE];
276 for (int i = 0; i < vertexNum; i++)
277 visited[i] = 0;
278
279 int temp, j;
280 ArcNode *p;
281 queue<int> Qu;
282 cout << adjlist[v].vertex << '\t';
283 visited[v] = 1;
284 Qu.push(v);
285 while (!Qu.empty()) {
286 temp = Qu.front();
287 Qu.pop();
288
289 p = adjlist[temp].firstedge;
290 while (NULL != p) {
291 j = p->adjvex;
292 if (!visited[j]) {
293 cout << adjlist[p->adjvex].vertex << '\t';
294 Qu.push(j);
295 }
296 p = p->next;
297 }
298 }
299 }