数据结构课上笔记15

左手的ㄟ右手 2022-04-08 08:49 238阅读 0赞

# 图的存储 #

**多重链表**：完全模拟图的样子，每个节点内的指针都指向该指向的节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70][]

节点结构内指针数为度

缺点：浪费空间、不容易操作

**数组表示法**（邻接矩阵表示法）

可用两个数组存储。其中一个 一维数组存储数据元素（顶点）的信息，另一个二维数组 （邻接矩阵）存储数据元素之间的关系（边或弧）的信息

有向图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 1][]

有向网：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 2][]

缺点：用于稀疏图时空间浪费严重

优点：操作较容易

**邻接表**

指针数组存放每个结点，每个结点后接所有能到达的节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 3][]

# 图的遍历 #

从图的任意指定顶点出发，依照某种规则去访问图中所有顶 点，且**每个顶点仅被访问一次**，这一过程叫做图的遍历。

图的遍历按照深度优先和广度优先规则去实施，通常有深度 优先遍历法（Depth\_First Search——DFS ）和 广度优先遍历法 （ Breadth\_Frist Search——BFS）两种。

简单棋盘搜索[https://blog.csdn.net/hebtu666/article/details/81483407][https_blog.csdn.net_hebtu666_article_details_81483407]

别的实现以后再贴

如何判别V的邻接点是否被访问？

为每个顶点设立一个“访问标志”。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70]: /images/20220407/4f68c3a18b4543eea07f9c8263bcbae4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 1]: /images/20220407/1da0c3749dcb4aa98fac7229069cc7c5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 2]: /images/20220407/e8c62266984e4308945bc78787a98945.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 3]: /images/20220407/10f0174b2bc34f659380da0af6effbde.png
[https_blog.csdn.net_hebtu666_article_details_81483407]: https://blog.csdn.net/hebtu666/article/details/81483407