1、图的定义和基本术语

图  G=(V,E)， V顶点(数据元素)的有穷非空集合； E边的有穷集合。

无向图：每条边都是无方向的；有向图：每条边都是有方向的。

完全图：图中任意两个顶点都有一条边相连。

对于有n个顶点的无向完全图，要有  n(n−1)/2条边；对于有n个顶点的有向完全图，要有 n(n−1)条边。

稀疏图：有很少边或者弧的图e<nlogn。

稠密图：有较多边或者弧的图。

网：边/弧带权重的图。

邻接：有边/弧相连的两个顶点之间的关系，存在  (vi,vj)，则称  vi和vj互为邻接点；存在 <vi,vj>，则称 v i v_i vi邻接到 vj，  vj邻接于  vi。

关联(依附)：边/弧与顶点之间的关系，存在 (vi,vj),<vi,vj>，则称该边/弧关联于 v i 和 vj。

顶点的度：与该顶点相关联的边的数量，即为TD(v)，在有向图中，顶点的度等于该顶点的入度和出度之和。顶点的入度是以v为终点的有向边的条数，记作 ID(v)；顶点的出度为以v为出发点的有向边的条数，记作  OD(v)。

路径：接续的便构成的顶点序列；

路径长度：路径上边或者弧的数目/权值之和；

回路(环)：第一个顶点和最后一个顶点相同的路径；

简单路径：除路径的起点和终点可以相同外，其余顶点均不相同的路径；

简单环：除路径的起点和终点相同外，其余顶点均不相同的路径；

连通图(强连通图)：在无(有)向图  G=(V,E)中，若对于任意两个顶点  v,u，都存在从  v到  u的路径，则称图  G是连通图(强连通图)。

权和网：图中边或者弧具有相关数称为权。表明从一个顶点到另一个顶点的距离或者耗费。带权的图称为网。

子图：设有两个图 G=(V,E),G1=(V1,E1)，若满足V1∈V,E1∈E，则称  G1是 G的子图。

连通分量(强连通分量)：无向图 G的极大连通子图称为 G的连通分量，极大连通的意思是：该子图是  G的连通子图，将  G中任意一个不再该子图中的顶点加入之后，该子图不再连通。

有向图  G的极大强连通子图称为  G的强连通分量。极大强连通子图的意思是：该子图是  G的强连通子图，将  D的任何不在该子图中的顶点加入，子图不再是强连通的。

极小连通子图：该子图是 G的连通子图，在该子图中删除任意一条边，子图不再连通。

生成树：包含无向图  G的所有顶点的极小连通子图；

生成森林：对于非连通图，由各个连通分量的生成树的集合。

1.1 图的数据类型定义

图的抽象类型定义如下所示：

图的基本操作包括以下几种：

2、图的存储结构

图是多对多的逻辑结构，图没有顺序存储结构，但可以借助二维数组来表示元素之间的关系，如邻接矩阵，邻接表，邻接多重表，十字链表等

2.1 邻接矩阵

首先建立一个顶点表(记录各个顶点的信息)，和一个邻接矩阵(表示各个顶点之间的关系)。设图  A=(V,E)有n个顶点，则顶点表的表示如下所示：

图的邻接矩阵是一个二维数组A.arcs[n][n]，定义为：

下图是一个无向图邻接矩阵的示意图：

可以发现无向图的邻接矩阵是一个对称矩阵，同时对角线的元素均为0；顶点i的度等于第 i行(列)中1的个数；完全图的邻接矩阵中，对角线元素为0，其余元素均为1。

下图是一个有向图邻接矩阵的示意图：

在有向图邻接矩阵中，第 i行的含义是：以结点

vi为尾的弧，即出度边；第 i列的含义是：以结点

vi为头的弧，即入度边。有向图的邻接矩阵可能是不对称的；顶点的出度=第  i行的元素之和；顶点的入度=第 i列的元素之和；有向图顶点的度=第 i行的元素之和+第  i列的元素之和。

网-即有权图的邻接矩阵表示法，定义如下所示：

下图是一个网的邻接矩阵的示意图：

邻接矩阵的存储表示：用两个数组分别存储顶点表和邻接矩阵。

#define MaxInt 50000      //定义一个极大的数
#define MVNum 100       //定义最大的顶点数  
typedef char VerTexType;    //设顶点的数据类型为字符型
typedef int ArcType;      //设边的权值类型为整数型
typedef struct
{
  VerTexType vexs[MVNum];   //顶点表
  ArcType arcs[MVNum][MVNum]; //邻接矩阵
  int vexNum, arcNum;     //图当前的节点数量和边数量
}AMGraph;

采用邻接矩阵构建无向网：

//创建图
void CreatUDN(AMGraph &G)
{
  cin >> G.vexNum >> G.arcNum;
  for(int i = 0; i < G.verNum; ++i)
    cin>> G.vex[i];   //依次输入点的信息
  for(int i = 0; i < G.vexNum; ++i) //初始化邻接矩阵
    for(int j = 0; j < G.vexNum; ++j)
      G.arcs[i][j] = MaxInt;
  //给边赋值
  for(int k = 0; k < G.arcNum; ++k)
  {
    int v1 = 0, v2 = 0;
    double w = 0;
    cin >> v1 >> v2 >> w;   //输入当前边的顶点和边的权重
    int i = LocateVex(G, v1); //确定出点v1和v2在图中的位置
    int j = LocateVex(G, v2);
    G.arcs[j][i] = G.arcs[i][j] = w;//无向图是对称的
  }
}
//在图中查找顶点
int LocateVex(AMGraph &G, VertexType u)
{
  for(int i = 0; i < G.verNum; ++i)
    if(u==G.vers[i]) return i;
  return -1;  
}

