发表于 | 更新于: | 分类于 ， |
字数统计: 1.6k | 阅读时长 ≈ 6

§1　向量组及其线性组合

定义1　n个有次序的数$a_1,a_2,\dots,a_n$所组成的数组称为n维向量，这n个数称为该向量的n个分量，第i个数$a_i$称为第i个分量。

定义2　给定向量组$A:a_1,a_2,\dots,a_m,$对于任何一组实数$k_1,k_2,\dots,k_m,$表达式

称为向量组$A$的一个线性组合，$k_1,k_2,\dots,k_m$称为这个线性组合的系数。

给定向量组$A:a_1,a_2,\dots,a_m​$和向量$b​$，如果存在一组数$\lambda_1,\lambda_2,\dots,\lambda_m,​$使

则向量$b$是向量组$A$的线性组合，称向量$b$能由向量组$A$线性表示。

定理1　向量$b​$能由向量组$A:a_1,a_2,\dots,a_m​$线性表示的充分必要条件是矩阵$A=(a_1,a_2,\dots,a_m)​$的秩等于矩阵$B=(a_1,a_2\dots,a_m,b)​$的秩。

定义3　设有两个向量组$A:a_1,a_2,\dots,a_m​$及$B:b_1,b_2,\dots,b_l,​$若$B​$组中的每个向量都能由向量组$A​$线性表示，则称向量组$B​$能由向量组$A​$线性表示。若向量组$A​$与向量组$B​$都互相线性表示，则称这两个向量组等价。

定理2　向量组$B:b_1,b_2,\dots,b_l​$能由向量组$A:a_1,a_2,\dots,a_m​$线性表示的充分必要条件是矩阵$A=(a_1,a_2,\dots,a_m)​$的秩等于矩阵$(A,B)=(a_1,\dots,a_m,b_1,\dots,b_l)​$的秩，即$R(A)=R(A,B)​$。

推论　向量组$A:a_1,a_2,\dots,a_m​$与向量组$B:b_1,b_2,\dots,b_l​$等价的充分必要条件是

其中$A$和$B$是向量组$A$和$B$所构成的矩阵。

定理3　设向量组$B:b_1,b_2,\dots,b_l​$能由向量组$A:a_1,a_2,\dots,a_m​$线性表示，则$R(b_1,b_2,\dots,b_l)\leq R(a_1,a_2,\dots,a_m)​$。

§2　向量组的线性相关性

定义4　给定向量组$A:a_1,a_2,\dots,a_m,$如果存在不全为零的数$k_1,k_2,\dots,k_m,$使

则称向量组$A$是线性相关的，否则称它线性无关。

定理4　向量组$A:a_1,a_2,\dots,a_m​$线性相关的充分必要条件是它所构成的矩阵$A=(a_1,a_2,\dots,a_m)​$的秩小于向量个数m；向量组$A​$线性无关的充分必要条件是$R(A)=m​$。

定理5　(1)若向量组$A:a1,a_2,\dots,a_m​$线性相关，则向量组$B:a_1,a_2,\dots,a_m,a{m+1}​$也线性相关。反之，若向量组$B​$线性无关，则向量组$A​$也线性无关。

(2)m个n维向量组成的向量组，当维数n小于向量个数m时一定线性相关。特别地n+1个n维向量一定线性相关。

(3)设向量组$A:a_1,a_2,\dots,a_m$线性无关，而向量组$B:a_1,a_2,\dots,a_m,b$线性相关，则向量$b$必能由向量组$A$线性表示，且表示式是惟一的。

阅读全文 »

发表于 | 更新于: | 分类于 ， ， |
字数统计: 193 | 阅读时长 ≈ 1 
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
#include <iostream>
#include<cstdio>
#include<cstring>
#include <algorithm>
using namespace std;
int dp[100009], c[100009], w[100009], m[100009];
int n, M, t;
void zeropack(int cost, int weight)
{
	for (int i = M; i >= cost; i--)
		dp[i] = max(dp[i - cost] + weight, dp[i]);
}
void completepack(int cost, int weight)
{
	for (int i = cost; i <= M; i++)
		dp[i] = max(dp[i - cost] + weight, dp[i]);
}
void multipack(int cost, int weight, int num)
{
	if (num*cost >= M)
	{
		completepack(cost, weight);
		return;
	}
	int k = 1;
	while (k < num)
	{
		zeropack(k*cost, k*weight);
		num -= k;
		k *= 2;
	}

	zeropack(cost*num, weight*num);
}
int main()
{
	while (~scanf("%d%d", &M, &n))
	{
		for (int i = 1; i <= n; i++) { scanf("%d%d", &m[i], &c[i]); w[i] = c[i]; }
		memset(dp, 0, sizeof(dp));
		for (int i = 1; i <= n; i++)
		{
			multipack(c[i], w[i], m[i]);
		}
		printf("%d\n", dp[M]);
	}
	return 0;
}

