目录

一、有向图的邻接表

二、无向图的邻接表

一、有向图的邻接表

 最简单粗暴的方式就是把某个顶点发出的箭头指向的顶点全作为单个结点连接到此顶点的后面。结点数等于边数。

按正常思路的话，是一种递归遍历。

1.选一个点作为出发点。比如选一个v0。

2.从第一出发点按箭头指向任意一点作为第二出发点。

3.从第二出发点按箭头指向任意一点作为第三出发点。

以此类推，访问所有边。

需要注意的是如果一个点只被指，不指其他点，那就返回上一个出发点，从此出发点指向另一个点，如果这个出发点的边都被访问过，那就再返回上上一个出发点，直到所有边访问完毕，实际上这是一个回溯的过程。并且每条边只访问一次。

①我以v0作为第一出发点，指向v1，即v0->v1

②将v1作为第二出发点，指向v2，即v1->v2

③将v2作为第三出发点，发现v2不指向其他结点，那么回溯到v1

④v1->v4

⑤v4也不指向其他结点，那么回溯到v1，v1->v2，v1->v4，都已经访问过，再回溯到v0

⑥v0->v2

⑦v2不指向其他结点，回溯到v0

⑧v0->v3

⑨v3->v4

至此，所有边访问完毕。

二、无向图的邻接表

 同样，最简单粗暴的方式也是把某个顶点发出的箭头指向的顶点全作为单个结点连接到此顶点的后面。但是由于v0->v1，v1->v0，所以结点数是边数的两倍。

 这个的递归遍历思路的话放到一个无向图递归遍历程序里去。后续更新。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！