非强连通图的极大强连通图子图成为强连通分量。
强连通分量
(三).图的遍历
(1).深度优先遍历(相似于栈)
深度优先遍历的主要思想: 新进后出: (1).访问顶点v。 (2).从v的未被访问的邻接点选取一个顶点w,然后从w深度优先遍历。 (3).如果访问途中没有遇到未被访问的顶点,那么就先进的后出(栈) (4).重复上诉步骤,直至所有顶点被访问完毕。
(2).广度优先遍历(相似于层序遍历)
以顶点v为起始点,有近到远,一次访问和v有路径相通且路径长度为1,2..的 顶点,为了使先被访问顶点的邻接点"先于"后被访问顶点的邻接点"被访问"
(四).图的存储结构及实现
(1).邻接矩阵的存储结构
图的邻接矩阵存储也称数组表示法,用一个一维数组存储图中的顶点,用一个二维 数组存储图中的边(即个顶点之间的邻接关系),存储顶点之间的邻接关系的二维数组 称为邻接矩阵,设图G=(V,E)有n个顶点,则邻接矩阵是一个n*n的方阵
无向图
1.无向图的邻接矩阵一定是对称矩阵,而有向图的矩阵不一定对称。
2.在无向图,顶点i的度等于邻接矩阵中第i行(或第i列)非零元素的个数。
3.对于有向图,顶点i的出度等于邻接矩阵中第i行非零元素的个数;顶点
i的入度等于邻接矩阵中第i列非零元素的个数
4.判断顶点 i 和 j 之间是否存在边,只需要测试邻接矩阵中相应位置的元素
edge[i][j],若其值为1,则有边;否则,顶点 i 和 j
之间不存在边
5.查找顶点i的所有邻接点,扫描邻接矩阵的第i行,若edge[i][j]的值为1,则顶点j是顶点i 的邻接点
(2).邻接表的存储结构
邻接表是一种顺序存储与链式存储相结合的存储方法,像极了孩子表示法
顶点表:存储边表头指针的数组和存储顶点的数组构成了邻接表的表头数组。
1.vertex为数据域,存储顶点信息。
2.firstEdge为指针域,指向边的第一个结点。
3.adjvex为邻接点域,存放该顶点的邻接点在顶点表中的下标
4.next为指针域,指向边表的下一个结点
无向图
有向图
1.对于无向图,顶点i的度等于顶点i的边表中的节点个数。
2.对于有向图,顶点 i 的出度等于顶点 i 的出边表中的结点个数。
3.顶点 i 的入读等于所有出边表中以顶点 i 为邻接点的结点个数
4.判断从顶点到顶点j是否存在边,只需要测试顶点 i 的边表中是否存在临接点域为 j 的结点
5.查找顶点 i 的所有邻接点,只需要遍历顶点i的边表,该边表中的所有结点都是顶点的邻接点。