发表于 | 更新于: | 分类于 ， |
字数统计: 1.3k | 阅读时长 ≈ 5

§1　矩阵的初等变换

定义1　下面三种变换称为矩阵的初等行变换：

(i)对换两行(对换i,j两行，记作$r_i\leftrightarrow r_j$)；

(ii)以数$k\neq0​$乘某一行中的所有元(第i行乘k，记作$r_i\times k​$)；

(iii)把某一行所有元的k倍加到另一行对应的元上去(第j行的k倍加到第i行上，记作$r_i+kr_j$)。

把行换成列，即得初等列变换的定义。统称初等变换。

如果$A$经有限次初等变换变成$B$，就称$A$与$B$等价，记作$A\sim B$。矩阵之间的等价关系具有下列性质：

(i)反身性　$A\sim A$；

(ii)对称性　若$A\sim B$，则$B\sim A$；

(iii)传递性　若$A\sim B$，$B\sim C$，则$A\sim C$。

定义2　(1)非零矩阵若满足(i)非零行在零行的上面；(ii)非零行的首非零元所在列在上一行的首非零元所在列的右面，则称此矩阵为行阶梯形矩阵；

(2)进一步，若$A$是行阶梯形矩阵，并且还满足：(i)非零行的首非零元素为1；(ii)首非零元所在的列的其他元均为0，则称$A$为行最简形矩阵。

对于任何非零矩阵$A_{m\times n}$，总可经有限次初等行变换把它变为行阶梯形矩阵和行最简形矩阵。

对最简形矩阵再施以初等列变换，可化为标准形。对于$m\times n$矩阵$A$，总可经过初等变换把它化为标准形

定理1　设$A$与$B$为$m\times n$矩阵，那么

(i)$A$与$B$行等价的充分必要条件是存在m阶可逆矩阵$P$，使$PA=B$；

(ii)$A​$与$B​$列等价的充分必要条件是存在n阶可逆矩阵$Q​$，使$AQ=B​$；

(iii)$A$与$B$等价的充分必要条件是存在m阶可逆矩阵$P$及n阶可逆矩阵$Q$，使$PAQ=B$。

定义3　由单位矩阵$E$经过一次初等变换得到的矩阵称为初等矩阵。

性质1　设$A$是一个$m\times n$矩阵，对$A$施行一次初等行变换，相当于在$A$的左边乘相应的m阶初等矩阵；对$A$施行一次初等列变换，相当于在$A$的右边乘相应的n阶初等矩阵

性质2　方阵$A$可逆的充分必要条件是存在有限个初等矩阵$P_1,P_2,\dots,P_l,$使$A=P_1P_2\dots P_l$。

推论　方阵$A$可逆的充分必要条件是$A$和$E$行等价

有可逆矩阵$P$，使$PA=B$，求可逆矩阵$P$：

由于

即$(A,E)$与$(B,P)$行等价，因此如果对矩阵$(A,E)$作初等行变换，当把$A$变为$B$时，$E$就变为$P$。

阅读全文 »

发表于 | 更新于: | 分类于 ， |
字数统计: 1.6k | 阅读时长 ≈ 7

§1　线性方程组和矩阵

一、线性方程组

设有n个未知数m个方程的线性方程组。当常数项不全为零时，线性方程组叫做n元非齐次线性方程组，当常数项全为零时，叫做n元齐次线性方程组

n元齐次线性方程组一定有零解，不一定有非零解。

二、矩阵的定义

定义1　由m$\times$n个数$a_{ij}(i=1,2,\dots,m;j=1,2,\dots,n)$排成的m行n列的数表

称为m行n列矩阵。记作

