图的存储结构

设点的个数为n,边的个数为m:

1、邻接矩阵储存:

  定义一个二维数组ma[n+1][n+1],其中ma[i][j]表示节点i到节点j的链接关系,若i和j之间有边,则ma[i][j]的值通常为1或边的权值,否则ma[i][j]的值通常为0或正无穷(判断图是否连通通常用第一种,最短路或最小生成树通常用第二种。注意无向图邻接矩阵的对称性,有时两节点不一定只有一条边需特别处理)。

  优点:判断两节点是否直接相连便捷。

  缺点:遍历图时很麻烦,同时时间复杂度高。

2、数组模拟邻接链表储存

原文地址:https://www.cnblogs.com/InductiveSorting-QYF/p/10759144.html