阅读量:0
一、有向图的存储方式
(1)邻接矩阵;(2)邻接表
二、有向图的存储
#include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 100010, M = N * 2; int h[N], e[M], ne[M], idx; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } int main() { memset(h, -1, sizeof h); }
三、有向图的深度优先搜索
#include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 100010, M = N * 2; int h[N], e[M], ne[M], idx; bool st[N]; void dfs(int u) { st[u] = true; for(int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if(!st[j]) dfs(j); } } int main() { memset(h, -1, sizeof h); bfs(1); }