强连通算法

❶ 请问数据结构中图的强连通分量是什么能具体解释一下吗

有向图的极大强连通子图，称为强连通分量(strongly connected components)。

在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。

(1)强连通算法扩展阅读：

强连通分量Tarjan算法

任何一个强连通分量，必定是对原图的深度优先搜索树的子树。那么只要确定每个强连通分量的子树的根，然后根据这些根从树的最低层开始，一个一个的拿出强连通分量即可。

维护两个数组，一个是indx[1..n]，一个是mlik[1..n]，其中indx[i]表示顶点i开始访问时间，mlik[i]为与顶点i邻接的顶点未删除顶点j的mlik[j]和mlik[i]的最小值(mlik[i]初始化为indx[i])。这样，在一次深搜的回溯过程中，如果发现mlik[i]==indx[i]那么，当前顶点就是一个强连通分量的根。

因为如果它不是强连通分量的根，那么它一定是属于另一个强连通分量，而且它的根是当前顶点的祖宗，那么存在包含当前顶点的到其祖宗的回路，可知mlik[i]一定被更改为一个比indx[i]更小的值。

至于拿出强连通分量，如果当前节点为一个强连通分量的根，那么它的强连通分量一定是以该根为根节点的(剩下节点)子树。在深度优先遍历的时候维护一个堆栈，每次访问一个新节点，就压入堆栈。

这样，由于当前节点是这个强连通分量中最先被压入堆栈的，那么在当前节点以后压入堆栈的并且仍在堆栈中的节点都属于这个强连通分量。

可以用反证法证明这个做法的正确性。假设一个节点在当前节点压入堆栈以后压入并且还存在，同时它不属于该强连通分量，那么它一定属于另一个强连通分量，但当前节点是它的根的祖宗，那么这个强连通分量应该在此之前已经被拿出。

❷ 怎么用c语言和数据结构来编写一个判断有向图是否为强连通图的算法

强连通图表明任意两点之间可以互相到达。
方案1：判断结点A可以到达的点的方法如下：
首先SA = {A}；
while 1
取SA中任意没有被去过的点x，根据以x为起点的有向线段，判断x可以直接到达的点，然后这些点加入SA；
如此循环，直到SA中的点的个数没有变化了
end
这样得到的集合SA是所有A可以到达的点的一个集合。
判断SA 是否等于S，若不等于S，表明不是强连通。

如此循环，求出所有S中的点的能够到达的点集。如果所有的点集都等于S表明强连通图。

方案2：可以优化1

❸ 对pagerank算法的整理

1、首先先大致介绍下pagerank，pagerank是Google排名算法法则的一部分，是用来标记网页的等级的一种方法，也是用来衡量一个网页好坏的唯一标准。pagerank他采用PR值来划分网页的受欢迎度，PR值越高，则表名受欢迎度越高，PR最高为10，最低为0，一般PR达到4，则表名网站已经不错了。PR为4的网站比PR为3的网站不是单纯的好一点来形容，他是一种里氏震级的形式来形容的，就好比地震的等级，是指数刻度增长的，因此可以想象PR为10的网站是一种什么程度。因为这个算法是Google提出的，因此Google将自己的网站PR值设置为10，所以想要自己的网站PR达到10，是非常难的，如果你的网站可以达到Google的水平。

2、介绍完了pagerank是一个什么东西后，我们就来介绍一下pagerank如何计算的。

2.1、用个例子来说明下PageRank算法

在网页A中有B、C、D三个链接，在网页B中有A、C两个个链接，在网页C中有D链接，网页D中有A、B两个链接。（可以看出这个图是强链接的，任何一个节点都可以到达另一个节点）。

我们假设每一个链接访问的概率是相同的，为了计算方便我们将每一个网页的PageRank设置为1。

先给出计算公式

PR(pj) 表示网页 pj 的 PageRank 得分，L(pj) 表示网页 pj 的出链接数量，1/L(pj) 就表示从网页 pj 跳转到 pi 的概率。

所以我们来计算第一次迭代后的PR值：

PR(A)=PR(B)/2+PR(D)/2

PR(B)=PR(A)/3+PR(D)/2

PR(C)=PR(A)/3+PR(B)/2

PR(D)=PR(A)/3+PR(C)/1

PR(A)+PR(B)+PR(C)+PR(D)=1

PR(A)=0.265, PR(B)=0.235, PR(C)=0.206, PR(D)=0.294

通过上面的公式在不断的进行迭代，可以得到一个收敛值，大概是在（0.265，0.235，2.206，0.294）附近。

2.2看完公式之后，我们来考虑俩种特殊的情况

2.2.1终止问题

上面过程要满足收敛性，需要具备一个条件：图是强连通的，即从任意网页可以到达其他任意网页。

互联网中存在网页不满足强连通的特性，因为有一些网页不指向任何网页，按照上面公式迭代计算下去，导致前面累计得到的转移概率被清零，最终得到的概率分布向量所有元素几乎都为0。

假设把上面图中C到D的链接丢掉，C变成了一个终止点，得到下面这个图：

转移矩阵M为：

不断迭代，最终得到所有元素都为0。

2.2.2 、陷阱问题

陷阱问题：是指有些网页不存在指向其他网页的链接，但存在指向自己的链接。比如下面这个图：

这种情况下，PageRank算法不断迭代会导致概率分布值全部转移到c网页上，这使得其他网页的概率分布值为0，从而整个网页排名就失去了意义。如果按照上面图则对应的转移矩阵M为：

不断迭代，最终得倒如下结果：

为了解决终止点问题和陷阱问题 ，下面需要对算法进行改进。假设选取下一个跳转页面时，既不选 当前页面 ，也不选 当前网页上的其他链接 ，而是以一定概率跳转到其他不相关网页，那么上面两个问题就能得到很好的解决，这就是 完整 PageRank 算法思想 。

N表示的时网页链接的个数，α表示不进行随机跳转的概率。

利用上面公式继续迭代下去，直到收敛，得到最终rank值。

PageRank 的计算是采样迭代法实现的：一开始所有网页结点的初始 PageRank 值都可以设置为某个相同的数，例如 1，然后我们通过上面这个公式，得到每个结点新的 PageRank 值。每当一张网页的 PageRank 发生了改变，它也会影响它的出链接所指向的网页，因此我们可以再次使用这个公式，循环地修正每个网页结点的值。由于这是一个马尔科夫过程，所以我们能从理论上证明，所有网页的 PageRank 最终会达到一个稳定的数值。整个证明过程很复杂，这里我们只需要知道这个迭代计算的过程就行了。

3、基于本文主题叫做数学建模之美，也是一篇读后感，所以我们还是写一下感受吧。

这个算法的优美之处，就在于巧妙地将网页内容的好坏，根据链接数的形式，用PR值进行了排名，它不仅激发网页越做越好，也促进了各个网页之间的联系。

同时在结构方面，他将一个复杂的问题，进行了简单的类比，用图结构的形式代替链接的形式，用户访问的顺序，也就是节点的走向。所以数学之美就在于他是非常的简单，用简单的原理，向我们展示了一个复杂的问题。