数据结构基础总结
<h2>1 数据结构三要素</h2>
<ol>
<li>逻辑结构：线性和非线性</li>
<li>存储结构：顺序，链式，索引，散列</li>
<li>数据运算：算法</li>
</ol>
<p>具体时间复杂度与问题的规模和初始条件相关，分最佳和最大</p>
<h2>2 链表</h2>
<p>链表与数组相比，链表是逻辑上连续的，但物理上是非连续的。</p>
<h3>2.1 单向链表</h3>
<p>单项链表中节点包含数据域和指针域，数据域存储节点的数据，指针域存储下一节点的地址；尾节点的指针域为NULL。</p>
<ul>
<li>无头结点:头指针指向第一个数据节点。
头插法：s->data=ch;s->next=head;head=s;
尾插法：rear->next=s;rear=s; (两个指针头尾指针）
删除：q=p->next;p->next=q->next;free(q);（q是临时节点）</li>
<li>有头结点：在第一个数据节点前面加上一个头节点，头指针指向头节点。有了头结点后，对在第一个元素结点前插入结点和删除第一个结点，其操作与对其它结点的操作统一了。
头插法：s->data=ch;s->next=head->next;head->next=s;
尾插法：rear->next=s;rear=s; (两个指针头尾指针）
删除：q=p->next;p->next=q->next;free(q);</li>
</ul>
<p>注：head和rear表示头指针和尾指针，分别指向头节点（第一个节点）和尾节点，不表示头节点和尾节点；s表示当前要插入的节点；q表示临时指针；p表示要删除节点的前一个节点。</p>
<ul>
<li>
<p>链表逆序</p>
<pre><code>public static Node reversed_linkedlist(Node head) {
//使用三个节指针
Node current = head;//当前节点
Node newHead = null;//当前节点前面一个节点，最后变成新的头节点
Node next = null;//当前节点的下一个节点
while(current != null) {//循环结束条件
//先将当前节点的下个节点保存，以便断链之后能够继续寻找，不会丢失链表
next = current.next;
current.next = newHead; //将原来的链表断链,将current的下一个结点指向新链表的头结点，即将链表反序
newHead = current; //将current设为新表头
current = next; //将之前保存的next设为下一个节点
}
return newHead;
}</code></pre>
<h3>2.2 循环链表</h3>
<p>单向链表的最后一个节点的next指针域指向头节点，而不是指向空。</p>
<h3>2.3 双向循环链表</h3>
<p>双向链表：节点中包含前驱结点、数据域和后继节点（指针域分别指向前驱结点和后继节点）。从任意一个节点开始都可以遍历整个链表。</p>
</li>
<li>前插：s->data=ch;s->prior=p->prior;s->next=p;p->prior->next=s;p->prior=s;</li>
<li>删除：p->prior->next=p->next;p->next->prior=p->prior;free(p);</li>
</ul>
<p>注：s表示要插入的节点；p表示指向当前节点的指针。</p>
<h4>应用场景</h4>
<p>如果要解决的问题里面需要很多快速查询，链表可能并不适合；如果遇到的问题中，数据的元素个数不确定，而且需要经常进行数据的添加和删除，那么链表会比较合适。而如果数据元素大小确定，删除插入的操作并不多，那么数组可能更适合。</p>
<h4>经典解法</h4>
<ul>
<li>利用快慢指针（有时候需要用到3个指针）</li>
</ul>
<p>典型题目例如：链表的翻转，寻找倒数第 k 个元素，寻找链表中间位置的元素，判断链表是否有环等等。</p>
<ul>
<li>构建一个虚假的链表头</li>
</ul>
<p>一般用在要返回新的链表的题目中，比如，给定两个排好序的链表，要求将它们整合在一起并排好序。又比如，将一个链表中的奇数和偶数按照原定的顺序分开后重新组合成一个新的链表，链表的头一半是奇数，后一半是偶数。</p>
<p>在这类问题里，如果不用一个虚假的链表头，那么在创建新链表的第一个元素时，我们都得要判断一下链表的头指针是否为空，也就是要多写一条 if else 语句。比较简洁的写法是创建一个空的链表头，直接往其后面添加元素即可，最后返回这个空的链表头的下一个节点即可。</p>
<h2>3 栈</h2>
<p>一种后进先出的存储数据的数据结构，只能在一端进行入栈和出栈。
顺序栈：栈底位置固定不变，栈顶位置随着入栈和出栈操作而变化。(栈顶插入和删除，栈底为0）</p>
<ul>
<li>初始栈：s->top=-1;</li>
<li>进栈：s->top++;S->data[s->top]=x;</li>
<li>出栈：x=S[s->top];s->top--;</li>
</ul>
<p>链栈：链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针</p>
<ul>
<li>进栈：p->data=x;p->next=S->top;S->top=p;(先进后出）S的next指向前面</li>
<li>出栈：S->top=p->next;free(p);</li>
</ul>
<h3>应用场景</h3>
<p>在解决某个问题的时候，只要求关心最近一次的操作，并且在操作完成了之后，需要向前查找到更前一次的操作。</p>
<h2>4 队列</h2>
<p>一种先进先出的存储数据的数据结构，队头删除，队尾插入（银行排队）</p>
<h3>4.1 顺序队列</h3>
<ul>
<li>front和rear分别指队头指针和队尾指针，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置</li>
</ul>
<h3>4.2 循环队列：为区分队列空和满：1，添加一个空;2,添加计数项</h3>
<ul>
<li>入队：Q->count++;Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%QueueSize;</li>
<li>出队：Q->count--;Q->front=(Q->front+1)%QueueSize;</li>
</ul>
<h3>4.3 链式队列：front指向队头元素，rear指向队尾元素</h3>
<ul>
<li>入队：p->data=x;Q->rear->next=p;Q->rear=p;</li>
<li>出队：p=Q->front;Q->front=p->next;free(p);</li>
</ul>
<p>应用场景：直观来看，当我们需要按照一定的顺序来处理数据，而该数据的数据量在不断地变化的时候，则需要队列来帮助解题。在算法面试题当中，广度优先搜索（Breadth-First Search）是运用队列最多的地方，我们将在第 06 课时中详细介绍。</p>
<h3>4.4 双端队列：双端队列和普通队列最大的不同在于，它允许我们在队列的头尾两端都能在 O(1) 的时间内进行数据的查看、添加和删除。</h3>
<p>实现：与队列相似，我们可以利用一个双链表实现双端队列。</p>
<p>应用场景：双端队列最常用的地方就是实现一个长度动态变化的窗口或者连续区间，而动态窗口这种数据结构在很多题目里都有运用。</p>
<h3>应用场景</h3>
<p>直观来看，当我们需要按照一定的顺序来处理数据，而该数据的数据量在不断地变化的时候，则需要队列来帮助解题。在算法面试题当中，广度优先搜索（Breadth-First Search）是运用队列最多的地方，我们将在第 06 课时中详细介绍。</p>
<h2>5 树</h2>
<h3>5.1 基本术语：</h3>
<ul>
<li>树结点：包含一个数据元素及若干指向子树的分支；</li>
<li>孩子结点：结点的子树的根称为该结点的孩子；</li>
<li>双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；</li>
<li>兄弟结点：同一双亲的孩子结点；</li>
<li>堂兄结点：同一层上结点；</li>
<li>结点层次：根结点的层定义为1；根的孩子为第二层结点，依此类推；</li>
<li>树的高（深）度：树中最大的结点层</li>
<li>结点的度：结点子树的个数</li>
<li>树的度： 树中最大的结点度。</li>
<li>叶子结点：也叫终端结点，是度为0的结点；</li>
<li>分枝结点：度不为0的结点（非终端结点）；</li>
<li>森林：互不相交的树集合；</li>
<li>有序树：子树有序的树，如：家族树；</li>
<li>无序树：不考虑子树的顺序；</li>
</ul>
<h3>5.2 二叉树性质：</h3>
<ul>
<li>二叉树第i层上的结点数目最多为2^(i-1)(i≥1)。</li>
<li>深度为k的二叉树至多有(2^k)-1个结点(k≥1)</li>
<li>对于任意一棵二叉树，设其总结点数为N，如果其叶结点(度为0的结点）数为N0，而度数为2的结点总数为N2，则N0=N2+1，度为1的结点数N1=N-N0-N2</li>
<li>具有n个结点的完全二叉树的深度为：log2[n](向下）+1或log2[n+1](向上）</li>
<li>有N个结点的完全二叉树各结点如果用顺序方式存储,如果所有结点从0开始编号，那么相应的i号节点的双亲节点的编号为（i-1）/2，左孩子的编号为2i+1，右孩子编号为2i+2。</li>
</ul>
<h3>5.3 二叉树存储形式：</h3>
<p> 1，顺序存储：第i个结点的孩子是2i,2i+1 (完全二叉树适用，如果该树不是完全二叉树，需要添加空节点构成完全二叉树）
2，二叉链表结构：左右指针，中间数据 |left|data|right|</p>
<h3>5.4 二叉树遍历：</h3>
<p>对于二叉树，有深度遍历和广度遍历，深度遍历有前序、中序以及后序三种遍历方法，广度遍历即我们寻常所说的层次遍历。（因为前后可以推出根结点，而中可以推左右） 使用递归思想来推树的结构能够快些.</p>
<h4>5.4.1 四种基本的遍历思想为</h4>
<ul>
<li>前序遍历：根结点 ---> 左子树 ---> 右子树</li>
<li>中序遍历：左子树---> 根结点 ---> 右子树</li>
<li>后序遍历：左子树 ---> 右子树 ---> 根结点</li>
<li>层次遍历：仅仅需按层次遍历就可以</li>
</ul>
<h4>5.4.2 通过遍历还原树</h4>
<ul>
<li>前+中
前：GDAFEMHZ 中：ADEFGHMZ
步骤：根据前知道root是G，根据中知道左子树是ADEF,右子树是HMZ
分析leftTree,由前知道root是D，so leftTree is:A,and rightTree is :EF
分析leftTree A ,结束，分析rightTree,From 前知道root 是F，From 中知leftTree is E
分析rigthTree HMZ,From 前知root is M,From 中知 leftTree is H,and rightTree is Z
遍历结束，树的层次遍历为 GDMAFHZE</li>
<li>中+后
中：ADEFGHMZ 后：AEFDHZMG
步骤：From 后，知道root 是G，From中知leftTree is ADEF,rightTree is HMZ;
分析leftTree:From 后知root is D,From 中leftTree is A ,rightTree is EF;
分析rightTree EF;From 后知：root is F,From 中leftTree is E;
分析rightTree HMZ;From 后知root is M ，From 中leftTree is H，rightTree is Z;
遍历结束，层次遍历为：GDMAFHZE</li>
</ul>
<h3>5.5 树存储结构</h3>
<ol>
<li>双亲链表表示法利用树中每个结点的双亲唯一性，在存储结点信息的同时，为每个结点附设一个指向其双亲的指针parent，惟一地表示任何-棵树。</li>
<li>孩子链表表示法是为树中每个结点设置一个孩子链表，并将这些结点及相应的孩子链表的头指针存放在一个向量中。类似hash</li>
<li>在存储结点信息的同时，附加两个分别指向该结点最左孩子和右邻兄弟的指针域leftmostchild和rightsibling，即可得树的孩子兄弟链表表示。</li>
</ol>
<p>这种存储结构的最大优点是：它和二叉树的二叉链表表示完全一样
树（森林）的前序遍历：前序遍历一棵树（森林）恰好等价于前序遍历该树（森林）对应的二叉树
后序遍历树（森林）恰好等价于中序遍历该树（森林）对应的二叉树</p>
<ul>
<li>树的路径：树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。</li>
<li>树的代价：结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积
带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树。</li>
</ul>
<h3>5.6 哈夫曼树</h3>
<ol>
<li>n个叶子的哈夫曼树要经过n-1次合并，产生n-1个新结点。最终求得的哈夫曼树中共有2n-1个结点。</li>
<li>哈夫曼树是严格的二叉树，没有度数为1的分支结点。</li>
</ol>
<h4>5.6.1 基本术语</h4>
<ul>
<li>路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径。</li>
<li>路径长度：在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第 i 层结点的路径长度为 i - 1 。</li>
<li>结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权。</li>
<li>结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。</li>
<li>WPL（带权路径长度）：树的带权路径长度为树中所有叶子结点的带权路径长度之和。</li>
</ul>
<h4>5.6.2 什么是哈夫曼树</h4>
<p>当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”。</p>
<p>在构建哈弗曼树时，要使树的带权路径长度最小，只需要遵循一个原则，那就是：权重越大的结点离树根越近。</p>
<h4>5.6.3 哈夫曼树的构建过程</h4>
<p>对于给定的有各自权值的 n 个结点，构建哈夫曼树有一个行之有效的办法：</p>
<ol>
<li>在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；</li>
<li>在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推；</li>
<li>重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。</li>
</ol>
<h4>5.6.4 哈弗曼树中结点结构</h4>
<p>构建哈夫曼树时，首先需要确定树中结点的构成。由于哈夫曼树的构建是从叶子结点开始，不断地构建新的父结点，直至树根，所以结点中应包含指向父结点的指针。但是在使用哈夫曼树时是从树根开始，根据需求遍历树中的结点，因此每个结点需要有指向其左孩子和右孩子的指针。此外，还应该有每个节点的权重。所以，节点中应该包括：父指针、左右孩子指针、节点权重四个值。</p>
<h4>5.6.5 构建哈弗曼树的算法实现</h4>
<p>构建哈夫曼树时，需要每次根据各个结点的权重值，筛选出其中值最小的两个结点，然后构建二叉树。</p>
<p>查找权重值最小的两个结点的思想是：从树组起始位置开始，首先找到两个无父结点的结点（说明还未使用其构建成树），然后和后续无父结点的结点依次做比较，有两种情况需要考虑：</p>
<ul>
<li>如果比两个结点中较小的那个还小，就保留这个结点，删除原来较大的结点；</li>
<li>如果介于两个结点权重值之间，替换原来较大的结点；</li>
</ul>
<h4>5.6.6 哈夫曼编码算法</h4>
<p>哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。
一个包含100000个字符文件的各字符出现频率表：</p>
<table>
<thead>
<tr>
<th style="text-align: center;">字符</th>
<th style="text-align: center;">频度（单位：千次）</th>
<th style="text-align: center;">定长编码</th>
<th style="text-align: center;">变长编码</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align: center;">a</td>
<td style="text-align: center;">45</td>
<td style="text-align: center;">000</td>
<td style="text-align: center;">0</td>
</tr>
<tr>
<td style="text-align: center;">b</td>
<td style="text-align: center;">13</td>
<td style="text-align: center;">001</td>
<td style="text-align: center;">101</td>
</tr>
<tr>
<td style="text-align: center;">c</td>
<td style="text-align: center;">12</td>
<td style="text-align: center;">010</td>
<td style="text-align: center;">100</td>
</tr>
<tr>
<td style="text-align: center;">d</td>
<td style="text-align: center;">16</td>
<td style="text-align: center;">011</td>
<td style="text-align: center;">111</td>
</tr>
<tr>
<td style="text-align: center;">e</td>
<td style="text-align: center;">9</td>
<td style="text-align: center;">100</td>
<td style="text-align: center;">1101</td>
</tr>
<tr>
<td style="text-align: center;">f</td>
<td style="text-align: center;">5</td>
<td style="text-align: center;">101</td>
<td style="text-align: center;">1100</td>
</tr>
</tbody>
</table>
<p>有多种方式表示文件中的信息，若用0,1码表示字符的方法，即每个字符用唯一的一个0,1串表示。</p>
<ul>
<li>若采用定长编码表示，则需要3位表示一个字符，整个文件编码需要300,000位；</li>
<li>若采用变长编码表示，给频率高的字符较短的编码；频率低的字符较长的编码，达到整体编码减少的目的，则整个文件编码需要（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000位，由此可见，变长码比定长码方案好，总码长减小约25%。</li>
</ul>
<h3>5.7 二叉搜索树</h3>
<p>二叉搜索树是一种节点值之间具有一定数量级次序的二叉树，对于树中每个节点：</p>
<ul>
<li>若其左子树存在，则其左子树中每个节点的值都不大于该节点值；</li>
<li>若其右子树存在，则其右子树中每个节点的值都不小于该节点值。</li>
</ul>
<h3>5.8 堆（优先队列）</h3>
<p>堆就是用数组实现的二叉树，所有它没有使用父指针或者子指针。堆根据“堆属性”来排序，“堆属性”决定了树中节点的位置。</p>
<h4>5.8.1 堆属性</h4>
<p>堆分为两种：最大堆和最小堆，两者的差别在于节点的排序方式。</p>
<p>在最大堆中，父节点的值比每一个子节点的值都要大。在最小堆中，父节点的值比每一个子节点的值都要小。这就是所谓的“堆属性”，并且这个属性对堆中的每一个节点都成立。</p>
<h4>5.8.2 特点</h4>
<p>能保证每次取出的元素都是队列中优先级别最高的。优先级别可以是自定义的，例如，数据的数值越大，优先级越高；或者数据的数值越小，优先级越高。优先级别甚至可以通过各种复杂的计算得到。</p>
<h4>5.8.3 应用场景</h4>
<p>从一堆杂乱无章的数据当中按照一定的顺序（或者优先级）逐步地筛选出部分乃至全部的数据。</p>
<h4>5.8.4 基本操作（向上筛选/向下筛选）</h4>
<h5>向上筛选</h5>
<ol>
<li>当有新的数据加入到优先队列中，新的数据首先被放置在二叉堆的底部。</li>
<li>不断进行向上筛选的操作，即如果发现该数据的优先级别比父节点的优先级别还要高，那么就和父节点的元素相互交换，再接着往上进行比较，直到无法再继续交换为止。</li>
</ol>
<h5>向下筛选</h5>
<ol>
<li>当堆顶的元素被取出时，要更新堆顶的元素来作为下一次按照优先级顺序被取出的对象，需要将堆底部的元素放置到堆顶，然后不断地对它执行向下筛选的操作。</li>
<li>将该元素和它的两个孩子节点对比优先级，如果优先级最高的是其中一个孩子，就将该元素和那个孩子进行交换，然后反复进行下去，直到无法继续交换为止。</li>
</ol>
<h5>初始化</h5>
<p>优先队列的初始化是一个最重要的时间复杂度，是分析运用优先队列性能时必不可少的，也是经常容易弄错的地方。时间复杂度为O(n)。</p>
<h2>6 图</h2>
<p>图G的顶点数n和边数e的关系</p>
<ul>
<li>若G是无向图，则0≤e≤n(n-1)/2</li>
<li>若G是有向图，则0≤e≤n(n-1)</li>
</ul>
<h3>6.1 图的度</h3>
<ul>
<li>无向图的度：无向图中顶点v的度(Degree)是关联于该顶点的边的数目，记为D(v)，不分出度和入度；</li>
<li>有向图的度：入度：以顶点v为终点的边的数目；出度：以顶点v为始点的边的数目；
图的边数等于度之和除以2</li>
</ul>
<h3>6.2 连通图</h3>
<ul>
<li>连通图：若V(G)中任意两个不同的顶点vi和vj都连通，则为连通图。</li>
<li>弧：有向边也称为弧(Arc)，边的始点称为弧尾(Tail)，终点称为弧头(Head)。</li>
<li>强连通图：有向图G中，若对于V(G)中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。</li>
<li>网络：若将图的每条边都赋上一个权，则称这种带权图为网络</li>
<li>连通分量：</li>
</ul>
<h3>6.3 图的存储结构</h3>
<h4>6.3.1 邻接矩阵</h4>
<p>图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（邻接矩阵）存储图中的边或弧的信息。设图G有n个顶点，则邻接矩阵是一个n*n的方阵。时间复杂度O(n^2)。</p>
<h4>6.3.2 邻接表</h4>
<p>邻接矩阵是不错的一种图存储结构，但是，对于边数相对顶点较少的图，这种结构存在对存储空间的极大浪费。因此，找到一种数组与链表相结合的存储方法称为邻接表。
邻接表的处理方法是这样的：</p>
<ol>
<li>图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过，数组可以较容易的读取顶点的信息，更加方便。</li>
<li>图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以，用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。
邻接矩阵的时间复杂度O(n+e)。</li>
</ol>
<h4>6.3.3 区别</h4>
<ul>
<li>对于一个具有n个顶点e条边的无向图，它的邻接表表示有n个顶点表结点、2e个边表结点；</li>
<li>对于一个具有n个顶点e条边的有向图，它的邻接表表示有n个顶点表结点、e个边表结点；</li>
<li>如果图中边的数目远远小于n^2称作稀疏图，这是用邻接表表示比用邻接矩阵表示节省空间;</li>
<li>如果图中边的数目接近于n^2,对于无向图接近于n*(n-1)称作稠密图,考虑到邻接表中要附加链域，采用邻接矩阵表示法为宜。</li>
</ul>
<h3>6.4 遍历</h3>
<h4>6.4.1 深度优先遍历</h4>
<p>由初始顶点开始,沿着一条道一直走,当走到走不动的时候,再回来走一条可以走的通的道,然后再继续往下走,直到走不动,再回来…
使用栈，时间复杂度为O(n^2)(邻接矩阵）O（n+e)（邻接表）</p>
<h4>6.4.2 广度优先遍历</h4>
<p>从初始顶点开始，一层一层的遍历整个图。
使用队列：先进先出 时间复杂度为O(n^2)(邻接矩阵）O（n+e)（邻接表）</p>
<h3>6.5 基本术语</h3>
<ul>
<li>连通图：在无向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该无向图为连通图。</li>
<li>强连通图：在有向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该有向图为强连通图。</li>
<li>连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。</li>
<li>生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。</li>
<li>最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。</li>
</ul>
<h3>6.6 最小生成树算法</h3>
<h4>6.6.1 prim算法</h4>
<p>时间复杂度O(n^2），与图的边数无关，适合稠密图。此算法可以称为“加点法”。
流程：每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。</p>
<h4>6.6.2 Kruskal算法</h4>
<p>时间复杂度O（elge），适合稀疏图。此算法可以称为“加边法”。
流程：提取边的集合；找权值最小的边，寻找下一条边（如果该边使图变为环，舍去），直到全部顶点变为生成树时，结束。</p>
<h3>6.7 最短路径算法</h3>
<p>Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。O(N^2) 不能计算权重为负，适合有向图计算。</p>
<ol>
<li>基本思想：设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对vi∈V-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v, …, vk，就将vk加入集合S中，并将路径v, …, vk , vi与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。</li>
<li>设计数据结构 :
<ul>
<li>图的存储结构：带权的邻接矩阵存储结构 。</li>
<li>数组dist[n]：每个分量dist[i]表示当前所找到的从始点v到终点vi的最短路径的长度。初态为：若从v到vi有弧，则dist[i]为弧上权值；否则置dist[i]为∞。</li>
<li>数组path[n]：path[i]是一个字符串，表示当前所找到的从始点v到终点vi的最短路径。初态为：若从v到vi有弧，则path[i]为vvi；否则置path[i]空串。</li>
<li>数组s[n]：存放源点和已经生成的终点，其初态为只有一个源点v。
伪代码:
<pre><code>初始化数组dist、path和s；
while (s中的元素个数<n){
在dist[n]中求最小值，其下标为k；
输出dist[j]和path[j]；
修改数组dist和path；
将顶点vk添加到数组s中；
}</code></pre>
<h3>6.8 环的检测（有向图、无向图）、二部图的检测、树的检测</h3></li>
</ul></li>
</ol>
<h3>6.9 拓扑排序</h3>
<h2>7 前缀树</h2>
<p>应用场景
前缀树被广泛地运用在字典查找当中，也被称为字典树。
举例：给定一系列字符串，这些字符串构成了一种字典，要求你在这个字典当中找出所有以“ABC”开头的字符串。</p>
<ul>
<li>
<p>解法 1：暴力搜索
直接遍历一遍字典，然后逐个判断每个字符串是否由“ABC”开头。假设字典很大，有 N 个单词，要对比的不是“ABC”，而是任意的，那不妨假设所要对比的开头平均长度为 M，那么时间复杂度是 O(M×N)。</p>
</li>
<li>解法 2：前缀树
如果用前缀树头帮助对字典的存储进行优化，那么可以把搜索的时间复杂度下降为 O(M)，其中 M 表示字典里最长的那个单词的字符个数，在很多情况下，字典里的单词个数 N 是远远大于 M 的。因此，前缀树在这种场合中是非常高效的。</li>
</ul>
<h3>经典应用</h3>
<p>网站上的搜索框会罗列出以搜索文字作为开头的相关搜索信息，这里运用了前缀树进行后端的快速检索。</p>
<p>汉字拼音输入法的联想输出功能也运用了前缀树。</p>
<h3>性质</h3>
<ol>
<li>每个节点至少包含两个基本属性。</li>
</ol>
<p>children：数组或者集合，罗列出每个分支当中包含的所有字符</p>
<p>isEnd：布尔值，表示该节点是否为某字符串的结尾</p>
<ol>
<li>前缀树的根节点是空的</li>
</ol>
<p>所谓空，即只利用到这个节点的 children 属性，即只关心在这个字典里，有哪些打头的字符。</p>
<ol>
<li>除了根节点，其他所有节点都有可能是单词的结尾，叶子节点一定都是单词的结尾。</li>
</ol>
<h3>实现</h3>
<p>前缀树最基本的操作就是两个：创建和搜索。</p>
<ol>
<li>创建</li>
</ol>
<p>遍历一遍输入的字符串，对每个字符串的字符进行遍历</p>
<p>从前缀树的根节点开始，将每个字符加入到节点的 children 字符集当中。</p>
<p>如果字符集已经包含了这个字符，则跳过。</p>
<p>如果当前字符是字符串的最后一个，则把当前节点的 isEnd 标记为真。</p>
<p>由上，创建的方法很直观。</p>
<p>前缀树真正强大的地方在于，每个节点还能用来保存额外的信息，比如可以用来记录拥有相同前缀的所有字符串。因此，当用户输入某个前缀时，就能在 O(1) 的时间内给出对应的推荐字符串。</p>
<ol>
<li>搜索</li>
</ol>
<p>与创建方法类似，从前缀树的根节点出发，逐个匹配输入的前缀字符，如果遇到了就继续往下一层搜索，如果没遇到，就立即返回。</p>
<h2>8 线段树</h2>
<h2>9 树状数组</h2>
<p>特点
树状数组的数据结构有以下几个重要的基本特征。</p>
<p>它是利用数组来表示多叉树的结构，在这一点上和优先队列有些类似，只不过，优先队列是用数组来表示完全二叉树，而树状数组是多叉树。</p>
<p>树状数组的第一个元素是空节点。</p>
<p>如果节点 tree[y] 是 tree[x] 的父节点，那么需要满足条件：y = x - (x & (-x))。</p>
<p>建议：由于树状数组所解决的问题跟线段树有些类似，所以不花篇幅进行问题的讨论。LeetCode 上有很多经典的题目可以用树状数组来解决，比如 LeetCode 第 308 题，求一个动态变化的二维矩阵里，任意子矩阵里的数的总和。</p>
<h5></h5>