图

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
template<class T>
class AdjGraph
{
private:
	T m_vertex[MAX_VERTEX_NUM];		// 顶点集合
	int m_nAdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];	// 邻接矩阵
	int m_nVertexNum;	// 顶点数目
	int m_nGraphType;	// 图的类型（0：无向图，1：有向图）
public:
	AdjGraph(int nGraphType);	// 创建图
	// 递归方式从下标nV的顶点对图做深度优先遍历
	bool DFSTraverse(int nV, int);
	// 由DFSTraverse调用以递归方式完成图的深度优先遍历
	void DFS(int nV, bool bVisited[]);
	// 非递归深度优先遍历
	bool DFSTraverse(int nV);
	// 下标为nV的顶点开始对图广度优先遍历
	bool BFSTraverse(int nV);
	int GetVertexNum();			// 获取顶点数目
	int GetFirstEdge(int nV);	// 获取与指定顶点nV相关的第一条边
	// 获取与指定边（nV1, nV2）或 <nV1，nV2>有相同关联顶点nV1的下一条边
	int GetNextEdge(int nV1, int nV2);
	bool AddOneVertex(const T& vertex);	// 添加一个顶点
	bool AddOneEdge(int nV1, int nV2, int nWeight);	// 添加一条边
	bool GetVertexValue(int nV, T& vertex);	// 获取顶点值
	bool IsEdge(int nV1, int nV2);		// 判断一条边是否存在
	bool SetEdgeWeight(int nV1, int nV2, int nWeight);	// 设置边的权重
	bool GetEdgeWeight(int nV1, int nV2, int nWeight);	// 获取边的权重
};

// 创建图
template<class T>
AdjGraph<T>::AdjGraph(int nGraphType)	// 图类型，0：无向图，1：有向图
{
	int nI, nJ;
	m_nGraphType = nGraphType;
	m_nVertexNum = 0;
	// 两任意节点边上权重无限大，初始时没有边
	for (nI = 0; nI < MAX_VERTEX_NUM; nI++)
		for (nJ = 0; nJ < MAX_VERTEX_NUM; nJ++)
			m_nAdjMatrix[nI][nJ] = INFINITY01;
}

// 获取顶点数目
template<class T>
int AdjGraph<T>::GetVertexNum()
{
	return m_nVertexNum;
}

// 判断一条边是否存在
template<class T>
bool AdjGraph<T>::IsEdge(int nV1, int nV2)
{
	// 权重为有限值，边存在
	return m_nAdjMatrix[nV1][nV2] != INFINITY01;
}

// 获取与指定顶点nV相关的第一条边
template<class T>
int AdjGraph<T>::GetFirstEdge(int nV)
{
	int nJ;
	if (nV < 0 || nV >= m_nVertexNum)
		return -1;
	for (nJ = 0; nJ < m_nVertexNum; nJ++)
		if (IsEdge(nV, nJ))
			return nJ;
	return -1;
}

// 获取与指定边（nV1, nV2）或 <nV1，nV2>有相同关联顶点nV1的下一条边
template<class T>
int AdjGraph<T>::GetNextEdge(int nV1, int nV2)
{
	int nJ;
	if (!IsEdge(nV1, nV2))
		return -1;
	// 访问nV2后面的顶点，找到下一条与nV1有关的边
	for (nJ = nV2 + 1; nJ < m_nVertexNum; nJ++)
		if (IsEdge(nV1, nJ))
			return nJ;
	return -1;
}

// 添加一个顶点
template<class T>
bool AdjGraph<T>::AddOneVertex(const T& vertex)
{
	if (m_nVertexNum >= MAX_VERTEX_NUM)
		return false;
	m_vertex[m_nVertexNum] = vertex;
	m_nVertexNum++;
	return true;
}

// 获取顶点值，获取nV顶点的数据放到vertex中
template<class T>
bool AdjGraph<T>::GetVertexValue(int nV, T& vertex)
{
	if (nV < 0 || nV >= m_nVertexNum)
		return false;
	vertex = m_vertex[nV];
	return true;
}