只有一行(列)的矩阵称为行(列)矩阵或行(列)向量。行数与列数相等的矩阵称为同型矩阵。元素都是0的矩阵称为零矩阵，记作$O$。

对于非齐次线性方程组，有

其中$A$称为系数矩阵，$x$称为未知数矩阵，$b$称为常数项矩阵，$B$称为增广矩阵。

对角线以外的元素都是0的矩阵称为对角矩阵，记作

线性变换与矩阵一一对应。

对角线全是1，其他全0的矩阵称为单位阵$E$，对应的线性变换称为恒等变换。

阅读全文 »

发表于 | 更新于: | 分类于 ， |
字数统计: 1.3k | 阅读时长 ≈ 5

§1　二阶与三阶行列式

定义1　设有9个数排成3行3列的数表

记

(6)式称为数表(5)所确定的三阶行列式

§2　全排列和对换

一、排列及其逆序数

对于n个不同元素规定一个标准次序，n个元素任一排列中当某对元素先后次序与标准次序不同时，构成一个逆序，逆序的总数叫做这个排列的逆序数。

逆序数为奇数的叫奇排列，反之为偶排列。

二、对换

排列中，将任意两元素对调，其余元素不动，称为对换。

定理1　一个排列中的任意两个元素对换，排列改变奇偶性。

推论　奇排列对换成标准排列的对换次数为奇数，偶排列对换成标准排列的对换次数为偶数。

阅读全文 »

发表于 | 更新于: | 分类于 |
字数统计: 2.9k | 阅读时长 ≈ 11

第2章　模型评估与选择

2.1　经验误差与过拟合

错误率(error rate) and 精度(accuracy)：分类错误的样本数占样本总数的比例称为“错误率”，如果在m个样本中有a个样本分类错误，则错误率E=a/m；相应的1-a/m称为“精度”。

误差(error)：学习器的实际预测输出与样本的真实输出之间的差异。

训练误差(training error) or 经验误差(empirical error)：学习器在训练集上的误差。

泛化误差(generalization error)：学习器在新样本上的误差。

过拟合(overfitting) and 欠拟合(underfitting)：学习器把训练样本自身的一些特点当作了所有潜在样本都会具有的一般性质，导致泛化性能下降的现象称为“过拟合”，相对的，“欠拟合”指对训练样本的一般性质尚未学好。

欠拟合比较容易克服，过拟合是机器学习面临的关键障碍。过拟合是无法彻底避免的，只能减小其风险。可以这样理解：机器学习面临的问题通常是NP难甚至更难，而有效的学习算法必然是在多项式时间内运行完成，若可彻底避免过拟合，则通过经验误差最小化就能获最优解，这就意味着我们构造性地证明了“P=NP”；因此，只要相信”P$\neq​$NP“，过拟合就不可避免。

模型选择(model selection)：现实任务中，往往有多种学习算法可供选择，对同一个学习算法，使用不同的参数配置时，也会产生不同的模型。选用哪一个学习算法、使用哪一种参数配置的问题，称为”模型选择“问题。

阅读全文 »

发表于 | 更新于: | 分类于 ， |
字数统计: 1.2k | 阅读时长 ≈ 5

Description

上课的时候总会有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的D对同学上课时会交头接耳。

同学们在教室中坐成了M行N列，坐在第i行第j列的同学的位置是(i,j)(i,j)，为了方便同学们进出，在教室中设置了K条横向的通道，L条纵向的通道。

于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了2个会交头接耳的同学，那么他们就不会交头接耳了。

请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生的对数最少。

Input

第一行，有5个用空格隔开的整数，分别是M,N,K,L,D(2 $\leq$ N,M $\leq$ 1000,0 $\leq$ K<M,0 $\leq$ L<N,D $\leq$ 2000)

接下来的D行，每行有4个用空格隔开的整数。第i行的4个整数Xi,Yi,Pi,Qi，表示坐在位置(Xi,Yi)与(Pi,Qi)的两个同学会交头接耳（输入保证他们前后相邻或者左右相邻）。

输入数据保证最优方案的唯一性。

Output

共两行。
第一行包含K个整数a1,a2,…,aK，表示第a1行和a1+1行之间、第a2行和a2+1行之间、…、第aK行和第aK+1行之间要开辟通道，其中ai<ai+1，每两个整数之间用空格隔开（行尾没有空格）。

