最近看离散数学图的部分根据自己的理解，整理了一下笔记
图的基本概念
这里所说的图是一种抽象的数学概念，并不是图片图像什么的，类似质点的概念，只不过可以用图行化表示出来。比如有四个城市{A，B，C，D}，我们想要描述他们之间的公路连通关系，我们画四个点，称为顶点（图中的顶点数>0），表示这四个城市
Fig1

这也算一个图了，但是顶点之间没有关系，这个关系称为边，这样的图被称为零图，对于没有边的任何一个顶点都是孤立顶点，上面就有A，B，C，D四个孤立顶点。
然后在相互之间连线表示互相连通，有以下的图，其中(A，B)互相连通，(A,D)不连通，其他同理
Fig2


上面说的是简单图，简单图指的是没有环和平行边的图，如果有平行边（即两个顶点之间有多条边，则他们是平行的），则这个图是多重图
Fig3

如果有环会出现以下情况（即一个顶点到自身有一条边，这条边就是环），下面的顶点B就有一个环，但这个属于多重图和简单图
FIg4

实际研究学习的时候，还接触到HyperGraph，读者可以自行到维基了解。
图的同构
由于图是一种抽象关系的描述工具，实际上，我们如果把简单图中的A，B，C，D，换成E，F，G，H（如下图所示），他们表示的图也是相同的
Fig5


而在实际作图的过程中，每个城市可能会根据数量关系（之后介绍，即关于集合的部分）有不同的方式去画同一幅图，我们并不关心怎么画这图，而关注的是他们之间的关系，这样的图也是相同的。我们称这样两个相同的图是同构的。如下图所示，
Fig6


Fig7


子图
如果我们在某些场景下只需要表示，一个图部分顶点和部分边，就产生了子图的概念，最开始的图称为母图（也有称为始图的），而子图是保留母图中的部分顶点和部分边的结果（不能产生新的边），即顶点集合是母图的非空子集，边集合也是母图的子集。依旧拿上面的简单图A，B，C，D来说，以下都是它的子图，（当然还有很多）
去掉顶点的子图（顺带去掉了相应边）
Fig8


只去掉边的子图
Fig9

说到子图，不得不说一下子图相关概念，其中就有支撑子图，支撑子图指的是母图中所有的顶点都在子图中，但是母图中边可以不用都在子图里面，毕竟还是子集嘛，比如只去掉边的子图Fig9也是支撑子图，显然下面的图也是，（当然还是不止这些）
Fig10

其次还要说一下，诱导子图，诱导子图其实还是比较简单的，就是有一个子图，如果它包含了母图中的某些点，那么它必须包含这些点在母图中对应的边（如果之前顶点之间没有边就不管），所以上面只去掉边的子图Fig9的例子就不是诱导子图了，去掉顶点的子图Fig8的例子恰好是一个诱导子图，下面再举一个例子，没有顶点C的诱导子图

Fig11


补图
如果母图去掉子图包含所有的边剩下的图（节点数与母图相同），称为相对补图
子图
Fig12


该子图关于母图Fig2的相对补图
Fig13

下面介绍一下完全图，完全图，简而言之，就是给定一个顶点集合，任意两个顶点之间都有边，比如对于ABCD来，他的完全图是这样的，对于更多顶点就会更加麻烦了。
Fig14

而实际上任意一个图都有补图，这个补图，是相对于它的完全图（严谨的说应该是它点集的完全图）的相对补图，
对于最开始的简单图ABCD来说它的补图其实就是这样的
Fig15

当然对于它的子图Fig12的补图，注意这里不是关于母图的相对补图了，是子图本身的补图，别弄混淆了，就
Fig16

权图
当我们要表示，城市间的距离的时候，我们可以再对应的边上加上一个实数，称为权值，用$\omega$表示。比如我们再简单图ABCD加上路径长度时，就可以表示成这样，显然 $\omega(AB)=3$，$\omega(AC)=4$
Fig17

