Skip to content

Latest commit

 

History

History
511 lines (390 loc) · 25.3 KB

File metadata and controls

511 lines (390 loc) · 25.3 KB

专栏原创出处:github-源笔记文件 github-源码 ,欢迎 Star,转载请附上原文出处链接和本声明。

[toc]

图是由顶点的有穷非空集合和顶点之间边的集合组成。
若用 $G=(V,E)$ 表示一个图:$V$ 表示顶点(数据元素)的有穷非空集合,$E$ 表示两个顶点组成的边的有穷集合。

若顶点 $v$$w$ 之间的边是没有方向的,则称这条边为无向边,用无序偶对 $(v,w)$ 表示。
每条边都是无向边的图称为无向图。

若顶点 $v$$w$ 之间的边是有方向的,则称这条边为有向边,也称为弧,用有序偶对 $<v,w>$ 表示。
每条边都有向边的图称为有向图。

任意有向边 $<v,w>$ 中,无箭头一端的顶点 $v$ 称为弧尾,有箭头的顶点 $v$ 称为弧头。

在无向图中边具有 $(v_i,v_j)$ 关系,则称 $v_i$$v_j$ 互为邻接点。与顶点相关联的边的数目称为顶点的度。 在有向图中边具有 $<v_i,v_j>$ 关系,则称 $v_i$ 邻接到 $v_j$,$v_j$ 邻接于 $v_i$。以顶点为终点的有向边的条数称为入度,以顶点为始点的有向边的条数称为出度,顶点的度等于该顶点的入度和出度之和。

由连续的边构成的顶点序列称为路径;
除路径起点和终点可以相同外,其余顶点均不相同的路径称为简单路径;
路径起点和终点相同的路径称为回路;
除路径起点和终点相同外,其余顶点均不相同的路径称为简单回路;
路径上的边或弧的数目/权值之和称为路径长度。

图的边或弧具有与它相关的数字,这种与图的边或弧相关的数叫做权。权可以表示从一个顶点到另一个顶点的距离或耗费。
边/弧带权的图称为网。

设有两个图,$G = (V,E)$、$G_1 = (V_1,E_1)$,若 $V_1 \subseteq V$,$E_1 \subseteq E$,则称 $G_1$$G$ 的子图。

任意两个点都有一条边相连的无向图称为无向完全图。若无向完全图有 $n$ 个顶点,则具有 ${n(n-1)}\over 2$ 条无向边。
任意顶点都有一条指向其他顶点的出度边和指向该顶点的入度边的有向图称为有向完全图。 若有向完全图有 $n$ 个顶点,则具有 $n(n-1)$ 条有向边。
有很少边或弧的图称为稀疏图;有较多边或弧的图称为稠密图。

若从顶点 $v$$u$ 有路径,则称 $v$$u$ 是连通的。
在无(有)向图 $G=(V,E)$ 中,若对任何两个顶点 $v$、$u$ 都存在从 $v$$u$ 的路径,则称 $G$ 是连通图(强连通图)。

子图 $G_1$$G$ 连通子图,将 $G$ 的任何不在子图中的顶点加入,子图不再连通,此时称该子图为极大(强)连通子图。
该子图是 $G$ 的连通子图,在该子图中删除任何一条边/弧,子图不再连通,此时称该子图为极小连通子图。
无(有)向图 $G$ 的极大连通子图称为 $G$ 的连通分量(强连通分量)。

包含无向图 $G$ 所有顶点的极小连通子图称为生成树。
对非连通图,由各个连通分量的生成树的集合称为生成森林。

图与线性结构、树形结构的比较

线性结构中元素是一对一的关系,每个元素只有一个前驱结点和后继结点; 树形结构中元素是一对多的关系,每个元素只有一个前驱结点和多个后继结点; 图形结构中元素是多对多的关系,任意两个元素之间都可能相关。

图的存储结构

邻接矩阵表示法

建立一个顶点表和一个邻接矩阵来存储图的方式称为邻接矩阵表示法。顶点表记录各个顶点信息;邻接矩阵表示各个顶点之间的关系。

设图 $G=(V,E)$$n$ 个顶点,则顶点表 $Vexs[n]$ 定义为: $$ \begin{array}{c|lcr} i & 0 & 1 & 2 & ... & {n-1} \ \hline Vexs[i] & V_1 & V_2 & ... & V_n \ \end{array} $$