第二行包含L个整数b1,b2,…,bL，表示第b1列和b1+1列之间、第b2列和b2+1列之间、…、第bL列和第bL+1列之间要开辟通道，其中bi<bi+1，每两个整数之间用空格隔开（列尾没有空格）。

Sample Input

1
2
3
4
4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4

Sample Output

1
2
2
2 4
阅读全文 »

发表于 | 更新于: | 分类于 |
字数统计: 1.9k | 阅读时长 ≈ 7

第1章　绪论

1.1　引言

机器学习是这样一门学科，它致力于研究如何通过计算的手段，利用经验来改善系统自身的性能。在计算机系统中，”经验“通常以”数据“形式存在，因此，机器学习所研究的主要内容，是关于在计算机上从数据中产生”模型“(model)的算法，即”学习算法“(learning algorithm)。有了学习算法，我们把经验数据提供给它，它就能基于这些数据产生模型；在面对新的情况时，模型会给我们提供相应的判断。

[Mitchell,1997]给出了一个更形式化的定义：假设用P来评估计算机程序在某任务类T上的性能，若一个程序通过利用经验E在T中任务上获得了性能改善，则我们说关于T和P，该程序对E进行了学习。

阅读全文 »

发表于 | 更新于: | 分类于 ， |
字数统计: 1.1k | 阅读时长 ≈ 6

线索二叉树的定义、实现、三种线索化方式以及其对应的遍历方式。

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
#include <iostream>
using namespace std;
typedef struct BiThrNode {//线索二叉树的结点
	int data;//数据域
	BiThrNode *lchild, *rchild;//左右孩子指针
	BiThrNode *parent;
	int LTag = 0, RTag = 0;//左右标志
}BiThrNode, *BiThrTree;

class ThreadBiTree {
private:
	BiThrNode *bt;//根结点
	BiThrNode *pre;
	void RCreate(BiThrNode *p, int k, int end);
public:
	BiThrNode *Thrt;//头结点
	ThreadBiTree() { bt = NULL; pre = NULL; Thrt = new BiThrNode; }//构造函数，对二叉链表进行初始化
	void CreateBiTree(int end);
	BiThrNode *Getroot();//二叉树不为空获取根结点指针，否则返回NULL
	void BiTreeDisplay(BiThrNode *bt, int level);//二叉树的树形显示算法
	void PreThreading(BiThrTree p);//先序线索化递归函数
	int PreOrderThreading(BiThrTree &Thrt, BiThrTree T);//先序遍历进行先序线索化
	int PreOrderTraverse_Thr(BiThrTree T);//先序遍历线索二叉树的非递归算法
	void InThreading(BiThrTree p);//中序线索化递归函数
	int InOrderThreading(BiThrTree &Thrt, BiThrTree T);//中序遍历进行中序线索化
	int InOrderTraverse_Thr(BiThrTree T);//中序遍历线索二叉树的非递归算法
	void PostThreading(BiThrTree p);//后序线索化递归函数
	int PostOrderTraverse_Thr(BiThrTree T);//后序遍历线索二叉树的非递归算法
};

void ThreadBiTree::RCreate(BiThrNode * p, int k, int end) {
	BiThrNode *q;
	int e;
	cin >> e;
	if (e != end) {
		q = new BiThrNode;
		q->data = e;
		q->lchild = NULL;
		q->rchild = NULL;
		q->parent = p;
		if (k == 1) p->lchild = q;
		if (k == 2) p->rchild = q;
		RCreate(q, 1, end);
		RCreate(q, 2, end);
	}
}

void ThreadBiTree::CreateBiTree(int end) {
	cout << "请按先序序列的顺序输入二叉树，0为空指针域标志：" << endl;
	BiThrNode *p;
	int e;
	cin >> e;
	if (e == end) return;
	p = new BiThrNode;
	if (!p) {
		cout << "申请内存失败！" << endl;
		exit(-1);
	}
	p->data = e;
	p->lchild = NULL;
	p->rchild = NULL;
	bt = p;
	RCreate(p, 1, end);
	RCreate(p, 2, end);
}

BiThrNode * ThreadBiTree::Getroot() {
	if (bt != NULL) return bt;
	return NULL;
}



void ThreadBiTree::BiTreeDisplay(BiThrNode * bt, int level) {
	if (bt) {
		BiTreeDisplay(bt->rchild, level + 1);
		for (int i = 0; i < level; i++) cout << "  ";
		cout << bt->data << endl;
		BiTreeDisplay(bt->lchild, level + 1);
	}
}

