关系模型是1970年由E.F.Codd提出的，用以表示实体和实体间联系的数据模型。关系就是包含行与列表，会随时间变化而变化，一个若干个表可组成关系数据库；而关系模型是符合一定条件的相对固定的关系模式。关系模型由关系数据结构、关系操作集合和完整的关系数据组成。关系模型中的关系是建立在严格的理论基础上的，并且概念简单，数据结构单一，用户易于理解和操作。
关系模型常见用途
关系模型是数据库管理的专业名词，它表示一种抽象的固定的抽象关系模式，是SQL语言的基础，便于创建、操纵和查询关系数据库，提高数据库管理效率。还可以表示实体和实体间联系，所以在生产及商业管理等也有所应用。比如商品关系模型等等。一张清晰简洁关系模型可促使商业活动管理规范化进行，减少工作失误，提高效率。
关系模型绘制方法
以下几步操作简单地呈现了关系模型的绘制方法。
第一步：打开“亿图图示"软件，点击“新建”。
第二步：点击搜索框，输入“关系模型”，开始搜索。
第三步：在下方模板中，任选一个关系模型模板，点击“使用”进入编辑。
第四步：双击替换文本，在素材库中拖动需要的形状，增加或替换元素。最后调节字体、主题等。
第五步：绘制完成后，点击“导出&发送”可将关系模型存储为多种图片格式，还可以选择导出为PS、office等格式。还可以进行下载、打印、分享。
关系模型绘制软件——亿图图示
亿图图示是一款适用于市场分析，商务办公，战略规划，人力资源，数据和工程管理的办公绘图软件，内含绘图类型260多种，丰富的模板素材可以帮助数据管理人士轻松快速绘制关系模型、甘特图、商务图表、流程图、组织结构图等图形，有效提高工作效率。亿图图示PC客户端支持windowsmaclinux系统平台，亿图在线版免安装，能够直接登录作图。多场景使用，实现无障碍绘图。
为什么选择亿图图示绘制关系模型？
1、操作便捷
拖拽式操作，自动对齐，模板直接套用编辑。使用顺畅。2、兼容多个版本，跨平台无障碍绘图
亿图图示支持Mac、Linux和Windows三种系统，云存档功能可随时找回绘图进度。还可以免安装使用，进行在线绘图，小巧方便。3、模板丰富
绘图类型超过260种，广泛覆盖多个领域。模板和矢量符号超过26000种，可随心选用。4、多格式导入
可批量转化Visio文件到Edraw文件。支持 一键导入Visio，SVG格式文件。5、关系呈现清晰
让复杂的数据和关系简单化呈现。可使用超链接，添加注解和附件功能，图表呈现更加立体。6、兼容性强，支持多种格式导出
绘制好的关系模型图表可以一键转化为PDF、PNG、Word、Excel、PowerPoint、等格式，并支持Visio格式的批量导入和导出。

什么是图

 表示“多对多”的关系
 包含

一组顶点：通常用V (Vertex) 表示顶点集合
一组边：通常用E (Edge) 表示边的集合

边是顶点对：$(v, w) \in\mathbb E$，其中$v, w \in\mathbb V$
有向边< v, w> 表示从v指向w的边（单行线）
不考虑重边和自回路







抽象数据类型定义

 类型名：图（Graph）
 数据对象集：G(V,E)由一个非空的有限顶点集合V和一个有限边集合E组成（顶点不为空，边可以为空）。
 操作集：对于任意图$G\in\mathbb Graph$，以及$v\in\mathbb V$, $e\in\mathbb E$

Graph Create()：建立并返回空图；
Graph InsertVertex(Graph G, Vertex v)：将v插入G；
Graph InsertEdge(Graph G, Edge e)：将e插入G；
void DFS(Graph G, Vertex v)：从顶点v出发深度优先遍历图G；
void BFS(Graph G, Vertex v)：从顶点v出发宽度优先遍历图G；
void ShortestPath(Graph G, Vertex v, int Dist[])：计算图G中顶点v到任意其他顶点的最短距离；
void MST(Graph G)：计算图G的最小生成树；



常用术语
网络：就是边上有权值的图

怎么在程序中表示一个图
1、邻接矩阵

问题：对于无向图的存储，怎样可以省一半空间？

用一个长度为N(N+1)/2的1维数组A存储{G00,G10,G11,……,G(n-1)0,…,G(n-1)(n-1)}，

则Gij在A中对应的下标是：
( i*(i+1)/2 + j )
对于网络，只要把G[i][j]的值定义为边

