图由点和边组成，有连通图和非连通图之分，还可以分为有向图和无向图
连通图：
非连通图：
有向图：
无向图：
连通分量：非联通图中不能连通的数量
度：一个点连接的边的数量
入度：有向图中到达一个点的边的数量
出度：有向图中从一个点出发的边的数量
图的存储：
1.邻接矩阵：用V*V的数组存有V个点的图，g[i][j]表示i和j有没有连接
1为有连接，0为没有连接
存储代码：
for(int i = 1; i <= m; i++)
{
int x, y;
cin >> x >> y;//两个点
g[x][y] = 1;
//g[y][x] = 1;（无向图要加）
}
2.邻接表：用动态数组存储一个点能到达的点
存储代码：
for(int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
g[a].push_back(b);
//g[b].push_back(a); （无向图要加）
}
图的遍历：
1.DFS
void dfs(int x)
{
cout << x << " ";
vis[x] = 1;//标记走过
for(int i = 0; i < g[x].size(); i++)//邻接表
{
int nx = g[x][i];
if (vis[nx] == 0)//没走过才能走
{
dfs(nx);
}
}
return;
}
2.BFS：
queue <int> q;
void bfs()
{
while (q.size())
{
int x = q.front();
q.pop();
cout << x << " ";
for(int i = 0; i < g[x].size(); i++)
{
int nx = g[x][i];
if (vis[nx] == 0)//没走过
{
vis[nx] = 1;//标记
q.push(nx);
}
}
}
return;
}
树
树就是没有环的连通图
特性：节点数-1=边数（判断树的标准）
树的深度（有向图DFS，搜索每个点取最大）
void dfs(int s, int d)
{
dn = max(dn, d);//最大深度
for(int i = 0; i < a[s].size(); i++)
{
dfs(a[s][i], d + 1);//下一层，深度+1
}
return;
}
树的宽度（无向图DFS，搜索每个深度的所有点取最大）
void dfs(int d, int s)
{
b[d]++;//存当前深度的宽度
bn = max(bn, b[d]);//最大宽度
vis[s] = 1;
for(int i = 1; i <= n; i++)//邻接矩阵
{
if (a[s][i] == '1' && vis[i] == 0)//能走
{
dfs(d + 1, i);
}
}
}
树上两点的距离（把一个点当作根节点，再BFS去搜另一个点）
void bfs(int t, int e)
{
vis[t] = 1;//起点
while (q.size())
{
q.pop();
}
q.push(t);
while (q.size())
{
int x = q.front();
q.pop();
if (x == e)//到终点
{
cout << cnt[x];
return;
}
for(int i = 0; i < a[x].size(); i++)
{
int nx = a[x][i];
if (vis[nx] == 0)
{
vis[nx] = 1;
cnt[nx] = cnt[x] + 1;
q.push(nx);
}
}
}
return;
}