1. 4. 简单图
   1. · 【 3 】图的定义与相关概念
      1. 定义
         1. 图G由顶点集V和边集E组成，记为G=(V,E)，其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系(边)集合。若V={ v1,v2,...,vn},则用|V|表示图G中顶点的个数，也称图G的阶，E={(u,v)|u∈V，v∈V}，用|E|表示图G中边的条数。边：节点之间的连接，可以是有向或无向的
            1. 注意：线性表可以是空表，树也可以是空树，但图不可以是空图，就是说，图中不能一个顶点也没有，图的顶点集V一定非空，但边集E可以为空，此时图中只有顶点而没有边。
      2. 相关概念
         1. 有向图
            1. 若E是有向边（也称弧）的有限集合时，则图G为有向图。弧是顶点的有序对，记为<v,w>，其中v,w是顶点，v称弧尾，w称弧头，<v,w>称为从顶点v到w的弧，也称v邻接到w，或w邻接自v。
            2. (a)所示的有向图G1可表示为G1 = （V1，E1），V1 = {1,2,3} ，E1={<1,2>,<2,1>,<2,3>}
         2. 无向图
            1. 若E是无向边（简称边）的有限集合时，则图G为无向图。便是顶点的无序对，记为(v,w)或(w,v)，因为(v,w)=(w,v),其中v.w为顶点。可以说顶点w和顶点v互为邻接点。边(v,w)依附于顶点w和v，或者说边(v,w)和顶点v,w相关联。
            2. (b)所示的无向图G2可表示Wie，G2=（V2，K2）V2={1,2,3,4}，E2={(1,2)，(1.3)，(1,4)，(2,3)，(2,4)，(3,4)}
         3. 完全图（也称简单完全图）
            1. 对于无向图，|E|的取值范围是0到n(n-1)/2，有n(n-1)/2条边的无向图称为完全图，在完全图中任意两个顶点之间都存在边（ G2 是无向完全图）
            2. 对于有向图，|E|的取值范围是0到n(n-1)，有n(n-1)条弧的有向图称为有向完全图，在有向完全图中任意两个顶点之间都存在方向相反的两条弧
         4. 简单图
            1. 简单图是指没有自环（连接到自身的边）和重边（同一对节点之间的多条边）的图。
         5. 多重图
            1. 多重图是一种允许多条边连接同一对节点的图。这意味着在多重图中，同一对节点之间可以有多个平行的边。每条边可能具有不同的权重或属性
         6. 连通、连通图和连通分量
            1. 在无向图中，若从顶点v到顶点w有路径存在。则称v和w是连通的。若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。
            2. 无向图中的极大连通子图称为连通分量（不是最大）。若一个图有n个顶点，并且边数小于n-1，则此图必是非连通图。如图44-2(a)所示，图G4有3个连通分量，如图44-2(b)所示。
            3. 强连通图
            4. 在有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的，则称此图为强连通图
         7. 顶点的度、入度和出度
            1. 度定义为以该顶点为一个端点的边的数目
            2. 对于无向图，顶点b的度是指依附于该顶点的边的条数，无向图的全部顶点的度的和等于边的2倍
            3. 对于有向图，顶点v的度分为入度和出度，入度是以顶点v为终点的有向边的数目，记为ID(v)；而出度是以顶点v为起点的有向边的数目，记为OD(v)。顶点v的度等于其入度和出度之和，即TD(v) = ID(v)+OD(v)。
         8. 边的权和网
            1. 在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权重，这种边上带有权值的图称为带权图，也称网
            2. 距离
            3. 从顶点u从发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷
         9. 稠密图、稀疏图
            1. 边数很少的图称为稀疏图，反之称为稠密图。洗漱和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。一般当图G满足|E|<|V|log|V|时，可以将G视为稀疏图。
         10. 路径、路径长度和回路
             1. 顶点Vp到顶点Vq之间的一条路径是指顶点序列Vp,Vi1,Vi2,...,Vim,Vq，当然关联的边也可以理解为路径的构成要素。路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。若一个图有n个顶点，并且有大于n-1条边，则此图一定有环。
         11. 有向树
             1. 一个顶点的入度为0，其余顶点的入度均为1的有向图，称为有向树
   2. · 【 4 】图的表示与存储：邻接矩阵
   3. · 【 4 】图的表示与存储：邻接表