引入

我们知道如何构建一个图的数据结构，那么现在，我们看看如何根据一棵图的图形，创建一张图到内存中去。

创建数据结构

#define MAX_VEX_NUM 50  //最大的容量暂定为50
typedef enum {DG, UDG} GraphType;  //选择有向图还是无向图
typedef struct {
    char vexs[MAX_VEX_NUM];  //一维数组存储顶点
    int arcs[MAX_VEX_NUM][MAX_VEX_NUM];   //二维数组（邻接矩阵）存储边
    int vexnum, arcnum;  //记录顶点的数量和边的数量，等下用作循环判断条件
    GraphType type;  //记录图得类型
} MGraph;

数据结构中

• 记录顶点的数量和边的数量，等下用作循环判断条件
• 记录图得类型，等下用于写入矩阵

引入

学了那么多图的知识，是时候动手设计一下图的存储结构了，图跟线性表、树有那么大得差别，所以图的数据结构要复杂很多。

思考

我们先回忆一下线性表和树得存储结构

• **线性表：**一对一的关系，用数组和链表就能很好的表示。
• **树：**一对多得关系，用数组和链表得特性结合在一起就可以很好的表示。

那么图呢？

• 图上的任意一个顶点都可以是第一个顶点，谁开始都行。
• 任意一个顶点的邻接点也不存在次序关系，多对多，大家都一样。

我们观察下面的四张图

引入

前面我们基本讲了什么是图结构，以及顶点、边和弧之间不同状态的特殊图结构，我们今天继续，看看这些顶点、边和弧之间的关系。

关系

我们来讲讲顶点和边的一些关系

顶点和边的关系

我们说，如果存在一个无向图，G（V，E）

• 图中的两个顶点构成的边$(V1 , V2)\in E$属于 E 的集合
• 那么我们就说 V1 和 V2 互为邻接点（Adjacent）
• 也就说明 V1 和 V2 相邻接，不是连接！。
• 对于边(V1 , V2)来说
• 边(V1 , V2)依附（Incident）于 顶点 V1和 V2
• 也可以说边(V1 , V2)与顶点 V1 、V2 相关联

无向图中的度

引入

终于，我们迎来了新的数据结构，图结构。之前的线性表，主要是一对一的关系，一个元素和另一个元素的关系。树结构，主要层与层之间一对多的关系，即一个结点可以有 N 个子树，N 个子树也只对应一个双亲结点。那么大家也应该猜到了，图解决的是多对多的数据关系。

图的定义

（顶点1有一个环的图结构）

**图（Graph）：**是有顶点的又穷非空集合和顶点之间的边集合组成。

• 通常表示为G（V，E）
• G 是一个图
• V 是图 G 中顶点的集合
• E 是图 G 中边的集合。

未完待续…

未完待续…

引入

上一节我们发现，树、森林和二叉树之间竟然有这么多有趣的关联，前根和后根遍历结果竟然都可以跟二叉树相同。二叉树竟然这么的独特，今天我们就来看看，如何打造一棵完美二叉树！

从一个问题出发

我们在使用二叉树的时候，会遇到类似这样的问题

• 这是一棵二叉树，结点连接线上的数字，是访问这个结点的概率
• 我们有5%的几率访问 A、15%访问 B、70%访问 C、10%访问 D
• 那么问题来了，既然绝大多数都是访问 C 的
• 那访问 C 必须要先判断是否是 A 或者 B，这样太麻烦了

要弄清楚这个问题，我先首先要弄清楚刚才哪些加了数字的结点是什么。