图这种数据结构表现的是对象集合以及其间的关系的集合。
图中的“对象”称为结点(Node)或者顶点(Vertex)，通常用圆来表示。“关系”表示顶点与顶点之间的关系，称为边(Edge)。圆与圆之间的关系用连线或者箭头来表示。
无向图
无向图是边没有方向的图。可以用来表现朋友关系这一类的关系。
有向图
有向图是边有方向的图，比如可以用来表示一件事物的学习顺序，要先学会某样知识才能学下一样知识。
加权无向图
加权的“权”就是给边赋的值。有了权值，我们可以表示诸如两个地点之间的距离这样子的信息。
加权有向图
有了加权有向图，那么就可以为A->B和B->A来设置不同的权值。
图的表述
设顶点的集合为V，边的集合为E的图记作G=(V,E)。并且这个图的定点数和边数分别为|V|、|E|。
连接两个顶点u、v的边记作e = (u, v) ，在无向图之中，(u,v) 和 (v,u)代表同一条边。在加权图中，边 (u, v) 的权值记作 w(u, v)
两个点的相邻：如果无向图中存在边(u, v) ，那就称这两个点相邻。
路径： 一组相邻顶点的序列称为路径。起点和终点相同的路径称为环
不存在环的有向图称为DAG
度：与顶点u相连的边数称为顶点u的度。对于有向图来说还有入度和出度。
连通图：对于有向图而言，如果任意两点u, v之间，都存在使得u能到达v的路径。
子图：对于两个图G和G’，如果G’的顶点集合和边的集合是G的子集，那么称G’是G的子图。
邻接表表示法
邻接表表示法中，对于每个顶点，都用一个邻接表来表示，每个邻接表中的元素表示与当前结点相连的顶点。
邻接矩阵表示法
邻接矩阵表示法用|V|*|V|的矩阵表示图。如果顶点i到顶点j存在边，那么a(ij) = 1，否则为0；
邻接矩阵表示法的优点
·可以通过M[u][v]直接引用边(u, v), 因此只需常数时间O(1)即可确定顶点u和顶点v的关系
·只要更改M[u][v] 就能完成边的添加与删除，简单高效。
邻接矩阵表示法的缺点
·消耗的内存空间等于顶点数的平方。如果图的边数较少（稀疏图），则会浪费大量的内存空间。
·在一个邻接矩阵中，只能记录顶点u到顶点v的一个关系（一个基本型的二维数组中，无法在同一对顶点之间画出两条边）
例题：
ALDS1_11_A
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_A
代码语言：javascript复制#include<iostream>
using namespace std;
int g[101][101];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i )
{
int u;
cin>>u;
int k;
cin>>k;
for(int j=1;j<=k;j )
{
int v;
cin>>v;
g[u][v] = 1;
}
}
for(int i=1;i<=n;i )
{
for(int j=1;j<=n;j )
{
cout<<g[i][j];
if(j!=n) cout<<" ";
else cout<<endl;
}
}
}
