边一般从0开始编号 点一般从1开始编号
邻接矩阵
1
2
3
4
5
6
|
邻接矩阵
二维数组w[u][v] 表示存储从 u->v的边的权值
时间复杂度o(n^2)//一般为n*m 完全图为n^2
空间复杂度o(n^2)
应用：只有在点数不多的稠密图(n = 10^3,m = 10^6)
|
以无向图为例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
输入
4 5
1 2 20
1 4 40
2 3 50
2 4 60
3 2 30
输出
1 2 20
2 1 20
2 3 30
3 2 30
2 4 60
4 1 40
4 2 60
1 4 40
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
const int N = 1e3+10;
int w[N][N];
int vis[N];
int n , m;//n为节点数 m 为边数
void dfs(int u){
vis[u] = true;
//从1还是从0开始看点/边集的编号是从0还是从1开始编号,一般是从1
//去枚举该点的出度 也就是边
for(int v =1;v<=m;++v){
//枚举每一个出度 如果出度的权值不为0 说明有点
if(w[u][v]){
printf("%d %d %d\n",u,v,w[u][v]);
//如果对应的点集已经在别的地方枚举过 就不要重复枚举了
//如 3号点的入度为 4 5 6 ，在4号点已经枚举输出 没必要 5 6继续枚举
if(vis[v]) continue;
//去枚举出度
dfs(v);
}
}
}
int main() {
scanf("%d %d",&n,&m);
for(int i =0;i<m;++i){//开始建图
int a,b,c; //a<->b , weight = c
scanf("%d %d %d",&a,&b,&c);
w[a][b] = c;
//w[b][a] = c; 无向图才用
}
std::cout<<"\n";
dfs(1);
}
|
edgeset
1
2
3
4
5
|
边集数组
边集数组e[i] 存储第i条边的{起点，终点，权值}
时间复杂度O(nm) //每个点都去枚举m条边
空间复杂度O(m)
应用：一般应用在Kruskal 需要将按边排序 直接存边。这里示例的是有向图 ,无向图一样的、因为都已经知道相连的信息了
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
输入
7 6
4 3 90
1 4 30
5 7 80
5 6 60
1 5 20
5 2 70
输出
1 4 30
4 3 90
1 5 20
5 7 80
5 6 60
5 2 70
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
const int N = 1e3+10;
struct edge{
int u , v , w;
}e[N];
int vis[N];
int n , m;
void dfs(int u){
vis[u] = true;
//去枚举该结点的所有可能的出度
for(int i=0;i<m;++i){
//如果枚举到的点的入度恰好和当前结点一样
//说明该结点和枚举到的结点有建立一条边
if(e[i].u == u){
//后面和邻接矩阵一样
int v = e[i].v;
int w = e[i].w;
printf("%d %d %d\n",u,v,w);
if(vis[v]) continue;
dfs(v);
}
}
}
int main() {
scanf("%d %d",&n,&m);
for(int i =0;i<m;++i){//开始建图
int a,b,c; //a<->b , weight = c
scanf("%d %d %d",&a,&b,&c);
e[i] = {a,b,c};
//e[] = {b,a,c};
}
std::cout<<"\n";
dfs(1);
}
|
邻接表
1
2
3
4
5
6
7
8
|
出边数组e[u][i] 存储u点的所有出边{终点v,权值w};
邻接表缺点不能处理反向边 不能根据正向边的编号找到反向边的编号 在网络流不能用
因为并没有对边进行编号 只能从一个点找到另一个点 你可能知道从1号点到2号点的边是多少 但是你从2号点到1号点的边什么时候输入的 不确定 都没用数组保存这个信息
所以你并不能通过1号点到2号点的边来反推2号点到一号店的边 所以不能处理反向边
应用：各种图 不能处理反向边
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
7 6
4 3 90
1 4 30
5 7 80
5 6 60
1 5 20
5 2 70
1 4 30
4 3 90
1 5 20
5 7 80
5 6 60
5 2 70
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
const int N = 1e3+10;
struct edge{
int v,w;
};
vector<edge> e[N];//每个数组元素都是vector<edge>类型
int vis[N];
int n , m;
//fa = 父结点 这里把a的出度是b 那么b的其中一个入度为a
//b的其中一个fa 就是a
void dfs(int u,int fa){
for(auto ed : e[u]){
int v = ed.v;
int w = ed.w;
/*
无向图判重 比如 1号结点指向2号 当dfs到2号点的时候
由于2号点存有一号点的的邻接链表结点，然后取出来 又去dfs 1号结点
这样就无限递归了.
所以当dfs到2号结点 并且取出1号结点 发现 和 2号结点的父节点1相等
这时候就停
*/
//if(v == fa) continue;
printf("%d %d %d\n",u,v,w);
dfs(v,u);//深搜下一个结点 父节点为当前结点
}
}
int main() {
scanf("%d %d",&n,&m);
for(int i =1;i<=m;++i){//开始建图
int a,b,w;
scanf("%d %d %d",&a,&b,&w);
e[a].push_back({b,w});
//e[b].push_back({a,w});//无向图
}
std::cout<<"\n";
dfs(1,0);//从1号开始深搜
}
|
链式邻接表
1
2
3
4
5
6
|
边集数组e[j] 存储第j条边的{起点u，终点v,权值w};
表头数组h[u][j] 存储u点的所有出边的编号;
通过u点拿到所有出边的编号 再通过编号去e数组询问 拿到u点的所有出度结点 结点从1开始编号 边从0开始编号
时空o(n+m)
应用：各种图 能处理反向边
|
1
2
3
4
5
6
7
8
9
10
11
12
|
6 5
4 3 90
1 4 30
5 6 60
1 5 20
5 2 70
1 4 30
4 3 90
1 5 20
5 6 60
5 2 70
|
解决邻接表不能通过找到边直接的关系，后面网络流常常用到
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
const int N = 1e3+10;
struct edge{
int u,v,w;
};
int n , m;
vector<edge> e;
vector<int> h[N];//
void add(int u,int v,int w){
e.push_back({u,v,w});//第i条边记录着u这个点的出度的信息
//第u个点存当前边(出边)，因为边的计数是从0依次计数
h[u].push_back(e.size()-1);
}
void dfs(int u , int fa){
//链式邻接表是通过 一个点 找到对应的边 再通过边可以知道自己到底连了哪些点
//开始取出当前结点的所有边
for(int i =0;i<h[u].size();++i){
//开始拿边
int j = h[i][j];//拿到对应的边
//再通过边去找连的哪个点
int v = e[j].v; int w = e[j].w;
//和前面一样 防止无限递归
if(v == fa) continue;
printf("%d %d %d\n",u,v,w);
dfs(v,u);
}
}
int main() {
scanf("%d %d",&n,&m);
for(int i =0;i<m;++i){
int u , v ,w;
std::cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);//无向图
}
std::cout<<"\n";
dfs(1,0);
}
|
那如何找到反向边？
如果你是0 那么你的反向边就是1 因为存储的时候是从0开始存的 刚好符合异或的运算
如果你拿到a 只需 a ^1即可拿到 b , 即便你拿到b b^1 还是a / 相反取真 相同取假
这种 ^ 1的位运算 而且是从0开始成对出现 恰好为找反向边提供了条件 之后网络流会用到
总结：
链式邻接表的区别和邻接表的区别
邻接表是 点对点 既通过点 找到所有点(出度) 并没有存储边的信息
而链式邻接表是通过 一个点 找到对应的边 再通过边可以知道存储了哪些点
链式前向星
重点掌握
不使用vector ，
与链式邻接表不同的是，表头数组只使用一维，即只存最新的一条边的编号。
通过这个编号可以找到所有剩余的边。
说白了，链式前向是通过拿到u点的第一条边，再通过这个边依次拿到剩下的边。
而链式邻接表可一次性拿到所有边，再通过边查询拿到指定的点。
1
2
3
|
struct edge{
int v,w,next; //通过h[]数组拿到最新的edge , 而edge里存着next
};
|
1
2
3
4
5
|
边集数组e[i] 存的是第i条边的{终点v,边权w,下一条边next};
表头数组h[u] 记录第u个点的第一条出边的编号
idx 记录边的编号 0.1.2.3...
时空o(n+m)
|
1
2
3
4
5
6
7
8
9
10
11
12
|
6 5
4 3 90
1 4 30
5 6 60
1 5 20
5 2 70
1 5 20
5 2 70
5 6 60
1 4 30
4 3 90
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
const int N = 8000010;
struct edge{
int v,w,next;
};
int n , m;
int idx = 0;//記錄的邊的編號
int h[N];
edge e[N];
void add(int u , int v, int w){
e[idx] = {v,w,h[u]};
h[u] = idx++;
}
void p(){
//遍历每一个点
for(int i = 1;i<=n;++i){
//遍历没个点的每一条边
//首先拿到i个点的首边，然后不断往下走
// ~(-1) = 0
for(int j = h[i];~j;j=e[j].next){
std::cout<<i<<" "<<e[j].v<<" "<<e[j].w<<"\n";
}
}
}
void dfs(int u , int fa){
for(int i = h[u];i != -1;i = e[i].next){
int v = e[i].v; int w = e[i].w;
if(v == fa) continue;
printf("%d %d %d\n",u,v,w);
dfs(v,u);
}
}
int main() {
// int f;是否为有向图
// std::cin>>n>>m>>f;
std::cin>>n>>m;
memset(h,255,sizeof(h)); //-1为代表结尾
for(int i =0;i<m;++i){
int u , v , w;
std::cin>>u>>v>>w;
add(u,v,w);
//if(f == 0)
add(v,u,w);
}
std::cout<<"\n";
dfs(1,0);
}
|
参考:
董晓算法