数据结构速通之图的概念

相关知识

1.逻辑结构：多对多
2.图graph顶点vertex边edge
3.图G由两个集合构成，V是顶点的有限非空集合，E是V中顶点对的有限集。
4.V是⼀个有限的的⾮空集合，我们也称之为顶点集合，其元素称之为顶点或者点。V =
{v1,v2,v3,v4,v5}。｜V｜表示顶点的数⽬。
5.E是由V中的点组成的⽆序对构成的集合的边集，其元素称之为边，且同⼀点对在E中可以重复出现多次。⽤｜E｜表示边数。
6.图可以⽤图形表示，顶点集V中元素⽤平⾯上的⼀个⿊点表示，边集E中元素⽤⼀条连接V中相应点对的任意形状的线表示。现实中，点集合代表事物或对象的全体，边集代表点之间的联系或者相互作⽤。即图是描述事物之间联系或相互作⽤状态的⼀个概念。
7.边可重复，可有向，可由一节点连接至自身。

基本术语

1.简单图

在图结构中，若不存在顶点到其自身的边，且同⼀条边不重复出现，则称这样的图为简单图。

2.无向图

在图G中，如果代表边的顶点偶对是无序的，则称G为无向图。
若关系<V，V>无方向性，则称此时的图为无向图，关系用(V，V)表示，称之为⼀条边（edge）。

3.有向图

设 V 、V 为图中的两个顶点，若关系< V ，V >存在方向性，则称相应的图为有向图。起点为弧尾，终点为弧头。
（其实无向图也可以视为有向图，即每条边都是双向的，在图的存储中也确实是这么做的）

4.环

从一个结点出发，经过一系列边后，可回到原顶点，此结构称为环。
有向无环图（Directed Acyclic Graph，简称DAG）
如果有⼀个有向图，从任⼀顶点出发⽆法经过若⼲条边回到该顶点，那么它就是⼀个有向无环图。

5.完全图

如果图中的每两个顶点之间，都存在⼀条边，我们就称这个图为完全图。

6.端点与邻接点

在⼀个⽆向图中，若存在⼀条边（i，j），则称顶点i和顶点j为该边的两个端点。并称它们互为邻接点。
在⼀个有向图中，若存在⼀条边<i，j>，则称顶点i和顶点j为该边的两个端点。它们互为邻接点。 此时，顶点i为起点。顶点j为终点。

7.顶点的度、入度与出度

顶点的度：无向图中，顶点所具有的边的数目。
入/出度：此对概念仅用于有向图。分别指从该节点发出和进入的边数。一个结点的度等于出入度之和。
有e条边的图中度之和为2e

8.子图

若一图中结点是另一图中结点的子集，则称此图为另一图的子图。

9.路径和路径长度