图的表示

图的概念

• 无向图

  
  无向图

• 有向图

  
  有向图

• 带权图

  
  带权图

• 顶点：图中的元素。

• 边：图中的一个顶点可以与任意其他顶点建立连接关系。

• 度：跟顶点相连接的边的条数。

• 入度：表示有多少条边指向这个顶点。

• 出度：表示有多少条边是以这个顶点为起点指向其他顶点。

图的存储方式

1. 图最直接的一种存储方法就是，邻接矩阵，邻接矩阵的底层依赖一个二维数组.

   
   图一

• 无向图：如果顶点i与顶点j之间右边，我们就将A[i][j] 和A[j][i] 标记为1；
• 有向图：如果有顶点i到顶点j之间，有一条箭头从顶点i指向顶点j的边，那我们就将A[i][j]标记为1.同理，如果有顶点j到顶点i之间，有一条箭头从顶点j指向顶点i的边，那我们就将A[j][i]标记为1.
• 权重图：对于带权图，数组中就存储相应的权重。

2. 图的另一种存储方法为邻接表。

   
   图二