爱网站找不到了,网站加网页,最新互联网平台项目,WordPress集成阿里图标文章目录 十字链表邻接多重表#xff08;无向图的另一种链式存储结构#xff09;图的遍历 十字链表
方便找到入度和出度边。 顶点结点#xff1a; data#xff1a;顶点存放的数据域。 firstin#xff1a;第一个入度边。 firstout#xff1a;第一个出度边。 弧度结点无向图的另一种链式存储结构图的遍历 十字链表
方便找到入度和出度边。 顶点结点 data顶点存放的数据域。 firstin第一个入度边。 firstout第一个出度边。 弧度结点 tailvex:尾结点。 headvex头结点。 建立十字链表的步骤 ①先找结点的出度例如a的出度有bc。所以a的最后一个firstout指针域指向出度结点因为结点是从下标为0到1,2所以表示为如图。 ②找到结点的出度例如a结点的入度就是dc。所以就是从下标为2到0,3到0.表示如图。 ③按照以上两个步骤进行查看剩下的顶点结点。最后形成的图就是十字链表。
邻接多重表无向图的另一种链式存储结构 图的遍历
从已知连通图中的某一顶点出发沿着一些边访遍图中的所有顶点使每一个顶点仅被访问一次叫做图的遍历它是图的基本运算。 遍历实质找每一顶点的邻接点的过程。 图的特点 图中可能存在回路且图的任一顶点都可能与其它顶点想通在访问完某个顶点之后可能会沿着某些边又回到曾经访问过的顶点。 怎样避免重复访问 解决思路 设置辅助数组visited[n]用来标记被访问过的顶点。
初始状态visited[i]为0顶点i被访问改visited[i]为1防止被多次访问。
图常用的遍历
深度优先搜索(Depth_First Search----DFS)广度优先搜索(Width_First Search----WFS)
