链式前向星

链式前向星

相当于手写链表建图

有向图

#define N 100005
struct Edge{int next,to;
}e[N];
int cnt;
int head[N];
void Add_edge(int from,int to){e[++cnt].to=to;//新一条边所指向的点e[cnt].next=head[from];//新边提供了下一条边的地址（均由from发出的边）head[from]=cnt;//from这点 最近加的边的地址
}

带权有向图

#define N 100005
struct Edge{int next,to,weight;
}e[2*N];
int cnt;
int head[N];
void Add_edge(int from,int to,int value){e[++cnt].to=to;e[cnt].next=head[from];e[cnt].weight=value;head[from]=cnt;
}

无向图

建两次边即可

下面是不带权值的，带权值类似上面加两句即可

#define N 100005struct Edge{int next,to;
}e[2*N];
int cnt;
int head[N];
void Add_edge(int from,int to){e[++cnt].to=to;//from->to的边e[cnt].next=head[from];head[from]=cnt;e[++cnt].to=from;//to->from的边e[cnt].next=head[to];head[to]=cnt;
}

由此看来，无向图其实也只需要在有向图的基础代码上面反过来多调用一次函数即可

Add_edge(x,y);
Add_edge(y,x);