图的存储及基本操作

图的存储及基本操作

• 邻接矩阵法有向图的度是其第i列的非零元素之和，无向图的度是第i行或第i列的非零元素之和

• 邻接表中n个顶点，e条边，删除与某个顶点v相关的所有边的时间复杂度为O（n+e）

• 邻接表和邻接矩阵法对于不同的操作各有优势

• 无向图的邻接矩阵一定是对称矩阵

  • 但当有向图中任意两个顶点之间有边相连，且是两条方向相反的有向边（无向图也可视为有两条方向相反的有向边的特殊有向图）时，有向图的邻接矩阵也是一个对称矩阵