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