若图 $G$$n$ 个顶点,则邻接矩阵时一个 $n * n$ 的方阵,则方阵任一元素具有如下关系: $$ arcs[i][i]= \begin{cases} 1, &if <i,j> or (i,j) \in E \ 0, &others \end{cases} $$

无向图的邻接矩阵表示法

图的邻接矩阵是一个二维数组 $arcs[n][n]$ 定义为: $$ arcs[i][i]= \begin{cases} 1, &if (i,j) \in E \ 0, &others \end{cases} $$

  • 无向图的邻接矩阵的特点
    • 无向图的邻接矩阵是对称的;
    • 顶点 $i$ 的度 = 第 $i$ 行(列)中 1 的个数;
    • 完全图的邻接矩阵中,对角元素为 0,其余为 1。

有向图的邻接矩阵表示法

  • 怎样定义邻接矩阵?

有向图的邻接矩阵 $arcs[n][n]$ 定义为: $$ arcs[i][i]= \begin{cases} 1, &if <i,j> \in E \ 0, &others \end{cases} $$

有向图的邻接矩阵的特点:

  • 有向图的邻接矩阵可能不对称;
  • $i$ 行含义表示以结点 $i$ 为尾的弧,即出度边;顶点的出度 = 第 $i$ 行元素之和。
  • $i$ 列含义表示以结点 $i$ 为头的弧,即入度边;顶点的入度 = 第 $i$ 列元素之和。
  • 顶点的度 = 第 $i$ 行元素之和 + 第 $i$ 列元素之和。

有权图的邻接矩阵表示法

网的邻接矩阵$arcs[n][n]$定义为: $$ arcs[i][i]= \begin{cases} E_{ij}, &if <i,j> or (i,j) \in E \ \infty , &others \end{cases} $$

邻接矩阵总结

邻接矩阵的构造方法:

  • 输入总顶点数和总边数;
  • 依次输入点的信息存储在顶点表中;
  • 初始化邻接矩阵,初始化每个权限;
  • 构造邻接矩阵,依次输入每条边依附的顶点和其权值:确定两个顶点在图中的位置之后;使相应的边赋予相应的值;同时使其对应的边赋予相同的权值;

邻接矩阵的优点:

  • 直观、简单、好理解;
  • 便于判断任意两个顶点是否存在边;便于查找任意顶点的所有邻接点;便于计算任意顶点的度;
  • 适用于完全图。

邻接矩阵的缺点:

  • 邻接表和邻接矩阵确定后,只能进行修改和查找操作;
  • 不便于增加和删除顶点,若增加或删除顶点,需重新创建邻接矩阵;
  • 稀疏图的存储浪费空间;统计稀疏图共有多少边时浪费时间。

邻接表表示法

数组和链表相结合的存储方式称为邻接表表示法。
按编号顺序将顶点数据存储在一维数组中,用线性链表存储关联同一顶点的边。

一维数组的由指针域和数据域组成: 数据域($data$)存储顶点 $v_i$ 的相关信息,指针域($firstarc$)指向与该顶点相关的链表中的第一个结点。

链表的结点由:邻接点域、链域、数据域组成。
邻接点域($adjvex$)指示与顶点 $v_i$ 连接的点在图中的位置,即顶点在一维数组中的位置;
链域($nextarc$)指示下一条边或弧的结点;
数据域($info$)存储和边或弧相关的信息,如权重;有向图和无向图中通常省略。

无向图的邻接表表示法

无向图的连接表结构如图所示:

无向图的邻接表的特点:

  • 邻接表不唯一,顶点在一维数组中的位置是随意的,每个顶点的邻接链表结点构成也是任意的。
  • 若无向图有 $n$ 个顶点、$e$ 条边,则其邻接表需 $n$ 个头结点和 $2e$ 个表结点。
  • 适合存储稀释图。

有向图的邻接表表示法

因为有向图的顶点对应的边有入度和出度之分,则: - 数组的指针域指向该顶点的出度边组成的弧尾链表,此时称为邻接表表示法。 - 数组的指针域指向该顶点的入度边组成的弧头链表,此时称为逆邻接表表示法。

有向图的邻接表的特点:

  • 顶点 $v_i$ 的出度为第 $i$ 个单链表中的结点个数;
  • 顶点 $v_i$ 的入度为整个单链表中邻接点域值是 $i-1$ 的结点个数;
  • 找出度容易,找入度难。