void ThreadBiTree::PreThreading(BiThrTree p) {
	if (p) {
		if (!p->lchild) p->LTag = 1, p->lchild = pre;
		if (pre != NULL && !pre->rchild) pre->RTag = 1, pre->rchild = p;
		pre = p;
		if (p->LTag == 0) PreThreading(p->lchild);
		if (p->RTag == 0) PreThreading(p->rchild);
	}
}

int ThreadBiTree::PreOrderThreading(BiThrTree & Thrt, BiThrTree T) {
	Thrt->LTag = 0; Thrt->RTag = 1;
	Thrt->rchild = Thrt;
	if (!T) Thrt->lchild = Thrt;
	else {
		Thrt->lchild = T; pre = Thrt;
		PreThreading(T);
		pre->rchild = Thrt; pre->RTag = 1;
		Thrt->rchild = pre;
	}
	return 1;
}

int ThreadBiTree::PreOrderTraverse_Thr(BiThrTree T) {
	BiThrNode *p;
	p = T->lchild;
	while (p != T) {
		while (p->lchild != NULL && p->LTag == 0) {
			cout << p->data << " ";
			p = p->lchild;
		}
		cout << p->data << " ";
		if (p->LTag == 1) p = p->rchild;
	}
	return 1;
}

void ThreadBiTree::InThreading(BiThrTree p) {
	if (p) {
		InThreading(p->lchild);
		if (!p->lchild) p->LTag = 1, p->lchild = pre;
		if (!pre->rchild) pre->RTag = 1, pre->rchild = p;
		pre = p;
		InThreading(p->rchild);
	}
}

int ThreadBiTree::InOrderThreading(BiThrTree & Thrt, BiThrTree T) {
	Thrt->LTag = 0; Thrt->RTag = 1;//Thrt指向头结点
	Thrt->rchild = Thrt;
	if (!T) Thrt->lchild = Thrt;
	else {
		Thrt->lchild = T; pre = Thrt;
		InThreading(T);
		pre->rchild = Thrt; pre->RTag = 1;
		Thrt->rchild = pre;
	}
	return 1;
}

int ThreadBiTree::InOrderTraverse_Thr(BiThrTree T) {
	BiThrNode *p;
	p = T->lchild;
	while (p != T) {
		while (p->LTag == 0) p = p->lchild;
		cout << p->data << " ";
		while (p->RTag == 1 && p->rchild != T) {
			p = p->rchild;
			cout << p->data << " ";
		}
		p = p->rchild;
	}
	return 1;
}

void ThreadBiTree::PostThreading(BiThrTree p) {
	if (p) {
		PostThreading(p->lchild);
		PostThreading(p->rchild);
		if (!p->lchild) p->LTag = 1, p->lchild = pre;
		if (pre && !pre->rchild) pre->RTag = 1, pre->rchild = p;
		pre = p;
	}
}

int ThreadBiTree::PostOrderTraverse_Thr(BiThrTree T) {
	if (T) {
		BiThrTree p = T;
		pre = NULL;
		while (pre != T) {
			while (p->LTag == 0) p = p->lchild;
			while (p&&p->RTag == 1) {
				cout << p->data << " ";
				pre = p;
				p = p->rchild;
			}
			while (pre != T && p->rchild == pre) {
				cout << p->data << " ";
				pre = p;
				if (pre != T)p = p->parent;
			}
			if (p->RTag == 0)p = p->rchild;
		}
	}
	return 1;
}

int main() {
	ThreadBiTree TA;
	TA.CreateBiTree(0);
	TA.BiTreeDisplay(TA.Getroot(), 0);
	TA.PreOrderThreading(TA.Thrt, TA.Getroot());
	cout << "先序遍历先序线索二叉树：";
	TA.PreOrderTraverse_Thr(TA.Thrt);
	cout << endl;
	ThreadBiTree TB;
	TB.CreateBiTree(0);
	TB.BiTreeDisplay(TB.Getroot(), 0);
	TB.InOrderThreading(TB.Thrt, TB.Getroot());
	cout << "中序遍历中序线索二叉树：";
	TB.InOrderTraverse_Thr(TB.Thrt);
	cout << endl;
	ThreadBiTree TC;
	TC.CreateBiTree(0);
	TC.BiTreeDisplay(TC.Getroot(), 0);
	TC.PostThreading(TC.Getroot());
	cout << "后序遍历后序线索二叉树：";
	TC.PostOrderTraverse_Thr(TC.Getroot());
	cout << endl;
	return 0;
}

