(摘自书：数据结构c++实现)
图的基本概念
图的术语
1.完全图(complete graph)（略）
2.权(weight)
3.邻接点(adjacent vertex)
4.子图(subgraph)
5.顶点的度(degree)
在无向图中，一个顶点v的度，是依附于顶点v的边的条数，记为TD(v)。
在有向图中，以顶点v为起始点的有向边的条数，称为顶点v的出度，记为OD(v)；
以之为终点的有向边的条数，称为其入度，记为ID(v)。
有向图中顶点v的度等于该顶点的入度出度之和：TD(v) = OD(v) + ID(v)。
一般：若图G中有n个顶点，e条边，则：e = (TD(v1) + TD(v2) + ... + TD(vn)) / 2。
6.路径(path)
在图G = (V,E)中，若从顶点vi出发，沿一些边经过一些顶点(vx,vx,vx,vx...)，到达vj，则刚才那些顶点序列称为从vi到vj的路径。
7.路径长度(path length)
对于不带权的图，边的数目即为路径长度。有权则为权和。
8.简单路径和回路(cycle)
对于一条路径，若路径上各顶点均不相同，则称此路径为简单路径。
若路径上第一个顶点和和最后一个顶点相同，则称这样的路径为回路或环。
如：0，1，2组成一个 简单路径；0，1，2，0组成一个环。
9.连通图和连通分量(connected graph and connected component)
无向图(子图)各点皆连
10.强连通图和强连通分量(strongly connected digraph)
有向图各(子图)各点皆连
11.生成树(spanning tree)
一个连通图的生成树是它的极小连通子图，它包含图全部n个顶点和仅使这n个顶点连通的n-1条边。如果一个有向图只有一个入度为0的顶点，其他顶点的入度均为1（老鹰捉小鸡，鸡尾无入），则称这个有向图为有向树。一个有向图的生成森林由若干棵有向树组成，生成森林含有图中所有的顶点，且只有足以构成若干颗互不相交的有向树的弧。
图的基本操作
和其他结构类似，图的基本操作主要也是插入、删除和查找。
- InsertVertex(vertex)
- InsertEdge(v1, v2)
- DeleteVertex(v)
- DeleteEdge(v1, v2)
- GetWeight(v1, v2)
- GetFirstNeighbor(int v) 在图中取顶点v的第一个邻接点
- GetNextNeighbor(int v1, int v2) 在图中取顶点v1的在v2后的下一个邻接点。
- Travers()遍历图，按某种次序访问图中所有顶点，且只访问一次。
- IsEmpty()判断图是否为空
图的存储结构
由于在图中，任意两个顶点之间都可能存在联系，所以无法在存储位置上反应数据元素之间的联系，因此图没有顺序存储结构。
不适合多重链表，具体用哪种结构根据具体问题来确定比较好。
常用的结构：邻接矩阵、邻接表、邻接多重表、十字链表。
邻接矩阵
除了记录顶点信息，还需要表示各个顶点关系的矩阵，称之为邻接矩阵。二维数组arcs[n][n]
无向图的邻接矩阵是对称的，将第i行/列的元素值相加，就得到了顶点i的度(有几条边和它相连)
有向图可能是不对称的，某个顶点所在列相加为入度，行相加为出度。
(见书，略)
邻接表
邻接表是邻接矩阵的改进。当图中的边数很少时，邻接矩阵会出现大量的零元素，为了节约空间，将邻接矩阵的每一行改成一个单链表。
网友评论