有向图的逆邻接表的特点:

  • 顶点 $v_i$ 的入度为第 $i$ 个单链表中的结点个数;
  • 顶点 $v_i$ 的出度为整个单链表中邻接点域值是 $i-1$ 的结点个数;
  • 找入度容易,找出度难

有向网的邻接表表示法

有向网的连接表结构如图所示:

邻接表总结

邻接矩阵的构造方法:

  • 输入总顶点数和总边数;
  • 建立顶点表:依次输入点的信息存入顶点表中,使每个表头结点的指针域初始化为 $null$
  • 创建邻接表:依次输入每条边依附的两个顶点;确定两个顶点的序号i和j,建立边结点;将此边结点分别插入到 $v_i$$v_j$ 对应的两个边链表的头部。

邻接表的优点:

  • 便于增加和删除结点,方便找任一顶点的所有邻接点。
  • 方便计算任一顶点的度。按顶点表顺序扫描所有链表可得到顶点的度,时间复杂度为 $O(n+e)$
  • 节约稀疏图的存储空间,仅需要 $n$ 个头指针和 $2e$ 个结点。

邻接表的缺点:

  • 不便于判断顶点之间是否有边,要判断 $v_i$$v_j$ 之间是否有边,就需扫描第 $v_i$ 个顶点的链表。
  • 不便于计算有向图各个顶点的度。

邻接表与邻接矩阵的区别与联系:

  • 邻接表中每个链表对应邻接矩阵的一行,链表中结点个数等于一行中非零元素的个数;
  • 对于任一确定的无向图,邻接矩阵时唯一的,但邻接表不唯一;
  • 邻接矩阵的空间复杂度为 $O(n^2)$,邻接表的空间复杂度为 $n + 2e$
  • 邻接矩阵多用于稠密图,邻接表多用于稀疏图。

十字链表表示法

为了解决有向图的结点求度难,将邻接表和逆邻接表的特点结合起来的存储结构称为十字链表表示法。
按编号顺序将顶点数据存储在一维数组中,用链表存储关联顶点的边。

十字链表法仅适用于存储有向图和有向网

一维数组的由入度指针域、出度指针域、数据域组成:数据域($data$)存储顶点 $v_i$ 的相关信息,入度指针域($firstin$)指向该顶点为弧头的第一个结点,出度指针域($firstout$)指向该顶点为弧尾的第一个结点。

链表的结点由:尾域、头域、弧尾指针域、弧头指针域、数据域组成:
数据域($info$)存储和边或弧相关的信息,如权重;有向图和无向图中通常省略;
尾域($tailvex$)和头域($headvex$)分别指示弧头和弧尾的顶点在图中的位置;
链域($hlink$)指向弧头相同的下一条弧;
链域($tlink$)指向弧尾相同的下一条弧。

  • 有向图的十字链表表示法示意图:

邻接多重表表示法

为了解决无向图每条边都要存储两遍问题,将邻接表和十字链表的特点结合起来的存储方式称为邻接多重表表示法。 按编号顺序将顶点数据存储在一维数组中,用线性链表存储关联同一顶点的边。

邻接多重表仅适用于存储无向图或无向网

一维数组的由指针域和数据域组成:数据域($data$)存储顶点 $v_i$ 的相关信息,指针域($firstedge$)指向第一条依附于该顶点的边。

链表的结点组成结构:
数据域($info$)存储弧的相关信息;
标识域($mark$)标记该条边是否被搜索过;
$ivex$$jvex$ 为该边依附的两个顶点在图中的位置;
$ilink$ 指向下一条依附于顶点 $ivex$ 的边;
$jlink$ 指向下一条依附于顶点 $jvex$ 的边。

无向图的邻接多重表表示法示意图:

图的遍历

从连通图中的某个顶点出发,沿着一些边访遍图中所有的顶点,且使每个顶点仅被访问一次,叫做图的遍历。遍历实质是找每个顶点的邻接点的过程

因为图中可能存在回路,任一顶点都可能与其他顶点相通,避免重复访问已访问过的顶点,需要做如下操作:

  • 设置辅助数组 $visited[n]$ 用来标记每个被访问过的顶点;
  • 初始状态中 $visited[i]=0$
  • 顶点 $i$ 被访问过后 $visited[i]=1$,从而避免被多次访问

深度优先遍历

深度优先搜索DFS遍历类似于树的先序遍历

