图计算机的表现形式以及遍历方法

一、图在计算机的几种表现形式

二、图的遍历

针对图可能产生一个顶点多次访问的状况，用黑、灰、白来加以区分

图的遍历算法

1、广度遍历（BFS）

广度优先搜索算法（Breadth First Search）：简称为 BFS，又译作宽度优先搜索 / 横向优先搜索。是一种用于遍历或搜索树或图的算法。该算法从根节点开始，沿着树的宽度遍历树或图的节点。如果所有节点均被访问，则算法中止

1、寻找节点所对应的所有子节点

2、利用连接链表

3、判断是否白色的原因，有可能节点已被发现，针对多个父节点的状况

自我模式方式

1、按照层次遍历，采用递归，参数，需要遍历的数组

2、用临接链表，遍历数组

3、黑色的意义不大

2、深度遍历（DFS）

此图可能是一个森林，而不是一棵树，这是已广度最大的区别

3、拓扑排序

深度优先搜索每个节点，并且搭上时间戳

针对时间戳进行排序，就是一个线性的拓扑排序

三、名词定义

1、邻接链表定义

邻接表是一种数组与链表相结合的存储方式；用一个一维数组取存放图的顶点，记做顶点表；该数组中的每一个顶点的所有邻接点构成一个链表，无向图称该链表为该顶点的边表，有向图称该链表为该顶点作为弧尾的出边表；

当然，顶点表也可以用链表来存放，不过由于顶点数是确定的，所以用数组较为合适，方便查询；

2、强连通分量定义

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

1、分量图c的性质