可达矩阵求解过程？强连通分量是什么？

1. 可达矩阵求解过程？
2. 强连通分量是什么？
3. 弦图的三种经典例题？
4. mccade度量法计算公式？
5. 如何求出图中的强连通分支数？

可达矩阵求解过程？

求可达矩阵的方法：连乘法、幂乘法、warshall算法、迭代warshall、tarjan算法

利用布尔矩阵的运算性质给出了计算有向图可达矩阵的方法，该方法计算简便.

强连通分量是什么？

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

弦图的三种经典例题？

1.编程求解n阶斐波那契数列：从第3项开始，每一项都等于前两项之和，前两项均为1。
2.使用鸽巢原理解决的八皇后问题：八个皇后放置在8*8格的棋盘上，不能在同一行、同一列或同一对角线上，求所有可能的放置方案。
3. Kosaraju算法：它是一种应用于有向图的深度优先搜索（DFS）算法，应用于求解强连通分量（SCCs）。

mccade度量法计算公式？

McCabe度量法是由托马斯·麦克凯提出的一种基于程序控制流的复杂性度量方法。McCabe复杂性度量又称环路度量。它认为程序的复杂性很大程度上取决于程序图的复杂性。单一的顺序结构最为简单，循环和选择所构成的环路越多，程序就越复杂。这种方法以图论为工具，先画出程序图，然后用该图的环路数作为程序复杂性的度量值。程序图是退化的程序流程图。也就是说，把程序流程图的每一个处理符号都退化成一个结点，原来连接不同处理符号的流线变成连接不同结点的有向弧，这样得到的有向图就叫做程序图。

程序图仅描述程序内部的控制流程，完全不表现对数据的具体操作分支和循环的具体条件。因此，它往往把一个简单的IF语句与循环语句的复杂性看成是一样的，把嵌套的IF语句与CASE的复杂性看成是一样的。

如何求出图中的强连通分支数？

从节点1开始DFS，把遍历到的节点加入栈中。搜索到节点u=6时，DFN[6]=LOW[6]，找到了一个强连通分量。退栈到u=v为止，{6}为一个强连通分量。

初始化时Low[u]=DFN[u]=++index