图.c

图：元素之间存在多对多关系（线性表的元素之间存在前驱和后继，树的元素之间存在父子关系，图的任意元素之间都有可能存在关系）。
    由顶点的有穷非空集合和顶点之间边的集合组成。
    在图型数据结构中，数据被称为顶点，数据之间的关系补称为边。
    在图中不允许出现没有点，但可以没有边。
    G(V,E),V表示顶点，E表示边的集合。
各种图的定义：
    无向图：顶点与顶点之间没有方向，这种边称为无向边，边用无向序偶对表示(v,v1)。
    V={A,B,C,D} E={(A,B),(B,C),(C,D),(D,A)}
    在无向图中，如果任意两个顶点之间都存在边，这种图称为无向完全图,那这种图的边为n*(n-1)/2。

    有向图：若顶点之间有方向，这种边称为有向边，也叫弧，用有序偶对表示<v,v1>,v1叫做弧头，v叫做弧尾。
    注意：若不存在顶点到自身和边，也不存在重复出现的边这种图叫做简单图，数据结构课程中讨论的都是简单图，数据结构课程中讨论的都是简单图。
    
    在有向图中如果任意两个顶点之间存在方向相反的两条弧，这种图叫做有向完全图。

    图中有很少边或弧的图叫做稀疏图，反之叫做稠密图。

    如果图中的边或弧有相关的数据，数据称为权，这种图也叫做网（带权图）。
    如果G(v,E)和G1(v1,E1),存在v1∈V,且E1∈E,那么G1是G的子图。

顶点与边的关系
    顶点的度：指的是顶点相关联的边或弧的条目数。
        有向图又分为出度和入度。
        入度：其他顶点到该顶点的弧的条目数。
        出度：从该点出发到其他顶点的弧的条目数。
        顶点序列：从一个顶点到另一个顶点的路径，路径长度指的是路径上的边或弧的条目数。

连通图相关术语：
    在无向图中，在顶点v到v1之间有路径，则称v到v1之间是连通的，如果任意两个顶点都是连通的，那么这种图称为连通图。
    无向图中的极大连通子图称为连通分量：
        1、必须是子图
        2、子图必须是连通的
        3、连通子图含有极大的顶点数
    在有向图中，任意顶点之间都存在路径，这种图叫做强连通图。
    有向图中的极大连通子图称为有向的强连通分量。
    在有向图中如果有一个顶点的入度为0，其他顶点的入度均为1，则是一颗有向树。

图的存储结构：
    图的存储主要是两个方面：顶点，边
    邻接矩阵：
        一个一维数组（顶点）和一个二维数组（边，弧）组成。
        二维数组i,i位置都是0，如果是无向图则数组对称（左上到右下对称）。
        优点：
            1、非常容易判定两顶点之间是否有边
            2、非常容易计算任意顶点的入度和出度。
            3、非常容易统计邻接点
        缺点：如果存储稀疏图，会非常浪费存储空间
    邻接表：
        由顶点表                   边表组成。
        顶点  下一个邻接点地址      顶点下标|下一个邻接点地址      
        A     ->                   [1] -> [3] -> NULL
        B     ->                   [2] -> NULL
        C     ->                   [4] -> [3] -> NULL
        D     ->                   
        E     ->                   
        优点：
            1、节省存储空间
            2、非常容易计算出度
        缺点：不方便计算入度
    十字链表：由于邻接表不能同时兼顾出度和入度，因此我们修改邻接的边表结构，使用即存储入度也存储出度，这种表就叫做十字链表。
    邻接多重表：由于遍历表时需要一些删除边操作而邻接表在删除边时非常麻烦，因此就设计出了邻接多重表
    边集数组：由两个一维数组构成，一个存储顶点的消息，另一个存储边的信息（它的每个数据元素都由一条边的起点到终点的下标和权组成），
这种存储结构更侧重于边的相关操作（路径、路径长度、最短路径），而统计顶点的度需要扫描整个数组，效率不高。

图的遍历：
    注意：图的遍历结果无论是深度优先还是广度优先，结果都不唯一
    深度优先：类似树的前序遍历。
    广度优先：类似树的层序遍历（需要借助队列）