发表于 | 更新于: | 分类于 ， |
字数统计: 1.3k | 阅读时长 ≈ 7

图的邻接矩阵存储结构的定义、实现、输出、遍历。(未完待续)..

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
#include <iostream>
#include <string>
#include <cstring>
using namespace std;

#define MAX_VERTEX_NUM 20 //最大顶点数
const int infinity = INT_MAX;//无穷大

struct ArcCell{
	int adj;//对无权图用1,0表示是否相邻，对带权图为权值类型
	char *info;//该弧的相关信息
};

struct MGraph {
	string vexs[MAX_VERTEX_NUM];//顶点表
	ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵，即边表
	int vexnum;//顶点数
	int arcnum;//边数
	int kind;//邻接矩阵存储的图的种类
};

class Graph {
	//图的数组存储表示
private:
	MGraph mgraph;
	bool visited[MAX_VERTEX_NUM] = { 0 };
public:
	int LocateVex(string u);//图存在，图中存在顶点u则返回顶点在图中的位置
	bool CreateDG();//构造有向图
	bool CreateUDG();//构造无向图
	bool CreateDN();//构造有向网
	bool CreateUDN();//构造无向网
	void DisPlay();//输出邻接矩阵
	void DFSTraverse(int v);//深度优先遍历
	void BFSTraverse(int v);//广度优先遍历
	void clearVis();//清空访问数组
};

int Graph::LocateVex(string u) {
	for (int i = 0; i < MAX_VERTEX_NUM; i++) {
		if (u == mgraph.vexs[i]) return i;
	}
	return -1;
}
//构造有向图
bool Graph::CreateDG() {
	int i, j;
	string v1, v2;
	cout << "请输入有向图的顶点个数，边的个数：";
	cin >> mgraph.vexnum >> mgraph.arcnum;
	cout << "请输入各个顶点：";
	for (i = 0; i < mgraph.vexnum; i++) cin >> mgraph.vexs[i];//构造顶点向量
	for (i = 0; i < mgraph.vexnum; i++) {
		for (j = 0; j < mgraph.vexnum; j++) {
			mgraph.arcs[i][j].adj = 0;
			mgraph.arcs[i][j].info = false;
		}
	}
	for (i = 0; i < mgraph.arcnum; i++) {//构造邻接矩阵
		cout << "请输入一条边的起点与终点：";
		cin >> v1 >> v2;
		int m = LocateVex(v1);
		int n = LocateVex(v2);
		mgraph.arcs[m][n].adj = 1;
	}
	mgraph.kind = 1;
	return true;
}
//构造无向图
bool Graph::CreateUDG() {
	int i, j;
	string v1, v2;
	cout << "请输入无向图的顶点个数，边的个数：";
	cin >> mgraph.vexnum >> mgraph.arcnum;
	cout << "请输入各个顶点：";
	for (i = 0; i < mgraph.vexnum; i++) cin >> mgraph.vexs[i];//构造顶点向量
	for (i = 0; i < mgraph.vexnum; i++) {
		for (j = 0; j < mgraph.vexnum; j++) {
			mgraph.arcs[i][j].adj = 0;
			mgraph.arcs[i][j].info = false;
		}
	}
	for (i = 0; i < mgraph.arcnum; i++) {//构造邻接矩阵
		cout << "请输入一条边依附的两个顶点：";
		cin >> v1 >> v2;
		int m = LocateVex(v1);
		int n = LocateVex(v2);
		mgraph.arcs[m][n].adj = 1;
		mgraph.arcs[n][m].adj = 1;
	}
	mgraph.kind = 2;
	return true;
}
//构造有向网
bool Graph::CreateDN() {
	int i, j;
	string v1, v2;
	cout << "请输入有向网的顶点个数，边的个数：";
	cin >> mgraph.vexnum >> mgraph.arcnum;
	cout << "请输入各个顶点：";
	for (i = 0; i < mgraph.vexnum; i++) cin >> mgraph.vexs[i];//构造顶点向量
	for (i = 0; i < mgraph.vexnum; i++) {
		for (j = 0; j < mgraph.vexnum; j++) {
			mgraph.arcs[i][j].adj = 0;
			mgraph.arcs[i][j].info = false;
		}
	}
	for (i = 0; i < mgraph.arcnum; i++) {//构造邻接矩阵
		cout << "请输入一条边的起点与终点：";
		cin >> v1 >> v2;
		int m = LocateVex(v1);
		int n = LocateVex(v2);
		cout << "请输入该边的权值：";
		cin >> mgraph.arcs[m][n].adj;
	}
	mgraph.kind = 3;
	return true;
}
//构造无向网
bool Graph::CreateUDN() {
	int i, j;
	string v1, v2;
	cout << "请输入无向网的顶点个数，边的个数：";
	cin >> mgraph.vexnum >> mgraph.arcnum;
	cout << "请输入各个顶点：";
	for (i = 0; i < mgraph.vexnum; i++) cin >> mgraph.vexs[i];//构造顶点向量
	for (i = 0; i < mgraph.vexnum; i++) {
		for (j = 0; j < mgraph.vexnum; j++) {
			mgraph.arcs[i][j].adj = 0;
			mgraph.arcs[i][j].info = false;
		}
	}
	for (i = 0; i < mgraph.arcnum; i++) {//构造邻接矩阵
		cout << "请输入一条边依附的两个顶点：";
		cin >> v1 >> v2;
		int m = LocateVex(v1);
		int n = LocateVex(v2);
		cout << "请输入该边的权值：";
		cin >> mgraph.arcs[m][n].adj;
		mgraph.arcs[n][m].adj = mgraph.arcs[m][n].adj;
	}
	mgraph.kind = 4;
	return true;
}
//输出邻接矩阵
void Graph::DisPlay() {
	cout << "图的邻接矩阵为：" << endl;
	for (int i = 0; i < mgraph.vexnum; i++) {
		for (int j = 0; j < mgraph.vexnum; j++) {
			cout << mgraph.arcs[i][j].adj << " ";
		}
		cout << endl;
	}
}