假设初始状态图中所有顶点都没有被访问,深度优先遍历的遍历过程:

  • 先从图中的某个顶点 $v$ 出发,访问此顶点;
  • 然后依次从 $v$ 的未被访问的邻接点出发深度优先遍历图;
  • 直至图中所有与 $v$ 连通的顶点均被访问;
  • 若此时图中尚有未被访问的顶点,则选一个未被访问的顶点作为起点;
  • 重复上述步骤,直至所有顶点都被访问。

深度优先遍历的代码实现

void DFS(AMGraph G, int v){ // 图G为邻接矩阵类型
    visited[v]=true; // 访问第v个顶点
    for(w=0;w<G.vexnum;w++){// 依次检查邻接矩阵v所在的行
        if(G.arcs[v][w]!=0&& !visited[w]){
            DFS(G,W);
            // w为v的邻接点,如果w未访问,则递归调用DFS
}}}

广度优先遍历

广度优先搜索BFS遍历类似于树的层次遍历

假设初始状态图中所有顶点都没有被访问,广度优先遍历的遍历过程:

  • 先从图中的某个顶点 $v$ 出发,访问此顶点;
  • 依次访问该节点的所有相邻的结点;
  • 再按这些结点被访问的先后次序依次访问与他们相邻所有未被访问的顶点;
  • 重复此过程,直至所有顶点均被访问为止。

图的遍历总结

稠密图适用于在邻接矩阵上进行深度遍历,稀疏图适用于邻接表上进行深度遍历;
图的广度优先遍历和深度优先遍历的空间复杂度相同,均为 $O(n)$(借用了堆栈或队列);
图的遍历时间复杂度只与存储结构(邻接矩阵或邻接表)有关,而与搜索路径无关。

最小生成树

生成树

所有顶点均由边连接在一起,但不存在回路的图称为生成树

一个图可以有多棵不同的生成树,所有的生成树具有以下共同特点:

  • 生成树的顶点个数与图的顶点个数相同;
  • 生成树是图的极小连通子图,去掉一条边则非联通;
  • 一个有 $n$ 个顶点的连通图的生成树有 $n-1$ 条边;
  • 在生成树中再加一条边必然形成回路;
  • 生成树中任意两个顶点间的路径是唯一的。
    $n$ 个顶点 $n-1$ 条边的图不一定是生成树。

最小生成树

给定一个无向网络,在该网的所有生成树中,使得各边权值之和之和最小的那棵生成树称为该网的最小生成树,也称为最小代价生成树。最小生成树可能不唯一。

构造最小生成树

$N=(V,E)$ 是一个连通图:

  • $U$ 是顶点集 $V$ 的一个非空子集;
  • 若边 $(u,v)$ 是一条具有最小权值额边;
  • 其中 $u \subseteq U$ ,$v \subseteq {V-U}$;
  • 则必存在一棵包含边 $(u,v)$ 的最小生成树。

在生成树的构造过程中,图中 $n$ 个顶点分属于两个集合:已落在生成树上的顶点集,尚未落在生成树上的顶点集。

构造最小生成树-prim算法

$prim$ 算法的构造思想
$N=(V,E)$ 是一个连通网

  • $TE$$N$ 上最小的生成树中的边的集合;
  • 初始一个 $TE={}$ 集合;
  • 然后找到一个结点,找到 $TE$、$U-TE$ 集合最小权重的边;
  • 继续前两步,直到构成最小生成树。

构造最小生成树-Kruskal算法

$Kruskal$ 算法的构造思想
$N=(V,E)$ 是一个连通网

  • 令最小生成树初始状态为只有 $n$ 个顶点而无边的连通图 $T=(V,{})$,每个顶点自成一个连通分量;
  • 在设 $E$ 中选取代价最小的边;
    • 若该边依附的顶点落在 $T$ 中不同的连通分量上(不能形成环),则将该边加入到 $T$ 中;
    • 否则舍去该边,选取下一条代价最小的边。
  • 以此类推,直至 $T$ 中所有顶点都在同一个连通分量中为止

构造最小生成树-算法比较

  • $prim$ 算法:选择点,时间复杂度:$O(n^2)$ ( $n$ 为顶点数),适用于稠密图
  • $Kruskal$ 算法:选择边,时间复杂度:$O(eloge)$ ( $e$ 为边数),适用于稀疏图

最短路径问题

在有向网中使A点到B点的多条路径中,寻找一条各边权值之和最小的路径,即为最短路径

两点间最短路径-Dijkstra(迪杰斯特拉)算法

