7.图的存储

图

线性表中，数据元素是一对一的关系，除了第一个和最后一个元素外，每个元素有唯一的前驱和后继。

树形结构中，数据元素是一对多的关系，除了根之外，每个结点有唯一的双亲结点，可以有多个孩子。

图形结构是多对多的关系，任何两个数据元素都有可能有关系，每个结点可以有多个前驱和后继。

图通常用一个二元组表示：$G=<V,E>$，V表示顶点集，E表示边集。$|V|$表示顶点集中元素的个数，即顶点数，也成为图G的阶，如n阶图，表示图中有n个顶点。$|E|$表示边集中元素的个数，即边数。

V和E均为有限集合，E可以为空集，V不可以为空，也就是说图至少有一个顶点

1. 无向图。图中每条边都没有方向，则称为无向图。如顶点$v_1$和$v_3$可记为$(v_1, v_3)$或$(v_2, v_1)$。

2. 有向图。图中每条边都是有方向的，则称为有向图。有向边也称为弧，每条弧都是由来嗯个顶点组成的有序对。

尖括号$<v_i, v_j>$表示有序对，圆括号$(v_i, v_j)$表示无序对

3. 即不含平行边，也不含自环的图称为简单图。含有平行边或自环的图称为多重图。

4. 无向图中，任意两点都有一条边，则该图称为无向完全图。有向图中，任意两点都有两个方向相反的两条弧，则称该图为有向完全图。

5. 有很少边或者弧的图称为稀疏图，反之则为稠密图。一般来说，若图G满足$|E|<|V|*\log{|V|}$，则称G为稀疏图。

6. 网。实际中，经常在边上标注图距离、时间等数值，该数值称为边的权值。带权值的图称为网。

7. 邻接是指顶点和顶点之间的关系，关联是指边和顶点之间的关系。

8. 顶点的度是指该顶点相关联的边的数码，记为$TD(v)$。握手定理：度数之和等于边数的两倍。即$\sum_{i=1}^nTD(v_i)=2e$。其中n为顶点数，e为边数。

9. 路径、路径长度、距离

• 路径：接续的边的顶点构成的序列。

• 路径长度：路径上边或弧的数目。

• 距离：从顶点到另一个顶点的最短路径长度。

• 子图：设两个图$G=(V,E),G_1=(V_1,E_1)$。若$V_1 \subseteq V, E_1 \subseteq E$，则称$G_1$是G的子图。从图中选择若干个顶点、若干条边构成的图称为原图的子图。

• 生成子图：从图中选择所有顶点，若干条构成的图称为原图的生成子图。

10. 连通图和连通分量

• 连通图：无向图中，如果顶点$V_1$到$V_j$都有路径，则称$V_i$和$V_j$是连通的。如果图中任何两个顶点都是连通的，则称G为连通图。
• 连通分量：无向图G的极大连通子图称为G的连通分量。极大连通子图的意思是：该子图是G连通子图，如果再加一个顶点，该子图不连通。
• 对于连通图，则其连通分量就是它自己，对于非连通图，则有两个以上连通分量。

10. 强连通图和强连通分量

• 强连通图：有向图中，如果任何两个顶点$V_1$到$V_j$都有路径，且$V_j$到$V_i$也有路径。则称G为强连通图。
• 强连通分量：有向图G的极大强连通子图称为G的强连通分量。极大连通子图的意思是：该子图是G的强连通子图，如果再加入一个顶点，该子图不再是强连通的。

邻接矩阵

1. 无向图的邻接矩阵

无向图中，如果$v_i$到$v_j$有边，则邻接矩阵$M[i][j]=M[j][i]=1$，否则$M[i][j]=0$

2. 无向图的邻接矩阵

有向图中，如果$v_i$到$v_j$有边，则邻接矩阵$M[i][j]=1$，否则$M[i][j]=0$

3. 网的邻接矩阵

如果$v_i$到$v_j$有边，$w_{ij}$为$v_i$到$v_i$的权重，则邻接矩阵$M[i][j]=w_{ij}$，否则$M[i][j]=\infty$

尖括号$<v_i, v_j>$表示有序对，圆括号$(v_i, v_j)$表示无序对

优先：

• 快速判断两顶点之间是否有边。时间复杂度为$O(1)$
• 方便计算各顶点的度。时间复杂度为$O(n)$

缺点：

• 不便于增删顶点。增删顶点需要改变邻接矩阵的大小，效率较低。

• 不便与访问所有邻接点。时间复杂度为$O(n^2)$

• 空间复杂度较高。空间复杂度为$O(n^2)$

实现

#include <stdio.h>
#include <stdlib.h>

// 无向图

// 最大顶点
#define MAXVNUM 100

// 顶点类型
typedef char VexType;
// 边上权值数据类型
typedef int EdgeType;

typedef struct AMGraph {
  VexType Vex[MAXVNUM];
  EdgeType Edge[MAXVNUM][MAXVNUM];
  // 顶点数 边数
  int vexnum, edgenum;
} AMGraph;