void Graph::DFSTraverse(int v) {
	cout << mgraph.vexs[v] << " ";
	visited[v] = 1;
	for (int j = 0; j < mgraph.vexnum; j++) {
		if (mgraph.arcs[v][j].adj != 0 && visited[j] == 0) DFSTraverse(j);
	}
}

void Graph::BFSTraverse(int v) {
	int front = -1, rear = -1;//初始化队列，假设队列采用顺序存储且不会发生溢出
	int Q[MAX_VERTEX_NUM];
	cout << mgraph.vexs[v] << " ";
	visited[v] = 1;
	Q[++rear] = v;//被访问顶点入队
	while (front != rear) {
		v = Q[++front];//将队头元素出队并送到v中
		for (int j = 0; j < mgraph.vexnum; j++) {
			if (mgraph.arcs[v][j].adj != 0 && visited[j] == 0) {
				cout << mgraph.vexs[j] << " ";
				visited[j] = 1;
				Q[++rear] = j;
			}
		}
	}
}

void Graph::clearVis() {
	memset(visited, 0, sizeof(visited));
}

int main() {
	Graph GA;//有向图
	GA.CreateDG();
	GA.DisPlay();
	cout << "DFS:";
	GA.DFSTraverse(0);
	GA.clearVis();
	cout << endl << "BFS:";
	GA.BFSTraverse(0);
	cout << endl;

	Graph GB;//无向图
	GB.CreateUDG();
	GB.DisPlay();
	cout << "DFS:";
	GB.DFSTraverse(0);
	GB.clearVis();
	cout << endl << "BFS:";
	GB.BFSTraverse(0);
	cout << endl;

	Graph GC;//有向网
	GC.CreateDN();
	GC.DisPlay();
	cout << "DFS:";
	GC.DFSTraverse(0);
	GC.clearVis();
	cout << endl << "BFS:";
	GC.BFSTraverse(0);
	cout << endl;

	Graph GD;//无向网
	GD.CreateUDN();
	GD.DisPlay();
	cout << "DFS:";
	GD.DFSTraverse(0);
	GD.clearVis();
	cout << endl << "BFS:";
	GD.BFSTraverse(0);
	cout << endl;
	return 0;
}