【图论】邻接表

邻接矩阵

给如下一个有向图：

该图有四个节点，五条边。右侧表示了有向图的起点，终点以及边权

根据该图建立邻接矩阵：

可以发现，邻接矩阵中许多位置并没有使用，故浪费了空间与时间

邻接表

让起点与终点直接相连，而不考虑先后顺序

将终点和边权作为一个节点，按头插法插入每个起点位置，就构建了一个邻接表

链表实现

#include <bits/stdc++.h>
using namespace std;
struct node{
  int x; // 节点编号
  int w; // 某个顶点到x的权值
  node* next;
  node(int x_, int w_){
    this->x = x_;
    this->w = w_;
    next = nullptr;
  }
};
vector<node*> head;
void add_edge(int u, int v, int w){
  node* a = head[u]; // 现在的头
  node* b = new node(v,w); // 建立新的节点
  // 头插法
  b->next = a->next;
  a->next = b;
}
int main(){
  int n, m;
  cin >> n >> m;
  head.resize(n+1);
  for(int i = 0;i<=n;i++){
    head[i] = new node(i,0);
  }
  for (int i = 0; i<=m;i++){
    int u,v,w;
    cin >> u >> v >> w;
    add_edge(u,v,w);
  }
  // 遍历
  for (int i = 1;i<=n;i++){
    node* p = head[i]->next; // 从某个节点开始，指向其相邻节点并输出
    while(p){
      // 起点总是i，而i连接的所有节点均为其兄弟
      printf("(%d, %d, %d)",i,p->x,p->w);
      p = p->next;
    }
    cout << endl;
  }
  return 0;
}

数组实现

建立四个数组

edge[i]：表示索引为i的边的终点，大小为m
next[i]：表示索引为i的边的下一条兄弟边的索引，大小为m
head[i]：表示i的第一条边的索引，大小为n
weigh[i]：表示索引为i的权重，大小为m

#include <bits/stdc++.h>
using namespace std;
vector<int> head, edge, Next, weight;
int idx = 0; // 表示边的索引
void add_edge(int u, int v, int w){
  edge[idx] = v;
  weight[idx]= w;
  Next[idx] = head[u];
  head[u]=idx++;

}
int main(){
  int n, m;
  cin >> n >> m;
  head.resize(n+1,-1);
  edge.resize(m+1);
  Next.resize(m+1);
  weight.resize(m+1);
  for (int i = 0; i<=m;i++){
    int u,v,w;
    cin >> u >> v >> w;
    add_edge(u,v,w);
  }
  // 遍历
  for (int i = 1;i<=n;i++){
    for (int j = head[i]; ~j; j=Next[j]){
      int u = i;
      int v = edge[j];
      int w = weight[j];
      printf("(%d, %d, %d)", u, v, w);
    }
    cout << endl;
  }
  return 0;
}

链式前向星

图的多种表示

输入数据模式

平面图
邻接矩阵
邻接表

数组实现

用一个数组与一个结构体：

head数组，大小为顶点个数，保存边的下标，初始化为-1，表示从i出发没有边
edge结构体，大小为边个数，元素表示终点、距离与下一条边的位置

如输入1 4 9，表示从1出发，终点为4，距离为9

检查是否有从1出发的边，没有(-1)，next改为-1，此时第一条边从1出发，将head[1]=1

再输入4 3 8

检查是否有从4出发的边，没有(-1)，next改为-1，此时第二条边从4出发，将head[4]=2

再输入1 2 5

检查是否有从1出发的边，head[1]=1，next改为1，此时第三条边也从1出发，将head[1]=3

再输入2 4 6

检查是否有从2出发的边，没有(-1)，next改为-1，此时第四条边从2出发，将head[2]=4

再输入1 3 7

检查是否有从1出发的边，head[1]=3，next改为3，此时第五条边也从1出发，将head[1]=5

最终为

即实现了头插法

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int n, m, s, u, v, w, cnt;
int head[100005];
struct edge{
  int to, dis, nxt;
}edge[200005];
void Add_edge(int from, int to, int w){
  edge[++cnt].to = to;
  edge[cnt].dis = w;
  edge[cnt].nxt = head[from];
  head[from]=cnt;
}
void solve() {
  cin >> n >> m;
  fill(head, head+n+1,-1);
  for (int i = 1;i<=n;i++){
    cin >> u >> v >> w;
    Add_edge(u,v,w);
  }
  // 遍历
  for (int i = 1;i<=n;i++){
    for (int k = head[i];~k;k = edge[k].nxt){
      /*具体处理*/
    }
  }
  
}
int main()
{
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int tomorin=1;
  cin >> tomorin;
  while (tomorin--) solve();
  return 0;
}