图的基本概念及基本术语

基本数据结构

线性表结构：线性关系

         除了起始结点与终止结点外，每个结点只有一个直接前驱和一个直接后继

树形结构：层次关系

        除了根结点外，每个结点只有一个父结点，但可以有多个儿子结点

图：非线性结构更加复杂

        每个结点(顶点)既可以有前驱结点也可以有后继结点，且个数不加限制。

 

图的其它分类

简单图:不考虑顶点到其自身的边,即(u,v)是图G的边，则u≠v；且，如果图中没有相同的边,则称图为简单图。

完全图:设|V|=n, |E|=e。 

        对有向图G，若e=n(n-1)，则称G为完全有向图; 

        对无向图G，若e=n(n-1)/2;则称G为完全无向图。

稀疏图: 有很少条边的图（e<nlogn）

稠密图: 相反于稀疏图的图。

赋权图：

        若无向图的每条边都带一个权，则称相应的图为赋权无向图。 

        若有向图的每条边都带一个权，则称相应的图为赋权有向图。 

        通常，权是具有某种实际意义的数，比如，2个顶点之间的距离，耗费等。

网：带权的图称为赋权图或网。

 

顶点的度

无向图顶点的度：关联于该顶点的边的数目，记为D(v)。

有向图顶点：以顶点v为 终点的边的数目，称为v的入度，记为ID(v)； 

                        以顶点v为起点的边的数目，称为v的出度，记 为OD(v)； 

                        顶点v的度则定义为该顶点的入度与 出度之和，即D(v)=ID(v)+OD(v)。

 

基本操作：

1. CreateGraph(G): 创建图G.

2. DestroyGraph(G): 销毁图G.

3. LocateVertex(G,v): 返回顶点v在图G中的位置，若没有顶点v，则返回值为“空”（-1）.

4. GetVertex(G,i):返回图G中第i个顶点的值，若i大于图G中顶点数，则返回值为“空”(－1).

5. FirstAdjVertex(G,v): 图G中顶点v的第一个邻接点。若v无邻接点或图G中无顶点v，则返回值为“空”(-1)。

6. NextAdjVertex(G,v,w): 图G中顶点v的下一个邻接点紧跟在w后面）。若w是v的最后一个邻接点，则函数返回值为“空”。

7. InsertVertex(G,u): 在图G中增加一个顶点u。

8. Delete Vertex(G,v): 删除图G中顶点v及与顶点v相关联的弧（边）。

9. InsertArc(G,v,w): 在图G中增加一条从顶点v到顶点w的弧。

10.DeleteArc(G,v,w): 删除图G中从顶点v到顶点w的弧（边）。

11.TraverseGraph(G): 对图G的每个顶点访问一次且仅访问一次.

 

无向图与有向图的差别仅在于无向图中的边是顶点的无序对，而有向图中的边是顶点的有序对

• 所以可以将一个无向图G当作一个有向图来处理。