干货分享｜常见建图方式

常见建图方式假将所有的点序号抽象成连续的存在设有如下的图以[u, v, w]表示从点u到点v存在一条权值为w的有向边。[0, 2, 3][2, 4, 6][4, 0, 7][0, 3, 5][3, 1, 3]邻接矩阵示意图inf 表示无穷大数据结构graph[i][j]表示从点i到点j存在一条边权值为graph[i][j]的值。若graph[i][j]为 inf 则视为不存在从i到j的边。特别注意一点邻接矩阵天然的存在从 i 到 i 本身的点有时最好在初始化时把所有的graph[i][i]设为0。// 假设共有n个点 int graph[n][n];操作构图时直接赋值循环遍历所有点即可。// u出度点v入度点w权值 [u, v, w] // 访问点出发的所有的有向边 for (int v 0; v n; v 1) { w graph[u][v] if (w inf) { // 无穷大视为不存在边 } else { // do } }