但是如果两个顶点之间没有边的存在，我们就认为他们之间的权值（距离）为无穷大，比如$\omega(AD)=\infty$，有时候，我们可能用到顶点到自己的权值，所以我们规定$\omega(AA)=0$
路
路实际上是两个顶点之间的路径，用顶点序列来表示(实际上我觉得用边序列来表示也可以)，比如Fig17中的AD之间的路就表示为(A,C,D),实际上我们并没有规定每个顶点只走一次，所以(A,B,A,C,D)也算AD之间的路。下图是路(A,C,D)
FIg18

要是只走一次呢，就称为简单路（但是端点可以相同,所以(A,B,A)也算简单路），所以(A,C,D)是简单路，(A,B,A,C,D)不是简单路.
注意路中的顶点序列是相邻的，相邻即，在序列中，连续的两个顶点需作为同一条边的端点，比如顶点A和C相邻，A和D不相邻
最短路径
两个端点之间可能有多条路，比如下图AC之间有(A,C),(A,B,C),(A,D,C)等路径，其中路径上的边权值和最小的称为最短路径，经计算，AC之间最短路径是也刚好是(A,B,C)（有时候可能绕个弯却会更短），且路径长度为7，我们称这个AC最短路径长度为AC之间的距离，记为 $d(A,C)=7$
Fig19


Dijkstra算法
我们再上面使用的计算最短路径的方法是枚举法，就是简单地举出所有路径，并计算长度，当图的规模变大了，比如包含几百个顶点，几万条边，这个方法就不靠谱了。下面介绍Dijkstra算法。
首先我们在最短路径那里定义了点之间的距离，下面引入点与点集合之间的距离，如下图所示，当整个图的点集$G$为$\{A,B,C,D\}$时，比如有一个点集合$S=\{B,D\}$，一个点为$A$，我们定义$A$到$S$的距离,为$A$到$S$中的每一点$v$的距离最小值，记作$d(A,S)=\min\limits_{v\in S}\{d(A,v)\}$,显然$d(A,S)=\min\{d(A,B),d(A,D)\}$
Fig20