$Dijkstra$ 算法的求解步骤:

  • 找到权值最小的边结点
  • 对于该结点的邻居,检查是否有前往他们最短的路径,如果有记录其距离
  • 重复上述过程,直到图中的每个结点的最短路径都找到
  • 计算最终路径

$Dijkstra$ 算法的求解过程:

每一对顶点之间的最短路径-Floyd(弗洛伊德)算法

$Floyd$ 算法的求解步骤

  • 初始设置一个 $n$ 阶方阵,令其对角线元素为 0。若存在弧 $&lt;v_i,v_j&gt;$,则对应元素为权值,否则为无穷。
  • 逐步在原直接路径中增加中间顶点。如加入中间顶点后路径变短,则修改之,否则维持原值。
  • 所有顶点试探完毕,算法结束。

$Floyd$ 算法的求解过程:

关键路径

路径上各活动持续时间之和称为路径长度。
路径最长的路径为关键路径。

AOE网解决关键路径问题时的4个描述量:

  • $ve(v_j)$:表示事件 $v_j$ 最早发生的时间
  • $vl(v_j)$:表示事件 $v_j$ 最迟发生的时间
  • $e(i)$:表示活动 $a_i$ 最早开始的时间
  • $l(i)$:表示活动 $a_i$ 最迟开始的时间
  • $l(i)-e(i)$:表示完成活动 $a_i$ 的时间余量

AOE网解决关键路径的求解过程:

算法例题

1.二部图的判断
例题:给定一个无向图 graph,当这个图为二部图时返回 true。

提示:如果能将一个图的节点集合分割成两个独立的子集 A 和 B,并使图中的每一条边的两个节点一个来自 A 集合,一个来自 B 集合,就将这个图称为二部图。

解题思路: 判断一个给定的任意图是否为二部图,就必须要对该图进行一次遍历:
深度优先
广度优先
二部图,图的所有顶点可以分成两个子集 U 和 V,子集里的顶点互不直接相连,图里面所有的边,一头连着子集 U 里的顶点,一头连着子集 V 里的顶点。

  1. 给图里的顶点涂上颜色,子集 U 里的顶点都涂上红色,子集 V 里的顶点都涂上蓝色。
  2. 开始遍历这个图的所有顶点,想象一下手里握有红色和蓝色的画笔,每次交替地给遍历当中遇到的顶点涂上颜色。
  3. 如果这个顶点还没有颜色,那就给它涂上颜色,然后换成另外一支画笔。
  4. 下一个顶点,如果发现这个顶点已经涂上了颜色,而且颜色跟我手里画笔的颜色不同,那么表示这个顶点它既能在子集 U 里,也能在子集 V 里。
  5. 所以,它不是一个二部图。

2.单词搜索 例题:给定一个二维网格 board 和一个字典中的单词列表 words,找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

说明:你可以假设所有输入都由小写字母 a-z 组成。

解题思路:
这是一道出现较为频繁的难题,题目给出了一个二维的字符矩阵,然后还给出了一个字典,现在要求在这个字符矩阵中找到出现在字典里的单词。

由于字符矩阵的每个点都能作为一个字符串的开头,所以必须得尝试从矩阵中的所有字符出发,上下左右一步步地走,然后去和字典进行匹配,如果发现那些经过的字符能组成字典里的单词,就把它记录下来。

可以借用深度优先的算法来实现,如果对它不熟悉,可以把它想象成走迷宫。

字典匹配的解法 1:每次都循环遍历字典,看看是否存在字典里面,如果把输入的字典变为哈希集合的话,似乎只需要 O(1) 的时间就能完成匹配。

但是,这样并不能进行前缀的对比,即,必须每次都要进行一次全面的深度优先搜索,或者搜索的长度为字典里最长的字符串长度,这样还是不够高效。

字典匹配的解法 2:对比字符串的前缀,借助前缀树来重新构建字典。

假如在矩阵里遇到了一个字符”V”,而字典里根本就没有以“V”开头的字符串,则不需要将深度优先搜索进行下去,可以大大地提高搜索效率。

构建好了前缀树之后,每次从矩阵里的某个字符出发进行搜索的时候,同步地对前缀树进行对比,如果发现字符一直能被找到,就继续进行下去,一步一步地匹配,直到在前缀树里发现一个完整的字符串,把它输出即可。

参考

  • 《数据结构(C语言版)》 严魏敏、吴伟民著
  • 《数据结构(第3版)》 刘大有等著
  • 《搞定数据结构与算法》 苏勇