<vi,vj>的权重即可。
邻接矩阵优点

 直观、简单、好理解
 方便检查任意一对顶点间是否存在边
 方便找任一顶点的所有“邻接点”（有边直接相连的顶点）
 方便计算任一顶点的“度”（从该点发出的边数为“出度”，指向该点的边数为“入度”）

无向图：对应行（或列）非0元素的个数
有向图：对应行非0元素的个数是“出度”；对应列非0元素的个数是“入度”



邻接矩阵缺点

 浪费空间—— 存稀疏图（点很多而边很少）有大量无效元素

对稠密图（特别是完全图）还是很合算的


 浪费时间—— 统计稀疏图中一共有多少条边

2、邻接表

邻接表优缺点

 方便找任一顶点的所有“邻接点”
 节约稀疏图的空间

需要N个头指针+ 2E个结点（每个结点至少2个域）


 方便计算任一顶点的“度”？

对无向图：是的
对有向图：只能计算“出度”；需要构造“逆邻接表”（存指向自己的边）来方便计算“入度”


 不能检查任意一对顶点间是否存在边

下面主要介绍一下UML类图怎么画

一.注释

注释就是对类图的补充说明，通过虚线连接被注释的元素。

二.类

类使用包含类名、属性(field) 和方法(method) 且带有分割线的矩形来表示。



三.接口

在UML中，接口有两种表示方式：

1.普通接口表示法（飞翔）。

2.棒棒糖表示法（讲人话），使用一个带有名称的小圆圈来表示，在旁边写上相应接口名称，没有具体接口方法。





四.类与类之间的关系

1.依赖关系

如果A类用到了B类 ,则A依赖于B, 没有B，A编译也不通过。



2.关联关系

实际上就是类与类之间的联系，是依赖关系的特例。



3.继承关系

也称泛化关系，是依赖关系的特例。 A类继承了B类也相当于A类用到了B类。



4.实现关系

实际上就是A类实现B接口，是依赖关系的特例，依赖关系更强。



5.聚合关系

6.组合关系

关系是可以分开的，则是聚合关系;

关系是不可以分开的，则是组合关系。



综合如下图所示：

依赖：虚线箭头

关联：实线箭头

继承：空心三角形+实线

实现：空心三角形+虚线

聚合：空心菱形+实线

组合：实心菱形+实线

什么是图？
1.表示一种多对多的关系

数据对象集：G(V,E)由一个非空的有限顶点集合V和一个有限边集合E组成；

包含

1.一组顶点：通常用V（vertex）表示顶点集合;

2.一组边：通常用E（Edge）表示边的集合；
常见术语






怎么在程序中表示一个图
1.邻接矩阵（只有稠密才划算）
*优点：*

1.直观、简单、好理解 

2.方便检查任意一对顶点间是否存在边 

3.方便找任一顶点的所有“邻接点”（有边直接相连的顶点） 

4.方便计算任一顶点的“度”（从该点发出的边数为“出 度”，指向该点的边数为“入度”）

无向图与有向图的度的计算方法 

**无向图：**对应行（或列）非0元素的个数 ；

**有向图：**对应行非0元素的个数是“出度”；对应列非0元素的 个数是“入度；

缺点：

1.浪费空间——存稀疏图（点很多而边很少）有大量无效元素

2.对稠密图（特别是完全图）还是很合算的 浪费时间——统计稀疏图中一共有多少条边

用领接矩阵表示图

顶点信息：有n个顶点的图G(V, E) 用一维数组D [ n ] 表示

边的信息：用邻接矩阵A [ n ] [ n ] 表示为:



用上图的用玲接矩阵表示为

对于无向图的存储，怎样可以省一半空间


用一个长度为N(N+1)/2的1维数组A存储 {G00,G10,G11,……,Gn-1 0,…,Gn-1 n-1}， 则Gij在A中对应的下标是： ( i(i+1)/2 + j );

对于网络，只要把G[i][j]的值定义为边 <vi,vj>的权重即可.
2.邻接表（只有稀疏才划算）
定义：G[N]为指针数组，对应矩阵每行一个链表， 只存非0元素；
优点

1.方便找任一顶点的所有“邻接点”

2.节约稀疏图的空间 需要N个头指针+ 2E个结点（每个结点至少2个域）

3.方便计算任一顶点的“度”？

4.对无向图：是的

