算法笔记-第十章-图的存储

图的基础知识

1.邻接表是图的一种链式存储结构，而邻接矩阵是图的一种顺序存储结构(数组)。
在邻接表中，对图中每个顶点都建立一个单链表，在第i个单链表中的节点表示衣依附于顶点vi的边。
2.若无向图中有n个节点、e条边，则它的邻接表需要n个头结点和2e个表结点。
无论有向图还是无向图，其邻接表不唯一，而邻接矩阵唯一。

图的邻接矩阵和邻接表

大佬讲解

无向图的邻接矩阵

#include <cstdio>
#include <cstring>

const int MAXN = 100;
int G[MAXN][MAXN];

int main() {  
    memset(G, 0, sizeof(G));  
    int n, m, u, v;  
    scanf("%d%d", &n, &m);  
    for (int i = 0; i < m; i++) {  
        scanf("%d%d", &u, &v);  
        G[u][v] = G[v][u] = 1;  
    }
    for (int i = 0; i < n; i++) {  
        for (int j = 0; j < n; j++) {  
            printf("%d", G[i][j]);  
            printf(j < n - 1 ? " " : "\n");  
        }
    }
    return 0;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

有向图的邻接矩阵

#include <cstdio>
#include <cstring>

const int MAXN = 100;
int G[MAXN][MAXN];

int main() {  
    memset(G, 0, sizeof(G));  
    int n, m, u, v;  
    scanf("%d%d", &n, &m);  
    for (int i = 0; i < m; i++) {  
        scanf("%d%d", &u, &v);  
        G[u][v] = 1;  
    }
    for (int i = 0; i < n; i++) {  
        for (int j = 0; j < n; j++) {  
            printf("%d", G[i][j]);  
            printf(j < n - 1 ? " " : "\n");  
        }
    }
    return 0;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

无向图的邻接表

#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 100;
vector<int> G[MAXN];

int main() {
    int n, m, u, v;  
    scanf("%d%d", &n, &m);  
    for (int i = 0; i < m; i++) {  
        scanf("%d%d", &u, &v);  
        G[u].push_back(v);  
        G[v].push_back(u);  
    }
    for (int i = 0; i < n; i++) {  
        printf("%d(%d)", i, (int)G[i].size());  
        for (int j = 0; j < G[i].size(); j++) {  
            printf(" %d", G[i][j]);  
        }
        printf("\n");  
    }
    return 0;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

有向图的邻接表

#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 100;
vector<int> G[MAXN];

int main() {
    memset(G, 0, sizeof(G));
    int n, m, u, v;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
    }
    for (int i = 0; i < n; i++) {
        printf("%d(%d)", i, (int)G[i].size());
        for (int j = 0; j < G[i].size(); j++) {
            printf(" %d", G[i][j]);
        }
        printf("\n");
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24