- 图的连通性
无向图：用图的遍历算法，调用DFS或BFS的次数就是连通分量的个数
有向图：上面的方法只能检测出非强连通分量，强连通分量见 Slides03.pdf
- 判断有向图是否存在回路
判断一个无向图是否为一棵树
思路1：判断是否是无回路的连通图
思路2：判断是否是n-1条边的连通图，若一次就能访问到所有的n个定点和n-1条边，那么就是一棵树。非递归DFS遍历图
要用一个栈来存放后面回来要遍历的节点，还要一个数组来记忆第i个定点是否在栈内或者曾经在栈内。见王道书籍P201，第三题最短路径
用DFS来遍历即可（类似树的层次遍历）DFS或BFS来判断两个定点是否存在路径
DFS的伪代码如下：
bool Exist_Path_DFS(Graph,i,j)
{
退出条件
if(i==j) return True
访问当前节点
visitd[i] = True
for x in x_neigbourhood
若当前节点没有被访问过 且 Exist_Path_DFS(Graph,x,j)==true
return True;
}
BFS的代码跟BFS遍历的代码一样，只不过在扫描到节点j的时候就马上返回。
还一种时间复杂度每次都是上面最坏的情况的方法：用BFS或者DFS从i点开始遍历，遍历完成后看visited[j]是否被遍历过即可，但是这种方法每次都要遍历完所有的节点。
- 设计一个算法求出从i到j所有简单路径
跟DFS是一样的，伪代码如下：
注意path和d作为参数只是在当前函数及其调用的子函数中会改变
调用，这种改变是向下的。
void FindPath(G,i,j,path[],d)
{
path[d] = i
d++
这里找到了没有->找到了输出路径
还没有找到向下
for x in x_neiberhood:
FindPath(G, i, j, path[], d)
path[d] = 0
}
