深度优先搜索(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跳🐊问题
六度空间理论
网友评论