【十字链表,邻接多重表（无向图的另一种链式存储结构）,图的遍历】
文章目录
- 十字链表
- 邻接多重表（无向图的另一种链式存储结构）
- 图的遍历
十字链表
方便找到入度和出度边。
顶点结点：
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)
