第7章图 72 图的存储结构.ppt

第7章 图 7.2 图的存储结构 7.2.1 邻接矩阵 int a[n][n] 1.无向图的邻接矩阵 1 如果(vi，vj)∈E A(i,j)= 0 其它 7.2.1 邻接矩阵 邻接矩阵的特点 （1） A(i,i)=0 1≤i≤n； （2） 无向图的邻接矩阵是对称的 A(i,j)=A(j,i) 1≤i≤n, 1≤j≤n； 存入上(下)三角形，需n(n+1)/2个单元； （3） 无向图的邻接矩阵的第i行(或第i列)非零元素的 个数正好是第i个顶点的度 TD(vi )； （4） 有向图的邻接矩阵一般不对称。 有向图需要n2个单元； （5） 有向图的邻接矩阵的 第i行非零元素的个数是第i个顶点的出度 OD(vi)； 第j列非零元素的个数是第j个顶点的入度ID(vi)； 7.2.1 邻接矩阵 int a[n][n] 3. 网（带权值的图）的邻接矩阵 wij i!=j 且 (vi，vj)∈E或vi，vj∈E A(i,j)= ∽ i!=j ，无边或弧 0 i==j , 对角线元素 3. 网（带权值的图）的邻接矩阵 0 20 30 ∞ ∞ ∞ 20 0 ∞ 40 ∞ ∞ 30 ∞ 0 50 ∞ ∞ ∞ 40 50 0 70 80 ∞ ∞ ∞ 70 0 ∞ ∞ ∞ ∞ 80 ∞ 0 ? 在主函数中应用 int main() { AdjMWGraph G0; G0.CreatG(4,5); G0.PrintOut(); _getch(); return 0; } 7.2.3 邻接链表 1. 顶点的结构 const int MaxVertices=100; typedef int VerT; //顶点数据类型 typedef int DistT; //边的数据类型 struct item { VerT data; //顶点数据 Edge *adj; //邻接边的指针 }; 2.数组（向量） item Vertices[MaxVertices]; //顶点的数组 7.2.3 邻接链表 3. 边的结构 struct Edge { int dest; //邻接顶点下标 DistT weight; //边的权值，或更多 Edge *next; //指针 }; 7.2.3 邻接链表 const int MaxVertices=100; typedef int VerT; typedef int DistT; struct item { VerT data; //顶点数据 Edge *adj; //邻接边的指针 }; item Vertices[MaxVertices]; //顶点的数组 在主函数中应用 int main() { AdjTWGraph G0; int n0,e0; cinn0e0; G0.CreatG(n0,e0); G0.PrintOut(); _getch(); return 0; } * * 2.有向图的邻接矩阵 1 如果vi，vj∈E A(i,j)= 0 其它 A1= A2= 4 5 6 2 1 3 20 30 40 50 70 80 const int MaxVertices=10; const