graph

图

图的概念

图的存储

网

带权的图就是网

图的存储结构

邻接矩阵(顺序存储)

1. 顶点数组：存储顶点信息
2. 边数组:存储顶点数组中2个顶点关系和权
3. 图{顶点数组，边数组，顶点数，边数，图类型}

不适合:查找顶点的度，需要扫描整张边数组，效率低，对顶点的相关操作 适合:对边依次进行处理的操作，

邻接表(链式存储)

1. 表头结点：存储顶点信息(data)和第一个邻接点地址(firstarc)，一般顺序存储在一个数组中
2. 表中结点：存储表头结点在数组中的位置和下一个结点的指针，可存储权值
3. 图{表头结点数组，顶点数，边数，图类型}

特点:

1. 出度为各自链表中的结点数，入度需要遍历整个表的结点，还有一种方法，求入度，建立一个逆邻接表
2. 稀疏图存储时，比使用邻接矩阵节省空间

十字链表(链式存储)

1. 顶点结点:存储顶点信息(data) 一个弧头结点指针(firstin) 一个弧尾结点指针(firstout)
2. 弧结点:tailvex 和 headvex 分别存储的是弧尾和弧头对应的顶点在数组中的位置下标； hlink 和 tlink 为指针域，分别指向弧头相同的下一个弧和弧尾相同的下一个弧； info 为指针域，存储的是该弧具有的相关信息，例如权值等
3. 图{顶点结点数组，弧数，顶点数}

特点:

1. 存储的是有向图或者有向网
2. 求入度出度方便，入度为弧头的数量，出度为弧尾的数量
3. 程序中构建链表对于每个新初始化的结点采用头插法进行插入

邻接多重表(链式存储)

邻接多重表可以看做是邻接表和十字链表的结合体

使用邻接表解决在无向图中删除某两个结点之间的边的操作时，由于表示边的结点分别处在两个顶点为头结点的链表中，所以需要都找到并删除，操作比较麻烦。处理类似这种操作，使用邻接多重表会更合适。

1. 表结点构成：

mark 为标志域，作用是标记某结点是否已经被操作过，例如在遍历各结点时， mark 域为 0 表示还未遍历；mark 域为 1 表示该结点遍历过； ivex 和 jvex 分别表示该结点表示的边两端的顶点在数组中的位置下标； ilink 指向下一条与 ivex 相关的边； jlink 指向下一条与 jvex 相关的边； info 指向与该边相关的信息。

2. 顶点结点构成：

data 为该顶点的数据域； firstedge 为指向第一条跟该顶点有关系的边。

总结

1. 邻接表适用于所有的图结构，无论是有向图（网）还是无向图（网），存储结构较为简单，但是在存储一些问题时，例如计算某顶点的度，需要通过遍历的方式自己求得
2. 十字链表适用于有向图（网）的存储，使用该方式存储的有向图，可以很容易计算出顶点的出度和入度，只需要知道对应链表中的结点个数即可
3. 邻接多重表适用于无向图（网）的存储，该方式避免了使用邻接表存储无向图时出现的存储空间浪费的现象，同时相比邻接表存储无向图，更方便了某些边操作（遍历、删除等）的实现