AMGraph* createAMGraph() {
  AMGraph *G = (AMGraph*) malloc(sizeof(AMGraph));
  // 顶点数
  G->vexnum = 3;
  // 边数
  G->edgenum = 3;
  // 存入顶点信息
  G->Vex[0] = 'A';
  G->Vex[1] = 'B';
  G->Vex[2] = 'C';
  // 初始化邻接矩阵
  for(int i = 0; i < G->vexnum; i ++) {
    for(int j = 0; j < G->vexnum; j ++) {
      G->Edge[i][j] = 0;
    }
  }
  // 边
  G->Edge[0][1] = G->Edge[1][0] = 1;
  G->Edge[1][2] = G->Edge[2][1] = 1;
  G->Edge[0][2] = G->Edge[2][0] = 1;


  return G;
}

int locatevex(AMGraph* G, VexType x) {
  for(int i = 0; i < G->vexnum; i ++) {
    if(x == G->Vex[i]) return i;
  }
  return -1;
}

void printAMGraph(AMGraph* G) {
  printf("邻接矩阵为：\n");
  /* printf("%d\t", G->vexnum); */
  for(int i = 0; i < G->vexnum; i ++) {
    for(int j = 0; j < G->vexnum; j ++) {
      printf("%d\t", G->Edge[i][j]);
    }
    printf("\n");
  }
}

int main(int argc, char *argv[])
{
  AMGraph *G = createAMGraph();
  printAMGraph(G);
  
  printf("\n查找B的下标：%d\n", locatevex(G, 'B'));
  return 0;
}

邻接表

邻接表（Adjacency List）是图的一种链式存储方式。包含顶点和邻接点。订报涵括顶点信息和指向第一个邻接点的指针，邻接点是包括邻接点的存储下标和指向下一个邻接点的指针，顶点$v_i$的所有邻接点构成一个单链表。

邻接表用到两种数据结构：

1. 顶点结点，包括顶点信息和指向第一个邻接点的指针，可用一维数组存储。
2. 邻接点结点，包括邻接点的存储下标和指向下一个邻接点的指针。顶点$v_i$的所有邻接点构成一个单链表

优点：

• 便于增删顶点
• 便于访问所有邻接点。时间复杂度为$O(n+e)$。
• 空间复杂度低。总体空间复杂度为$O(n+e)$

缺点：

• 不便于判断两点时间是否有边
• 不便于计算各顶点的度。无向图中顶点的度为顶点后单链表中的节点数。有向图的出度为顶点后面单链表的节点数，但求入度困难。有向图逆邻接表中，求入度为顶点后面单链表的节点数，但求出度困难

无向图

有向图

邻接表实现有向图

#include <stdio.h>
#include <stdlib.h>

// 有向图邻接表

// 顶点最大值
#define MAXVNUM 100

// 顶点数据类型
typedef char VexType;
typedef struct AdjNode {
  // 邻接点下标
  int v;
  // 下一个邻接点
  struct AdjNode *next;
} AdjNode;

typedef struct VexNode {
  // 顶点
  VexType data;
  // 指向第一个邻接点
  AdjNode *first;
} VexNode;

typedef struct ALGraph {
  VexNode *Vex;
  int vexnum, edgenum;
} ALGraph;

// 查找顶点的下标
int locatevex(ALGraph* G, VexType x) {
  for(int i = 0; i < G->vexnum; i ++) {
    if(x == G->Vex[i].data) return i;
  }
  return -1;
}

// 插入一条边
void insertEdge(ALGraph* G, int i, int j) {
  AdjNode *s = (AdjNode*) malloc(sizeof(AdjNode));
  s->v = j;
  s->next = G->Vex[i].first;
  G->Vex[i].first = s;
}

ALGraph* createALGraph() {
  ALGraph *G = (ALGraph*) malloc(sizeof(ALGraph));
  // 顶点和边
  G->vexnum = 3;
  G->edgenum = 3;
  G->Vex = (VexNode*) malloc(G->vexnum * sizeof(VexNode));
  G->Vex[0].data = 'A';
  G->Vex[1].data = 'B';
  G->Vex[2].data = 'C';
  G->Vex[0].first = NULL;
  G->Vex[1].first = NULL;
  G->Vex[2].first = NULL;
  insertEdge(G, locatevex(G, 'A'), locatevex(G, 'B'));
  insertEdge(G, locatevex(G, 'B'), locatevex(G, 'C'));
  insertEdge(G, locatevex(G, 'C'), locatevex(G, 'A'));

  return G;
}

void printALGraph(ALGraph* G) {
  printf("邻接矩阵为：\n");
  /* printf("%d\t", G->vexnum); */
  for(int i = 0; i < G->vexnum; i ++) {
    AdjNode *t = G->Vex[i].first;
    printf("%c: ", G->Vex[i].data);
    while(t != NULL) {
      printf(" [%d] ", t->v);
      t = t->next;
    }
    printf("\n");
  }
}

int main(int argc, char *argv[])
{
  ALGraph *G = createALGraph();
  printALGraph(G);
  return 0;
}