Algorithm14.0 图论 数据结构存储形式

// 数据结构：结构体「起点、终点、权重」
struct node {
  int from, to, cost;
  bool operator < (const node n) const{return cost < n.cost;} // kruskal初始化 => 边权排序
}edge[maxedge];

// 遍历
for (int i = 1; i <= number_of_edge; i++) {
  int from = edge[i].from, to = edge[i].to, cost = edge[i].cost;
}

// 数据结构：二维数组
int mp[maxpoint][maxpoint];
// 遍历
for (int i = 1; i <= number_of_point; i++) {
  for (int j = 1; j <= number_of_point; j++) {
    int from = i, to = j, cost = mp[i][j];
  }
}

// 数据结构：向量+结构体「终点、权重」
struct node {
  int to, cost;
};
vector<node> b[maxpoint];
// 遍历
for (int i = 1; i <= number_of_point; i++) {
  for (int j = 0; j < b[i].size; j++) {
    int from = i, to = b[i][j].to, cost = b[i][j].cost;
  }
}

// 数据结构：数组+结构体「终点、指向下一个点的指针」
struct node {
  int to, next; // 也可以添加cost，用来表示边权
}edge[maxedge<<1]; // 因为LCA可能是无向图，所以要正反两方向都addedge，所以要maxedge<<1
edge[maxedge]; // 因为最短路有可能是有向图，所以只需要一个方向addedge，所以只用maxedge即可
int head[maxpoint], tot;
// --添加边的操作--
void addedge(int from, int to) {
  edge[++tot].to = to;
  edge[tot].next = head[from];
  head[from] = tot;
}
// 遍历
for (int i = 1; i <= number_of_point; i++) {
  for (int j = head[i]; j; j=edge[j].next) {
    int from = i, to = edge[j].to; // cost = edge[j].cost
  }
}