7.1图的定义和术语 6.生成树 定义:设无向图G是含有n个顶点的连通图,则图G的生成树是 含有n个顶点,且只有n-1条边的连通子图 三要素: n个顶点极小连通子图, n-1条边 若再加一条边 必构成环 连通 生成树一>m-1条边
7.1 图的定义和术语 6. 生成树 定义：设无向图G是含有n个顶点的连通图，则图G的生成树是 含有n个顶点，且只有n-1条边的连通子图 三要素： n个顶点 n-1条边 连通 极小连通子图， 若再加一条边， 必构成环 生成树 n-1条边
7.2图的存储结构 图有数组、邻接表、邻接多重表和十字链表等表示方法 数组表示法(邻接矩阵) 设图G=(V,{})有n个顶点,则G的邻接矩阵定义为n阶方阵A。 其中:A[i,j 若(vi,vj)或<v,ⅴj>∈E,i 0其它 例如:G的邻接矩阵aG2g 0110 01010 A1=0000 A2= 0001 0101 1000 0100 01100 无向图的邻接矩阵为对称矩阵
7.2 图的存储结构 图有数组、邻接表、邻接多重表和十字链表等表示方法 一、数组表示法（邻接矩阵） 设图G=（V，{E}）有n个顶点，则G的邻接矩阵定义为n阶方阵A。 其中：A[i，j]= 1 若（ vi，vj）或 <vi，vj>∈E，i≠j 0 其它 例如：G1的邻接矩阵 ┌ 0 1 1 0 ┐ A1＝│ 0 0 0 0 │ │ 0 0 0 1 │ 1 0 0 0 ① G2 ② ③ ④ ⑤ ┌ 0 1 0 1 0 ┐ A2＝│ 1 0 1 0 1 │ │ 0 1 0 1 1 │ 1 0 1 0 0 0 1 1 0 0 无向图的邻接矩阵为对称矩阵 ① ② ③ ④ G1