图的基础概念及图的表示

基础概念

• 图，可定义为G = （V，E）。其中V中的元素称作顶点；集合E中的元素分别对应于V中的某一对顶点(U, V)，表示他们之间存在某种关系。也就是边

• 简单图
  不含任何自环的图称为简单图

• 完全图

• 连通图

• 通路

• 带权网络

• 包含n个顶点的图，之多可能包含多少个边？

  • 对于无向图，每一对顶点至多贡献一条边，所以总共不超过n(n-1)/2条边，且这个上界由完全图达到。
  • 对于有向图，每一对顶点都可能贡献2条边，因此至多可有n(n-1)条边。

• 度

  • 对于无向图：与顶点v关联的边数，称作v的度数。
  • 对于有向图：有向边：e = (u, v) e称作u的出边，称作v的入边。出边总数称为出度，入边总数称为入度。

图的表示

邻接矩阵

邻接矩阵是图的最基本表示方式，使用方阵A[ n ] [ n ]表示由n个顶点构成的图，其中每个单元，各自负责描述一对顶点之间可能存在的邻接关系。

Paste_Image.png

邻接表

参考资料
《数据结构：C++语言版》3th 邓俊辉