// 添加一条边
template<class T>
bool AdjGraph<T>::AddOneEdge(int nV1, int nV2, int nWeight)
{
	// 两个顶点必须存在且无边
	if (nV1 < 0 || nV1 >= m_nVertexNum || nV2 < 0 || nV2 >= m_nVertexNum || IsEdge(nV1, nV2))
		return false;
	m_nAdjMatrix[nV1][nV2] = nWeight;
	if (m_nGraphType == 0)	// 无向图
		m_nAdjMatrix[nV2][nV1] = nWeight;
	return true;
}

// 设置边的权重
template<class T>
bool AdjGraph<T>::SetEdgeWeight(int nV1, int nV2, int nWeight)
{
	if (!IsEdge(nV1, nV2))
		return false;
	m_nAdjMatrix[nV1][nV2] = nWeight;
	return true;
}

// 获取边的权重
template<class T>
bool AdjGraph<T>::GetEdgeWeight(int nV1, int nV2, int nWeight)
{
	if (!IsEdge(nV1, nV2))
		return false;
	nWeight = m_nAdjMatrix[nV1][nV2];
	return true;
}


// 非递归方式从下标nV的顶点对图做广度优先遍历
template<class T>
bool AdjGraph<T>::BFSTraverse(int nV)
{
	LinkQueue<int> queue;
	int nVisitVertex, nVertex, nBegVertex = nV;
	bool bVisited[MAX_VERTEX_NUM];		// 记录每个顶点是否已访问
	T vertex;
	if (nV<0 || nV>=m_nVertexNum)
		return false;
	memset(bVisited, 0, sizeof(bVisited));	// 各顶点均设置为未访问
	while (1)
	{
		queue.Insert(nBegVertex);
		bVisited[nBegVertex] = true;
		while (!queue.IsEmpty())
		{
			queue.Delete(nVisitVertex);
			GetVertexValue(nVisitVertex, vertex);
			cout << vertex << ' ';
			nVertex = GetFirstEdge(nVisitVertex);
			while (nVertex != -1)
			{
				if (bVisited[nVertex] == false)
				{
					queue.Insert(nVertex);
					bVisited[nVertex] = true;
				}
				nVertex = GetNextEdge(nVisitVertex, nVertex);
			}
		}
		// 如果还有未访问到的顶点，从该顶点再次遍历
		int n = nBegVertex + 1;
		for (; n < m_nVertexNum + nV; n++)
		{
			if (bVisited[n % m_nVertexNum] == false)
			{
				nBegVertex = n % m_nVertexNum;
				break;
			}
		}
		// 所有顶点已访问 退出循环
		if (n == m_nVertexNum + nV)
			break;
	}
	return true;
}


// 递归方式从下标nV的顶点对图做深度优先遍历
template<class T>
bool AdjGraph<T>::DFSTraverse(int nV, int)
{
	int nBegVertex;
	bool bVisited[MAX_VERTEX_NUM];
	// 若下标为nV顶点不存在，遍历失败
	if (nV < 0 || nV >= m_nVertexNum)
		return false;
	// 各顶点均设置未访问状态
	memset(bVisited, 0, sizeof(bVisited));
	// 对图中每个顶点若未访问则要访问，该顶点开始，调用DFS递归
	for (nBegVertex=nV; nBegVertex < m_nVertexNum + nV; nBegVertex++)
	{
		if (bVisited[nBegVertex % m_nVertexNum] == false)
			DFS(nBegVertex, bVisited);
	}
	return true;
}

// 由DFSTraverse调用以递归方式完成图的深度优先遍历
template<class T>
void AdjGraph<T>::DFS(int nV, bool bVisited[])
{
	T vertex;
	int nVertex;
	// 先访问当前顶点并设为已访问
	GetVertexValue(nV, vertex);
	cout << vertex << ' ';
	bVisited[nV] = true;
	// 逐个获取当前顶点邻接的顶点，若未访问则DFS遍历
	nVertex = GetFirstEdge(nV);
	while (nVertex != 1)
	{
		if (bVisited[nVertex] == false)
			DFS(nVertex, bVisited);
		nVertex = GetNextEdge(nV, nVertex);
	}
}