深度优先搜索(Depth First Search，DFS)：
相当于树的先序遍历
用邻接表存储，则DFS的时间复杂度为O(N+E)
用邻接矩阵存储，则DFS的时间复杂度为O(N^2)
广度优先搜索(Breadth First Search,BFS)：
相当于树的层序遍历
利用队列实现，从第一个点开始，压入队列，弹出该点时，将所有与该顶点直接关联的点压入队列，以此类推
时间复杂度同DFS
连通：如果从V到W存在一条（无向）路径，则认为V和W是连通的
路径：V和W的路径是一系列顶点的集合，路径的长度是路径的边数（带全，则是所有边的权重和）
简单路径：V和W路径的所有顶点都不同
回路：起点等于终点的路径
连通图：图中任意两个顶点都连通
连通分量：无向图的极大连通子图
1、极大顶点数：再加一个顶点就不连通了
2、极大边数：包含子图中，所有顶点相连的所有边
强连通：有向图中，V和W之间存在双向路径
强连通图：有向图中任意两顶点均强连通
强连通分量：有向图的极大强连通子图
遍历不连通的图：
遍历图的顶点，如果未被访问过，则调用DFS或BFS来进行访问
Q：一个顶点算不算连通分量？yes
例：007跳🐊问题
六度空间理论
网友评论