[算法]模式识别-Graph

Author Avatar
与狼同行 11月 25, 2016

#Graph

图的实现是一件很麻烦的事情,很多同学可能在学数据结构时只是理解了图的基本操作和遍历原理,但并没有动手实践过。在此,我说说我的实现过程。

首先,在草稿纸上画一个图表,这里是有向图,无向图也一样,如下:
我用的是vector+vector容器作为存储结构,如下: vector+vector)
|0|——|1|——|3|
|1|——|2|——|3|
|2|——|3|
|3|

第二步,用自然语言建立这个图,注意数据结构的书一般没有说明图是怎么建立的,在此我简述一下:

1)、加入 4个顶点——G.InsertVextex(V);

2)、在两个顶点之间增加有向弧——G.AddEdge(x, y)。

这样图就建立了。

我写了两个Graph的构造函数,也可以直接用一个数组实现1)的操作如下:

vector v(4);

Graph G(v);

第三步,广度优先遍历和深度优先遍历。遍历的目的是为了对每个顶点进行一些处理,能够遍历这个图是其他操作的基础。甚至可以用遍历的方法建立这个图,就像我之前用先序遍历建立二叉树一个道理。

这三步完成,图的实现就基本解决了。至于最小生成树、关键路径等问题,以后再说。

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
#include <queue>
#include <stdio.h>
using namespace std;
typedef int DataType;
const DataType INIT_DATA = -1;
const int NO_NODE = -1;
const int NO_EDGE = -2;
class VNode{
public:
//data member
bool visited; //访问标志
DataType data; //顶点内的数据
vector<int> e; //邻接的边
//member function
VNode(DataType val = INIT_DATA, bool flag = false):data(val), visited(flag){}
void Visit()
{
cout<<data<<"\t";
}
bool operator== (VNode &y){
if(data == y.data && e == y.e)
return true;
else
return false;
}
};
class Graph{
public:
//data member
int vexnum; //图中顶点数
int edgenum; //图中边数
vector<VNode> V; //图的存储结构
//member function
Graph()
{
vexnum = 0;
edgenum = 0;
}
Graph(vector<VNode> &v);
int GetVexNum();
int GetEdgeNum();
//节点操作
void InsertVertex(VNode &x);
bool DeleteVertex(int x);
//边的操作
//bool IfEdge(int x, int y); //判断是否有(x, y)的边
bool AddEdge(int x, int y);
bool RemoveEdge(int x, int y);
//邻边操作
void PrintNeighbors(int x); //
VNode &Neighbor(VNode &x, int n); //x的第n个邻接节点,默认n为第一个
//广度遍历和深度遍历
void BreadthFirstSearch();
void BFS(VNode &x); //队列实现
void DepthFirstSearch();
void DFS(VNode &x); //递归函数
~Graph(){};
};
Graph::Graph(vector<VNode> &v)
{
V.assign(v.begin(), v.end());
vexnum = V.size();
edgenum = GetEdgeNum();
}
int Graph::GetVexNum()
{
vexnum = V.size();
return vexnum;
}
int Graph::GetEdgeNum()
{
edgenum = 0;
for(vector<VNode>::iterator iter = V.begin(); iter != V.end(); ++iter)
{
edgenum += iter->e.size();
}
return edgenum;
}
void Graph::InsertVertex(VNode &x)
{
V.push_back(x);
vexnum++;
}
//删除x节点
bool Graph::DeleteVertex(int x)
{
if(x >= V.size() || x < 0)
{
cout<<"没有相应节点"<<endl;
return false;
}
vector<VNode>::iterator iter = V.begin()+x;
V.erase(iter);
vexnum--;
return true;
}
bool Graph::AddEdge(int x, int y)
{
if((x >= V.size() || x < 0) || (y >= V.size() || y < 0))
{
cout<<"没有相应节点"<<endl;
return false;
}
int size = V[x].e.size();
for(vector<int>::iterator iter = V[x].e.begin(); iter != V[x].e.end(); ++iter)
{
if(V[*iter] == V[y]) //已经有(x, y)
{
cout<<"已经有弧(x, y)"<<endl;
return false;
}
}
V[x].e.push_back(y); //没有,则把y加入x的邻边队列中
edgenum++;
return true;
}
bool Graph::RemoveEdge(int x, int y)
{
if((x >= V.size() || x < 0) || (y >= V.size() || y < 0))
{
cout<<"没有相应节点"<<endl;
return false;
}
for(vector<int>::iterator iter = V[x].e.begin(); iter != V[x].e.end(); ++iter)
{
if(V[*iter] == V[y])
{
V[x].e.erase(iter);
edgenum--;
return true;
}
}
cout<<"没有弧(x, y)"<<endl;
return false;
}
//邻边操作
void Graph::PrintNeighbors(int x)
{
cout<<"列出节点"<<x<<"的所有邻接节点"<<endl;
for(vector<int>::iterator iter = V[x].e.begin(); iter != V[x].e.end(); ++iter)
{
cout<<*iter<<"\t";
}
cout<<endl;
}
VNode &Graph::Neighbor(VNode &x, int n = 1)
{
if(n > x.e.size() || n <= 0)
{
cout<<"没有相应边"<<endl;
exit(0);
}
return V[(x.e[n-1])];
}
/******
遍历
**********/
void Graph::BreadthFirstSearch()
{
for(int i = 0; i != vexnum; ++i)
{
if(!V[i].visited)
BFS(V[i]);
}
for(vector<VNode>::iterator k = V.begin(); k != V.end(); ++k)
k->visited = false;
}
void Graph::BFS(VNode &x)
{
queue<VNode> q;
q.push(x);
while(!q.empty())
{
VNode &_x = q.front();
if(!_x.visited)
{
_x.Visit();
_x.visited = true;
int size = _x.e.size();
for(int i = 0; i < size; ++i)
{
VNode &w = V[_x.e[i]];
if(!w.visited)
{
w.Visit();
w.visited = true;
q.push(w);
}
}
}
q.pop();
}
}
void Graph::DepthFirstSearch()
{
for(int i = 0; i != vexnum; ++i)
{
if(!V[i].visited)
DFS(V[i]);
}
for(vector<VNode>::iterator k = V.begin(); k != V.end(); ++k)//改变访问标志,以便下次访问
k->visited = false;
}
void Graph::DFS(VNode &x)
{
x.Visit();
x.visited = true;
int size = x.e.size();
for(int i = 0; i < size; ++i)
{
VNode &w = V[x.e[i]];
if(!w.visited)
DFS(w);
}
}