我们可以在$S'=G-S$中找到一点$u$(可以是$A$本身), 使得$d(A,S)=\min\limits_{v\in S}\{d(A,v)\}=\min\limits_{v\in S\\u\in S'}\{d(A,u)+\omega(u,v)\}$
所以可以有如下组合
当$u=A$时,$d(A,A)=0$,$\omega(A,B)=4$,$\omega(A,D)=7$,所以
$\min\limits_{u\in S'}\{d(A,u)+\omega(u,v)\}=\min\{d(A,A)+\omega(A,B),d(A,A)+\omega(A,D)\}=\min\{0+4,0+7\}=4$
当$u=C$时,$d(A,C)=8$,$\omega(C,B)=3$,$\omega(C,D)=\infty$（这里不是距离,而是边的权值)，有
$\min\limits_{u\in S'}\{d(A,u)+\omega(u,v)\}=\min\{d(A,C)+\omega(C,B),d(A,C)+\omega(C,D)\}=\min\{8+3,8+\infty\}=11$
综上所述
$d(A,S)=\min\limits_{v\in S\\u\in S'}\{d(A,u)+\omega(u,v)\}=4$
其实从这里就可以看到Dijkstra的影子了，下面给出简单版本算法
目标：求给定点$u_0$到图中各点的最短距离（亦称单源最短路径）

1.初始化$S'=\{u_0\}$，给定点集$S=P-S'$,对于$S$中的每一点$v$,令$d(u_0,v)=d(u_0,u_0)+\omega(u_0,v)$(显然这里的$u=u_0$)
2.找出$u_0$到$S$的最短距离，并确定该点$u_i$，即在S中找出一点$u_i$使得$d(u_0,u_i)$最小，用公式表示为
​													$d(u_0,u_i)=\min\limits_{v\in S}\{d(u_0,v)\}$
3.若$S\neq P$,从给定点集S中删除$u_i$,并将其加入到$S'$中，用公式表示为$S=S-\{u_i\},S'=S'\cup\{u_i\}$
​	否则当$S=P$时，则终止
4.对于新的S中的每一个点$v$,重新计算$d(u_0,v)=\min\limits_{u\in S'}\{d(u_0,u)+\omega(u,v)\}$

其实上面基本能用了，但是还有一些地方可以优化的
其一,对于二维数组$d(u,v)$实际上我们只使用了$d(u_0,v)$,所以可以将它优化成一维数组$d(v)$
再者，第4步，重新计算$d(u_0,v)=\min\limits_{u\in S'}\{d(u_0,u)+\omega(u,v)\}$的时候有很多重复计算，让我们看看那里出来的重复计算？
当$S'=\{u_0,u_1,...u_i\}$时，
$d(u_0,v)\\=\min\limits_{u\in S'}\{d(u_0,u)+\omega(u,v)\}\\=\min\{d(u_0,u_0)+\omega(u_0,v),d(u_0,u_1)+\omega(u_1,v),...,d(u_0,u_i)+\omega(u_i,v)\}$
当$S'=\{u_0,u_1,...u_i,u_{i+1}\}$时，
$d(u_0,v)\\=\min\limits_{u\in S'}\{d(u_0,u)+\omega(u,v)\}\\=\min\{d(u_0,u_0)+\omega(u_0,v),d(u_0,u_1)++\omega(u_1,v)...,d(u_0,u_i)+\omega(u_i,v),d(u_0,u_{i+1})+\omega(u_{i+1},v)\}$
我们可以发现，在计算S’=$\{u_0,u_1,....u_{i+1}\}$最小值的时候，又计算了一遍在$\{u_0,u_1,....u_i\}$中的最小值，其实已经保存了$\{u_0,u_1,....u_i\}$的最小值，就直接和$u_i$对应的值比较就行了。
就优化成这样
$d(u_0,v)\\=\min\limits_{u\in S'}\{d(u_0,u)+\omega(u,v)\}\\=\min\{d(u_0,v),d(u_0,u_{i+1})+\omega(u_{i+1},v)\}$
结合前面两个优化，最后的Dijkstra算法如下

1.初始化$S'=\{u_0\}$，给定点集$S=P-S'$,对于$S$中的每一点$v$,令$d(v)=d(u_0)+\omega(u_0,v)$(显然这里的$u=u_0$)
2.找出$u_0$到$S$的最短距离，并确定该点$u_i$，即在S中找出一点$u_i$使得$d(u_i)$最小，用公式表示为
​													$d(u_i)=\min\limits_{v\in S}\{d(v)\}$
3.若$S\neq P$,从给定点集S中删除$u_i$,并将其加入到$S'$中，用公式表示为$S=S-\{u_i\},S'=S'\cup\{u_i\}$
​	否则当$S=P$时，则终止
4.对于新的S中的每一个点$v$,重新计算$d(v)=\min\limits_{u\in S'}\{d(u)+\omega(u,v)\}$

当然其中$d(u_0)=0$,是可以省略的
关于证明：
证明这条路径时最小的，其实考虑三个方面（路径第一步进入S，路径最后一步进入S，路径中间某步进入S），简单放缩一下，具体参考课本

基本概念
什么是数据？
数据是信息的载体，是客观描述事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。
数据元素、数据项
数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。
一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。
数据结构、数据对象
结构——各个元素之间的关系
数据结构是互相之间存在一个或多种特定关系的数据元素的集合。
数据对象是具有相同性质的数据元素的集合，是一个数据的子集。
三要素

逻辑结构
即，数据元素之间的逻辑关系是什么？

集合

各个数据元素同属一个集合，别无其它关系
线性结构

数据元素之间是一对一的关系，除了第一个元素，所有元素都有唯一前驱，除了最后一个元素，所有元素都有唯一后继
树形结构

数据元素之间是一对多的关系
图结构

数据元素之间是多对多的关系
物理结构
即，物理结构，如何用计算机表示数据元素的逻辑关系？
顺序存储

把逻辑上相邻的元素存储在物理地址上也相邻的存储单元中，元素之间的关系由存储单元的领接关系来体现。
链式存储

索引存储

散列存储

总结


若采用顺序存储，则各个数据元素在物理上必须是连续的；若采用非顺存储，则各个数据元素在物理上是可以离散的
数据的存储结构会影响存储空间的分配的方便程度
数据的存储机构会影响对数据运算的速度

数据的运算
施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，正对运算的功能；运算的实现是针对存储结构的，指的是运算实现的具体操作步骤。
数据类型、抽象数据类型
数据类型
数据类型是一个值的集合和定义在此集合的一组操作的总称。

原子类型，其值不可再分的数据类型
结构类型，其值可以再分解为若干成分（分量）的数据类型


抽象数据类型
Abstract Data Type （ADT）是抽象数据组织及与之相关的操作。
ADT 是用数学化的语言定义数据的逻辑结构、定义运算。与其具体的实现无关（类似于定义类吗？可能）
总结


在探讨一种数据结构时：

定义逻辑结构（数据原元素之间的关系）
定义数据的运算（针对现实需求，应该对这种逻辑结构进行什么样的运算）
确定某种存储结构，实现数据结构，并实现一些对数据结构的基本运算


源码
源码查看地址，点击 传送门 吧～

如果你这个系列的文章有帮助到你的话，不妨给点个赞吧！那将给我莫大的动力！
同系列其他文章目录

[数据结构]第一章绪论(1)——数据结构
[数据结构]第一章绪论(2)——算法
[数据结构]第二章线性表(1)——线性表
[数据结构]第二章线性表(2)——顺序表
[数据结构]第二章线性表(3)——单链表
[数据结构]第二章线性表(4)——双链表
[数据结构]第二章线性表(5)——循环链表
[数据结构]第二章线性表(6)——静态链表
[数据结构]第二章线性表(7)——章节反思

##牛客网假日赛：家族树

题目描述

Farmer John拥有一个传承数代的家族经营的农场，其中的奶牛的根源同样也可以在这个农场中追溯数代。通过检索古老的记录，Farmer John好奇于现在的这群奶牛互相之间是什么关系。请帮帮他！

输入描述:

输入的第一行包含N（1≤N≤100），之后是两头奶牛的名字。每头奶牛的名字都是由至多10个大写字母（A…Z）组成的字符串。Farmer John好奇于这行输入中这两头奶牛之间的关系。

接下来的N行，每行包含两头奶牛的名字X和Y，表示X是Y的母亲。

输出描述:

输出包含一行，表示输入第一行指定的两头奶牛之间的关系（简单起见，在下面的例子中，将这两头奶牛称为BESSIE和ELSIE）。下面是可能出现的不同种类的关系：如果BESSIE和ELSIE的母亲是同一头奶牛，输出“SIBLINGS”。BESSIE可能是ELSIE的直系后代，也就是说ELSIE是BESSIE的母亲（mother），外祖母（grand-mother），外曾外祖母（great-grand-mother），外曾外曾外祖母（great-great-grand-mother），等等。如果是这种情况，输出“ELSIE is the (relation) of BESSIE"，其中(relation)是适当的关系，比如“great-great-grand-mother”。如果ELSIE不是BESSIE的某个祖先或姐妹，但是是BESSIE的某个祖先的孩子，那么ELSIE就是BESSIE的姨母（aunt）。（译者注：英语原题在这里表述有误，供题人已作出声明。）如果ELSIE是BESSIE的外祖母的孩子，输出“ELSIE is the aunt of BESSIE”；如果ELSIE是BESSIE的外曾外祖母的孩子，输出“ELSIE is the great-aunt of BESSIE”；如果ELSIE是BESSIE的外曾外曾外祖母的孩子，输出“ELSIE is the great-great-aunt of BESSIE”；以此类推。如果BESSIE和ELSIE有任何其他的亲戚关系（也就是说，她们有共同的祖先），她们就是表姐妹，输出“COUSINS”。如果BESSIE和ELSIE既没有共同的祖先，其中任何一头也不是另一头的直系后代，输出“NOT RELATED”。

下图描述了上述关系，你只需考虑这些关系。观察到有一些像是“甥女（niece）”（姊妹的女儿）的关系是不必要的，这是由于如果BESSIE是ELSIE的甥女，那么ELSIE就是BESSIE的姨母。

 



输入

7 AA BB
MOTHER AA
GGMOTHER BB
MOTHER SISTER
GMOTHER MOTHER
GMOTHER AUNT
AUNT COUSIN
GGMOTHER GMOTHER

输出

BB is the great-aunt of AA

链接：https://ac.nowcoder.com/acm/contest/997/D

题意：题信息量有些大，但是读个两三遍就懂了，就是求两个人是什么关系，一定要注意grand和great两个单词不同。

题解：建树，dfs跑树，标记升几次、降几次找到该人。

#include <iostream>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
vector<int>up[205];
vector<int>down[205];
map<string,int>maps;
int book[205];
int topx,topy;//升，降
bool dfs(int x,int endx,int numx,int numy)
{
	if(book[x]==0)
	book[x]=1;
	else
	return false;
	if(x==endx)
	{
		topx=numx;
		topy=numy;
		return true;
	}
	for(int i=0;i<up[x].size();i++)
	if(dfs(up[x][i],endx,numx+1,numy))
		return true;
	for(int i=0;i<down[x].size();i++)
	if(dfs(down[x][i],endx,numx,numy+1))
		return true;
	return false;
}
void solve(string aa,string bb,int x,int y)
{
	if(dfs(x,y,0,0))
	{
		if(topx<topy)
		{
			swap(topx,topy);
			swap(aa,bb);
		}
		//	cout<<topx<<" "<<topy<<endl;
		if(topx==1&&topy==1)
		{
			cout<<"SIBLINGS";
		}
		else if(topy==0)//mother
		{
			//BB  AA
			cout<<bb<<" is the ";
			for(int i=0;i<topx-topy-2;i++)
			cout<<"great-";
			if(topx-topy>=2)
			cout<<"grand-";
			cout<<"mother of "<<aa;
		}
		else if(topy==1)//aunt
		{
			cout<<bb<<" is the ";
			for(int i=0;i<topx-topy-1;i++)
			cout<<"great-";
			cout<<"aunt of "<<aa;
		}
		else
		{
			cout<<"COUSINS";
		}
	}
	else
	cout<<"NOT RELATED";
}
int main()
{
	int n,len=0;
	string x,y,z,w;
	cin>>n>>x>>y;
	maps[x]=++len;
	maps[y]=++len;
	for(int i=0;i<n;i++)
	{
		cin>>z>>w;
		if(maps[z]==0)
		maps[z]=++len;
		if(maps[w]==0)
		maps[w]=++len;
		down[maps[z]].push_back(maps[w]);
		up[maps[w]].push_back(maps[z]);
	}
	solve(x,y,maps[x],maps[y]);
	return 0;
}

 

数据库系统(Database System)DBS
由一个互相关联的数据的集合(数据库)和一组用于访问这些数据的程序组成

数据视图
·数据抽象
物理层(physical level)：最底层的抽象，描述数据实际上是怎么存储的
逻辑层(logical level)：稍微高一点的层次，描述存储什么数据以及数据间的关系
视图层(view level)：最高层次的抽象，用于用户与系统的交互
·实例和模式
特定时刻存储在数据库中的信息集合称为数据库的一个实例(instance)
数据库的总体设计称作数据库模式(schema)

数据模型(data model)
是数据库结构的基础
·关系模型(relation model)：用表的集合来表示数据和数据间的联系
·实体联系模型(entity-relationship model)：E-R数据模型
·基于对象的数据模型(object-based data model)
·半结构化数据模型(semistructured data model)

数据库语言
·数据操纵语言(Data-Manipulation Language)DML
·数据定义语言(Data-Definition Language)DDL