图的基础知识

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;  
}

有向图的邻接矩阵

#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;  
}

无向图的邻接表

#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;  
}

有向图的邻接表

#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;
}