5.对有向图：只能计算“出度”；需要构造“逆邻接表”（存指向自己 的边）来方便计算“入度
图的遍历
DFS在空间上占优势，但往往耗时，BFS在时间上占优势，但浪费空间。

1.深度优先搜索（DFS）

原路返回（堆栈）

时间复杂度

用邻接表存储图：有O（N+E）

用邻接矩阵存储图，有O（N2）；

DFS例题

邻接矩阵存储图的深度优先遍历
void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) )
{
    Vertex i;
    Visited[V] = 1;
    Visit(V);
    for(i = 0; i < Graph->Nv ; i++)
    {
        if(Graph->G[V][i] ==1&&!Visited[i])
        {
            DFS(Graph, i, Visit);
        }
    }
    return;
}

2.广度优先搜索（BFS）

相当于树的层序遍历

时间复杂度

用邻接表存储图：有O（N+E）

用邻接矩阵存储图，有O（N2）；
BFS例题
void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) ) {
    int q[MaxVertexNum],head = 0,tail = 0;
    q[tail ++] = S;
    Visited[S] = true;
    while(head < tail) {
        int temp = q[head ++];
        Visit(temp);
        Visited[temp] = true;
        PtrToAdjVNode k = (Graph -> G[temp]).FirstEdge;
        while(k) {
            int d = k -> AdjV;
            if(!Visited[d]) {
                Visited[d] = true;
                q[tail ++] = d;
            }
            k = k -> Next;
        }
    }
}
图不连通怎么办？

连通：如果从V到W存在一条（无向）路径，则称 V和W是连通的 

路径：V到W的路径是一系列顶点{V, v1, v2, …, vn, W}的集合，其中任一对相邻的顶点间都有图 中的边。路径的长度是路径中的边数（如果带 权，则是所有边的权重和）。如果V到W之间的所 有顶点都不同，则称简单路径 

回路：起点等于终点的路径 

连通图：图中任意两顶点均连通

连通分量：无向图的极大连通子图 

极大顶点数：再加1个顶点就不连通了 

极大边数：包含子图中所有顶点相连的所有边

强连通：有向图中顶点V和W之间存在双向路 径，则称V和W是强连通的 

强连通图：有向图中任意两顶点均强连通 

强连通分量：有向图的极大强连通子图
应用实例
拯救

深度优先（DFS）
//visited[]标记是否走过了
voidListComponents( Graph G )
{
    for( each V in G )
        if( !visited[V] )
        {
            DFS( V );
        }
}
intDFS ( Vertex V )
{
    visited[V] = true;
    if( IsSafe(V) )//判断是否可以上岸，可以就直接结束
        answer = YES;
    else
    {
        for( each V in G )
            if( !visited[W]&&Jump(v，w))Jump(v,w)//是否在跳的范围内
            {
                answer = DFS(W);
                if(answer==YES)
                    break;
            }
    }
    return answer;
}
应用例题

六度空间
“六度空间”理论虽然得到广泛的认同，并且正在得到越来越多的应用。但是数十年来，试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因，这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具，能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。假如给你一个社交网络图，请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。输入格式:输入第1行给出两个正整数，分别表示社交网络图的结点数N（1<N≤10​3​​，表示人数）、边数M（≤33×N，表示社交关系数）。随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个结点的编号（节点从1到N编号）。输出格式:对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比，精确到小数点后2位。每个结节点输出一行，格式为“结点编号:（空格）百分比%”。输入样例:10 9

1 2

2 3

3 4

4 5

5 6

6 7

7 8

8 9

9 10
输出样例:1: 70.00%

2: 80.00%

3: 90.00%

4: 100.00%

5: 100.00%

6: 100.00%

7: 100.00%

8: 90.00%

9: 80.00%

10: 70.00%
分析

对每个节点，进行广度优先搜索

搜索过程中累计访问的节点数

需要记录“层”数，仅计算 6层以内的节点数

BFS代码区
void BFS(int P)
{
    struct ints
    {
        int sp, cnt;
    };
    queue<ints> Q;
    Q.push({P, 0});
    book[P] = true;
    int pass{1};
    while (!Q.empty())
    {
        ints top = Q.front();
        if (top.cnt == 6)
        break;
        for (int i = 1; i <= N; ++i)
        {
            if (mat[top.sp][i] && !book[i])
            {
                pass++;
                Q.push({i, top.cnt + 1});
                book[i] = true;
            }
        }
        Q.pop();
    }
    printf("%d: %.2lf%%\n", P, (static_cast<double>(pass) / N) * 100);
}