第六章图 6.1基本概念和术语 1、图（有向图、无向图、网、有向网、无向网） PT PRESS 退出 然东续下一配
第 六 章 图 6．1基本概念和术语 1、图（有向图、无向图、网、有向网、无向网） 退出
② Vo 2 N (a)有向图G1 (b)无向图G2 图6-1 PT PRESS 然东续了一
图6-1
10 8 V 15 20 30 20 30 10 5 15 (a)有向网G3 (b)无向网G4 图6-2 PT PRESS 数东燃姨下一 n
图6-2
1、完全图、稀疏图、稠密图 2、子图 3、度、入度、出度 4、路径和回路 5、连通图和连通分量 6、生成树 PT PRESS 按续不一列 n
1、完全图、稀疏图、稠密图 2、子图 3、度、入度、出度 4、路径和回路 5、连通图和连通分量 6、生成树
1.2图的存储结构 6.2.1邻接矩阵 1 0 O 8 ∞ 20 8 ∞ 15 ∞ 0 30 0 0 A1= A2= a∞ 15 0∞ 10 5 0 0 20 10 o∞ ∞ ∞ 30 5 ∞ (a)G,的邻接矩阵 (b)G4的邻接矩阵 图6-3图和网的邻接矩阵 PT PRESS 然东续了一列 n
1．2图的存储结构 6.2.1 邻接矩阵 图6-3 图和网的邻接矩阵
(1)、以邻接矩阵为存储结构定义图类型GRAPH #define N 50 #define MAX 10000 typedef struct int vexs N]; /~这里仅以整型编号来表示顶点。 PT PRESS 然东续下一配
（1）、以邻接矩阵为存储结构定义图类型MGRAPH #define N 50 #define MAX 10000 typedef struct { int vexs[N]； /*这里仅以整型编号来表示顶点。 */
int arcs[N][N];/*这里把邻接矩阵定义成整型。 */ int vexnum, arcnum; /*图的当前顶点数和弧 数。*/ int network; /*用1表示网，0表示图。*/ int digraph; /*用1表示有向图，0表示无向图。若network-=1且 digraph=1则是有向网*/ }MGRAPH;/六用邻接矩阵为存储结构的图的定义*/ PT PRESS
int arcs[N][N]； /*这里把邻接矩阵定义成整型。 */ int vexnum， arcnum； /*图的当前顶点数和弧 数。*/ int network； /*用1表示网，0表示图。*/ int digraph； /*用1表示有向图，0表示无向图。若network=1且 digraph=1则是有向网*/ }MGRAPH； /*用邻接矩阵为存储结构的图的定义*/
(2)、用邻接矩阵为存储结构，输入一个图的数据 建立图的算法 算法6.1 如书第164页所示 PT PRESS 然东续下一配
（2）、用邻接矩阵为存储结构，输入一个图的数据 建立图的算法 算法 6.1 如书第164页所示
0 西 T西 0 西 ①工0☑ 硒 2 V2 0西 2 2 工西 面 2西 本 (a)G,的邻接表 )G,的邻接表 (⊙G的逆邻接表 图6-4 表结点 头结点 adjvex nextarc info data firstarc 图6-5 PT PRESS 按续不一 n
图6-4 图6-5
(1)、以邻接表为存储结构定义图类型ALGRAPH typedef struct arcnode/*表结点定义*/ int adjvex; /*邻接点编号*/ struct arcnode *nextarc; int weight; /*这里用weight表示最为常用的 权值*/ YARCNODE,*ARCNODEPTR: typedef struct vnode {int data;/*可以处理为任意类型，本书把它处理 为顶点编号*/ ARCNODE *firstarc; VNODE,ADJLISTIN] PT PRESS 续下一
（1）、以邻接表为存储结构定义图类型ALGRAPH typedef struct arcnode /*表结点定义*/ { int adjvex； /* 邻接点编号*/ struct arcnode *nextarc； int weight； /* 这里用weight表示最为常用的 权值*/ }ARCNODE， *ARCNODEPTR； typedef struct vnode { int data； /*可以处理为任意类型，本书把它处理 为顶点编号*/ ARCNODE *firstarc； } VNODE，ADJLIST[N]；