7.1图的定义和基本术语(续三) 路径:两个顶点之间的顶点序列,该序列的每个顶点 与其前驱是邻接点,每个顶点与其后继也是邻接点 回路(环):第一顶点和最后顶点相同的路径 简单路径:顶点不重复的路径 连通 两个顶点之间有路径 连通图:任意两个顶点之间有路径 连通分量:无向图中的极大连通子图。 强连通图:任意两个顶点之间有双向路径 强连通分量:有向图中的极大强连通子图 连通图的生成树:极小连通子图。 不唯一,但n个顶点的生成树 有且仅有n-1条边 生成森林
7.1 图的定义和基本术语(续三) 路径：两个顶点之间的顶点序列，该序列的每个顶点 与其前驱是邻接点，每个顶点与其后继也是邻接点 回路（环）：第一顶点和最后顶点相同的路径 简单路径： 顶点不重复的路径 连通： 两个顶点之间有路径 连通图： 任意两个顶点之间有路径 连通分量： 无向图中的极大连通子图。 强连通图：任意两个顶点之间有双向路径 强连通分量：有向图中的极大强连通子图。 连通图的生成树：极小连通子图。 不唯一，但n个顶点的生成树 有且仅有n-1条边。 生成森林：
7.2图的存储结构 7.2.1数组表示法 #define INFINITY INT MAX #define MAX VERTEX NUM 20 typedef enum(DG, DN, AG, AN GraphKind typedef struct ArcCell VRType ad Info Type *info J ArcCell, AdjMatrix[MAX VERTEX NUM I[MAX VERTEX NUM I typedef struct i VetexType vexs[MAX VERTEX NUM I AdjMatrix arc nt vexnum, arcum GraphKind kind )MGraph
7.2 图的存储结构 7.2.1 数组表示法 #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 typedef enum{DG, DN, AG, AN} GraphKind; typedef struct ArcCell{ VRType adj; InfoType *info; }ArcCell, AdjMatrix[MAX_VERTEX_NUM ][MAX_VERTEX_NUM ] typedef struct { VetexType vexs[MAX_VERTEX_NUM ]; AdjMatrix arc; int vexnum, arcnum; GraphKind kind; }MGraph;