数据结构之图

图的基本概念

1. 图
2. 有向图
3. 无向图
4. 简单图
5. 多重图
6. 完全图（亦称 简单完全图）
7. 子图
8. 连通图，连通分量
9. 强连通图，强连通分量
10. 生成树，生成森林
11. 顶点的度（入度，出度）
12. 边的权和网
13. 稠密图，稀疏图
14. 路径，路径长度，回路
15. 简单路径，简单回路
16. 距离
17. 有向树

图的存储

👉🏻邻接矩阵法

一维数组存储顶点信息（将顶点编号），二维数组存储顶点间关系（二维数组存储边的信息）

邻接矩阵

网（带权图）的邻接矩阵

存储结构定义：

#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
typedef struct{
    VertexType Vex[MaxVertexNum];///顶点表（一维表）
    EdgeType Edge[MaxVertexNum][MaxVertexNum];///顶点关系表（二维表）
    int vexnum,arcnum;     
}MGraph;

👉🏻邻接表法

邻接表是在稀疏图的情况下对邻接矩阵的一种改进，是实际中广泛采用的一种存储结构。

结点结构

有向图和无向图的邻接表

存储结构定义

#define  MAX_VERTEX_NUM 20//最大顶点个数
#define  VertexType int//顶点数据的类型
#define  InfoType int//图中弧或者边包含的信息的类型
typedef struct ArcNode{
    int adjvex;//邻接点在数组中的位置下标
    struct ArcNode * nextarc;//指向下一个邻接点的指针
    InfoType * info;//信息域
}ArcNode;
typedef struct VNode{
    VertexType data;//顶点的数据域
    ArcNode * firstarc;//指向邻接点的指针
}VNode,AdjList[MAX_VERTEX_NUM];//存储各链表头结点的数组
typedef struct {
    AdjList vertices;//图中顶点的数组
    int vexnum,arcnum;//记录图中顶点数和边或弧数
    int kind;//记录图的种类
}ALGraph

👉🏻十字链表

有向图的另一种链式存储结构。可看是将有向图的邻接表和逆邻接表结合得到的一种存储方法。对应于有向图中的每一条弧有一个结点，对应于每个顶点也有一个结点。图的十字链表不唯一，但是一个十字链表确定一个图。

好处：既容易找以 V_i 为尾的弧，又容易找到以 V_i 为头的弧 ==> 容易求得顶点的入度和出度。

结点结构

存储结构定义

typedef struct ArcNode
{   
    int tailvex, headvex;      //弧尾、弧头在表头数组中位置
    struct ArcNode *hlink;     //指向弧头相同的下一条弧
    struct ArcNode *tlink;     //指向弧尾相同的下一条弧
    InfoType *info;            //弧相关信息指针
}ArcNode;

typedef struct VexNode
{   
     VertexType data;           //存与顶点有关信息
     struct arcnode *firstin;   //指向以该顶点为弧头的第一个弧结点
     struct arcnode *firstout;  //指向以该顶点为弧尾的第一个弧结点
}VexNode;

typedef struct  
{   VerNode xlist[MAX_VERTEX_NUM ] ;  //表头向量
    int vexnum, arcnum；
}OLGraph;

图示

👉🏻邻接多重表

无向图的另一种链式存储结构。 是为了解决在邻接表中对同一条边存储两个结点而引入的一种结构。

结点结构

其中：

mark 为标志域，可用于标记该边是否被搜索过。

ivex 和 jvex 记录依附于该边的两个顶点；

ilink 指示依附于 ivex 的下一条边。

jlin 指示依附于 jvex 的下一条边。

info 与边相关的信息。

其中：

data 存储顶点的相关信息；

firstedge 指示第一条依附于该顶点的边

图的遍历

👉🏻深度优先遍历 (DFS）

算法思路

性能分析

深度优先生成树

👉🏻广度优先遍历 (BFS)

算法思路

性能分析

广度优先生成树

👉🏻应用

图的遍历可以用来判断图的连通性。

图的应用

1. 图的遍历 —— 连通性判断
2. 有向无环图 —— 拓扑排序
3. 带权有向图 —— 最短路径，Dijkstra 算法