终于看到和图论有关的东西了，这次只是整理《数据结构》的图的知识，等C++过完，看《图论算法理论实现及应用》，再详细深入图论吧。 图是一种较线性表和树更为复杂的数据结构。不同线性表一对一的关系，图表示的多对多的关系。

术语

在图中的数据元素通常称作顶点

VR是两个顶点之间的关系的集合。若<v,w>属于VR，则<v,w>表示从v到w的一条弧，且称v为弧尾或初始点，称w为弧头或终端点，此时的图称为有向图，若<v,w>属于VR必有<w,v>属于VR，即VR是对称的，则以无序对（v,w）代替这两个有序对，表示v和w之间的一条边，此时的图称为无向图。

若<vi,vj>属于VR，则vi!=vj，那么，对于无向图，e的取值范围是0到(n(n-1))/2。有(n(n-1))/2条边的无向图成为完全图。

对于有向图，e的取值范围是0到n(n-1)。具有n(n-1)条弧的有向图称为有向完全图。

又很少条边或弧的图成为稀疏图，反之称为稠密图。

有时图的边或弧具有与它相关的数，这种与图的边或弧相关的数叫做权。这种带权的图通常称为网。

假设有两个图G=(V,{E})和G'=(V',{E'})，如果V'属于V且E'属于E，则称G'为G 的子图。

对于无向图G=(V,{E})，如果边（v,v'）属于E，则称顶点v和v'互为邻接点，即v和v'相邻接。边（v,v'）依附于顶点v和v'，或者说（v,v'）与顶点v和v'相关联。

顶点v的度和v相关联的边的数目记为TD（V）。对于有向图G=（V，{A}），如果弧（v,v'）属于A，则称顶点v邻接到顶点为v'，顶点v'邻接自顶点v。弧<v,v'>和顶点v，v'相关联。以顶点v为头的弧的数目称为v的入度，记为ID（v）；以v为尾的弧的数目称为v的出度，记为OD（v）；顶点的度为TD（v）=ID（v）+OD（v）。第一个顶点和最后一个顶点相同的路经称为回路或环。

序列中顶点不重复出现的路经称为简单路经。

除了第一个顶点和最后一个顶点之外，其余顶点之外，其余顶点不重复出现的回路称为简单回路或简单环。

在无向图G中，如果从顶点v到顶点v'有路径，则称v和v'是连通的。

对于图中任意两点是连通的，则称图为连通图。

连通分量指的是无向图中的极大连通子图。

在有向图G中，如果对于每一对vi，vj属于V，vi！=vj，从vi到vj和vj到vi都存在路经，则称为强连通图。

有向图的极大强连通子图称作有向图的强连通分量。

一个连通图的生成树是一个极小连通子图。

一棵有向图的生成森林有若干棵有向树组成。