2.2 邻接矩阵的优缺点

优点： 直观，简单，好理解；方便检查任意一对顶点间是否存在边；方便找任意一个顶点的所有“邻接点”，有边直接相连的顶点；方便计算任意一个顶点的“度”，从该点发出的边的数量为“出度”；指向该点的边的数量为“入度”。

缺点： 不便于增加和删除顶点；浪费空间， O(n2),n是顶点的数量，如果存稀疏图(点很多，边很少)，则会有大量无效元素；浪费时间，统计稀疏图中有多少条边。

2.3 邻接表

邻接表表示法使用链式存储的结构，顶点按照编号顺序将顶点数据存储在一维数组之中；关联同一顶点的边，用线性链表进行存储。邻接表的示意图如下所示：

邻接表是不唯一的，因为链表中的边的顺序可以互换；若无向图中有n个顶点，e条边，则其邻接表需要n个头结点和2e个表结点。适合存储稀疏图。所以邻接表的空间复杂度为： O(n+2e)；无向图中顶点  vi的度为第  i个单链表中的结点个数。

有向图的邻接表如下图所示：

有向图邻接表的空间复杂度为 O(n+e)；容易计算顶点vi的出度即为第 i个单链表中结点的个数；顶点  vi的入度即为整个单链表中邻接点域值为i−1的结点的个数，计算比较复杂。

上图是以顶点的出度建立的出度边邻接表，还可以使用顶点的入度边建立入度边邻接表，如下图所示：

容易计算顶点vi的入度即为第i个单链表中结点的个数；顶点vi的出即为整个单链表中邻接点域值为 i−1的结点的个数，计算比较复杂。

当已知一个邻接矩阵或者邻接表，可以唯一确定一个无向图/有向图。

邻接表的存储表示：

//顶点的结构
#define MVnum 100 //最大顶点数量
typedef struct VNode
{
  VerTexType data;  //顶点信息
  ArcNode *firstArc;  //指向第一条依附于该顶点的边的指针
}AdjList[MVnum];    //AdjList表示邻接表类型

//边的节点结构
typedef struct ArcNode
{
  int adjVex;   //该边指向的顶点的位置
  ArcNode *nextArc; //指向下一条边的指针
  double info;    //边的权值
};

//图的结构定义
typedef struct ALGraph
{
  AdjList vertices; //邻接表中的顶点表
  int vexNum, arcNum;//图中的顶点数和边数
};

//邻接表的构建
void CreateUDG(ALGraph &G)
{
  cin >> G.vexNum >> G.arcNum;  //输入总的顶点数和总的边数
  for(int i = 0; i < G.vexNum; ++i)
  {//构建顶点表
    cin >> G.vertices[i].data;
    G.vertices[i].firstArc = nullptr; //初始化头结点的指针域为空
  }
  for(k= 0; k <G.arcNum; ++k)
  {//构建边链表
    cin >> v1 >> v2;    //输入一条边依附的两个顶点
    int i = LocateVex(G,v1);
    int j = LocateVex(G,v2);
    ArcNode p1 = new ArcNode;//生成一个新的边结点
    p1->adjVex = j; //邻接点的序号为j
    p1->nextArc = G.vertices[i].firstArc;//头插法
    G.vertices[i].firstArc = p1;  //将新结点插入到顶点vi的头部
    //构建无向网
    ArcNode p2 = new ArcNode;//生成一个新的边结点
    p2->adjVex = i; 
    p2->nextArc = G.vertices[j].firstArc;//头插法
    G.vertices[j].firstArc = p2;  
  }
}

2.4 邻接表的优缺点

方便找到任一顶点的所有“邻接点”；

节约稀疏图的空间，需要N个头指针+2E个结点；

不方便计算某个顶点的度：对于无向图可以直接通过和头结点相连的边结点的个数获得结点的度；

但是对于有向图，只能计算节点的出度，需要构造逆邻接表来方便计算结点的入度；

不方便检查任意一对顶点之间是否存在边；

邻接矩阵常用于稠密图，邻接表常用于稀疏图

2.5 十字链表和邻接多重表

使用十字链表来存储有向图可以克服有向图求结点的度困难的问题；使用邻接多重表存储无向图可以解决无向图每条边都要存储两边的问题。

十字链表可以看做是有向图的邻接表和逆邻接表结合起来形成的一种链表。在原有向图邻接表的基础之上，给头结点增加一个指针域指向节点的第一条出度边；给边结点的增加一个指针域指向弧头相同的节点，之前边结点的指针域指向的是弧尾相同的节点；增加一个节点值域，记录边的尾节点的值。

邻接多重表中每一条边只申请一个边结点，增加几个指针域将边结点和顶点之间的关系表示出来即可。