图这种数据结构表现的是对象集合以及其间的关系的集合。
图中的“对象”称为结点(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
#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;
}
}
}