图（Graph）的基本概念

图（Graph）是一种比线性表和树更为复杂的非线性（多对多）数据结构。图中元素的关系是任意的，每个元素（也称为顶点）具有多个直接前驱和后继，所以图可以表达数据元素之间广泛存在着的更加复杂的关系。

图（Graph）：图$G$由顶点集$V(G)$和边集$E(G)$组成，形式上记为$G = (V, E)$。其中，$V(G)$是顶点（Vertex）的非空有限集合；$E(G)$是$V(G)$中任意两个顶点之间的关系集合，又称为边（Edge）的有限集合。

图的基本术语

有向图：当图G中的每条边有方向时，则称G为有向图。
- 有向边（弧） 有向边通常用两个顶点组成的有序对来表示，又称为弧
  - 弧尾：弧的起始结点称为弧尾
  - 弧头：弧的终止结点称为弧头
- 一个有向图，其顶点数$v$和边数$e$满足$0 \le e \le v(v - 1)$
- 完全有向图：如果$e = v(v - 1)$时，则称该有向图为完全有向图
无向图：图G中每条边是无方向的，称为无向图。无向图的两个顶点之间最多只存在一条边。
- 一个无向图，其顶点数$v$和边数$e$满足$0 \le e \le \frac{v(v - 1)}{2}$
- 完全无向图：如果$e = \frac{v(v - 1)}{2}$时，则称该无向图为完全无向图
稀疏图与稠密图：若图G的顶点与边的关系满足$e < vlog_2v$，则该图为稀疏图，否则为稠密图。
顶点的度（degree）：顶点的度是指依附于某顶点v的边数，通常记作$TD(v)$
- 入度：顶点v的入度是指以顶点为终点的弧的数目，记作$ID(v)$
- 出度：顶点v的出度是指以顶点为起点的弧的数目，记作$OD(v)$
- $TD(v) = ID(v) + OD(v)$
边的权、网图：
- 权（weight）：与边有关的数据信息称为权，在实际应用中，权值可以有某种含义。
- 网图或网络（network）：边上带权的图称为网图或网络。
- 有向带权图：如果边是有方向的带权图，称为有向带权图。
路径（path）：若从顶点$v_1$出发，沿着一些边经过顶点$v_1, v_2, \cdots, v_{n - 1}$到达顶点$v_n$，则称顶点序列$(v_1, v_2, \cdots, v_{n - 1}, v_n)$为从$v_1$到$v_n$的一条路径。
路径长度：沿路径经过的边数称为该路径的长度。
简单路径：若路径中的顶点不重复出现，则称这条路径为简单路径。
简单回路（简单环）：起点和终点相同并且路径长度不小于2的简单路径，被称为简单路径或简单环。
有根图：在一个有向图中，若存在一个顶点v，从该顶点可到达图中其他所有的顶点，则称这个有向图为有根图，v称为该图的根。
子图：对于图$G = (V, E), G' = (V', E')$，若存在$V' \in V, E' \in E$，则称图$G'$是图$G$的一个子图。
连通：
- 无向图：
  - 连通：在无向图G中，如果顶点$v_i$和$v_j(i \ne j)$存在路径，则称$v_i$和$v_j$是连通的
  - 连通图：如果V(G)中任意两个顶点都连通，则称G为连通图，否则为非连通图。
  - 连通分量：无向图G中的极大连通子图称为连通分量。对任何连通图而言，连通分量就是其自身；非连通图可有多个连通分量。
- 有向图：
  - 强连通：在有向图G中，如果顶点$v_i$和$v_j(i \ne j)$存在路径，则称$v_i$和$v_j$是强连通的
  - 强连通图：如果V(G)中任意两个顶点都强连通，则称G为强连通图，否则为非连通图。
  - 强连通分量：有向图G中的极大强连通子图称为强连通分量。
    图的存储方法
    
    邻接矩阵（边多）
    邻接矩阵是指用一个一维数组存储图中的顶点信息，用一个二维数组存储图中的边信息（即各顶点之间的邻接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵。
    结点数为n的图$G = (V, E)$的邻接矩阵$A$是$n \times n$的。将G的顶点编号为$v_1, v_2, \cdots, v_n$。若$(v_i, v_j) \in E$，则$A[i][j] = 1$，否则$A[i][j] = 0$
    $$ \begin{equation} A[i][j] = \left\{ \begin{array}{rr} 1 & 若(v_i, v_j)或 \in E(G) \\ 0 & 若(v_i, v_j)或 \notin E(G) \end{array} \right. \end{equation} $$
    对于带权图，若顶点$v_i$和$v_j$之间有边相连，则邻接矩阵中对应项存放着该边对应的权值，对于不相连的顶点，则用$\infty$代表两个顶点之间不存在边。
    $$ \begin{equation} A[i][j] = \left\{ \begin{array}{rr} w_{ij} & 若(v_i, v_j)或 \in E(G) \\ 0或\infty & 若(v_i, v_j)或 \notin E(G) \end{array} \right. \end{equation} $$
    
    上图的两个图对应的邻接矩阵分别为：
    $$ A_1 = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix}, A_2 = \begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{bmatrix} $$
    邻接矩阵的特点
    根据图的邻接矩阵的存储方法，易知图有以下特点：
无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放无向图邻接矩阵时只需考虑存放上（下）三角矩阵的元素即可。
对于无向图，邻接矩阵第$i$行（或第$i$列）非零元素（或非$\infty$元素）的个数正好是第$i$个顶点的度$TD(v_i)$
对于有向图，邻接矩阵第$i$行（或第$i$列）非零元素（或非$\infty$元素）的个数正好是第$i$个顶点的出度$OD(v_i)$（或入度$ID(v_i)$）
用邻接矩阵方式存储图，很容易确定图中任意两个元素之间是否相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的实际代价较大。
邻接矩阵结点类型描述
```C
// 最大顶多数
define MAX_VERTEX_NUM 20

// VertexType：顶点类型，EdgeType：边类型
typedef char VertexType;
typedef int EdgeType;

typedef struct {
VertexType vertex[MAX_VERTEX_NUM];
EdgeType edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
} MatrixGraph;

### 创建邻接矩阵
```C
/**
 * 创建无向图的邻接矩阵
 * @param graph 
 * @param edgesNum 无向图边的个数
 */
void CreateUndirectedMatrixGraph(MatrixGraph *graph, int edgesNum) {
    int i, j;
    float weight;
    // 读入无向图顶点信息
    for (i = 0; i < MAX_VERTEX_NUM; ++i) {
        printf("Please enter the %dth vertex information:", i + 1);
        graph->vertex[i] = getchar();
        printf("\n");
        // 邻接矩阵初始化
        for (j = 0; j < MAX_VERTEX_NUM; ++j) {
            graph->edges[i][j] = 0;
        }
    }
    // 读入边的权值信息
    for (int k = 0; k < MAX_VERTEX_NUM; ++k) {
        printf("Please enter the weight information "
               "of vertices I to j (starting from subscript 0, "
               "enter i, j, weight, separated by Spaces):");
        scanf("%d %d %f", &i, &j, &weight);
        printf("\n");
        graph->edges[i][j] = weight;
        graph->edges[j][i] = weight;
    }
}

上述算法的时间复杂度为$O(n + n^2 + 3)$，通常情况下$e \ll n^2$，所以该算法的时间复杂度为$O(n^2)$

邻接表（顶点多）

邻接表存储方法是一种顺序存储与链式存储相结合的存储方法。在这种方法中，只考虑非零元素。所以当图中的顶点很多而边很少时，可以有效的节省存储空间。

邻接表存储结构由顶点表和邻接链表两部分组成。
对于每个顶点$v_i$，使用一个具有两个域的结构体数组来存储，这个数组称为顶点表。其中，一个域称为顶点域（Vertex），用来存放顶点本身的数据信息；另一个域称为指针域，用来存放依附于该顶点的边所组成的单链表的表头结点的存储位置。
邻接于$v_i$的顶点$v_j$链接成的单链表称为$v_i$的邻接链表。邻接链表中每个结点由两个域构成，一个是邻接点域（Adjvex），用来存放与$v_i$相邻接的顶点$v_j$的序号$j$（可以是顶点$v_j$在顶点表中所占数组单元的下标）；二是链域（Next），用来将邻接链表中的结点链接在一起。

对于无向图，$v_i$的每个结点都对应与$v_i$相关联的一条边，所以无向图的邻接链表又称为边表；对于有向图，$v_i$的邻接链表中每个结点都对应于以$v_i$为起点射出去的一条边，所以有向图的邻接链表又称为出边表。
邻接表结点
无向图和有向图的示例分别如下图所示：
无向图邻接表表示法
有向图邻接表表示法

邻接表的特点

若G为无向图，则需存储空间为$O(|V| + 2|E|)$；若G为有向图，则需存储空间为$O(|V| + |E|)$。前者的倍数2是因为在无向图中，每条边在邻接表中出现了两次。
对于稀疏图，采用邻接表表示有利于节省存储空间。
在邻接表中，给定一顶点，很容易找出它的所有邻边，只需要扫描一遍它的邻接表，花费时间为$O(n)$。但是，要确定两个顶点之间是否有邻边，在邻接矩阵中可以在常数时间内查找到，在邻接表中，需要扫描一遍邻接表查找对应结点。
邻接表结点类型描述
邻接链表：
```
// 邻接链表
typedef struct Node{
  // 邻接点域：该弧指向的顶点的位置
  int adjvex;
  // 链域：指向下一条弧指针
  struct Node* next;
} AdjacencyNode;
```
顶点表：
```
// 顶点表
typedef struct {
  // 顶点域：顶点结点信息
  VertexType vertex;
  // 邻接链表：指向第一条依附于该顶点的弧的指针
  AdjacencyNode *first;
} VertexNode;
```
创建邻接表
```
/**
* 创建无向图的邻接表
* @param graph 
* @param vertexNum 
* @param edgeNum 
*/
void CreateUndirectedAdjacencyGraph(VertexNode graph[], int vertexNum, int edgeNum) {
  int i, j;
  AdjacencyNode *s;
  // 顶点表初始化
  for (i = 0; i < vertexNum; ++i) {
      printf("Please enter the %dth vertex information:", i + 1);
      graph[i].vertex = getchar();
      graph[i].first = NULL;
      printf("\n");
  }
  // 建立边表
  for (int k = 0; k < edgeNum; ++k) {
      printf("Please enter the values of vertices I to j "
             "(starting with subscript 0, enter I, j, separated by Spaces):");
      scanf("%d %d", &i, &j);
      // 建立i到j的邻接表信息
      s = (AdjacencyNode *) malloc(sizeof(AdjacencyNode));
      s->adjvex = j;
      s->next = graph[i].first;
      graph[i].first = s;
      // 邻接表无向图是对称的，建立从j到i的邻接表信息
      s = (AdjacencyNode *) malloc(sizeof(AdjacencyNode));
      s->adjvex = i;
      s->next = graph[j].first;
      graph[j].first = s;
      printf("\n");
  }
}
```
上述算法的时间复杂度为：$O(n + e)$
图的遍历
图在遍历过程中，任意一个结点都有可能与其他顶点相邻接，所以为了避免对同一顶点的重复访问，需要使用一个辅助数组$visited[n]$（$n$为顶点数）来对顶点进行标识，如果顶点$i$被访问，则$visited[i]$置1，否则保持0。
深度优先搜索遍历（DFS）
图的深度优先搜索遍历（DFS）类似于树的先序遍历，是树先序遍历的推广。
图的深度优先搜索遍历过程是：从图中某一顶点$v_I$出发，访问此结点，并进行标记；然后依次搜索$v_i$的每个邻接点$v_j$，若$v_j$未被访问过，则对$v_j$进行访问和标记；然后依次搜索$v_j$的每个邻接点，若$v_j$的邻接点未被访问过，则访问$v_j$的邻接点，并进行标记；$\cdots$直到图中和$v_i$的所有都被访问为止。若在非连通的情况下，图中还有另一顶点未被访问，则另选图中的另一个未被访问的结点作为出发点，重复上述过程，直到图中所有结点都被访问为止。
深度优先遍历得到的顶点序列称为该图的深度优先搜索遍历序列，又称为DFS序列。
邻接矩阵的深度优先搜索遍历算法
对于邻接矩阵的DFS序列，若确定其出发点，邻接点的序号按次序排序进行选择，则邻接矩阵作为存储结构得到的DFS序列是唯一的。
```C
/**
- 邻接矩阵的深度优先搜索具体算法
- @param graph 邻接矩阵
- @param v 顶点在邻接矩阵顶点信息表中的数组下标值
- @param visited 访问标记数组
  */
  void _DFS(MatrixGraph graph, int v, int visited[]) {
  // 访问出发点
  printf("%c ", graph.vertex[v]);
  // 标记已访问的出发点
  visited[v] = 1;
  // 搜索v的邻接点
  for (int j = 0; j < MAX_VERTEX_NUM; ++j) {
```
// 当邻接点vj未被访问，从vj开始进行新一轮的深度优先搜索
if ((0 != graph.edges[v][j]) && (0 == visited[j])) {
    _DFS(graph, j, visited);
}
```
  }
  }

/**

深度优先搜索包装算法，保证非连通图也能完全访问
@param graph
@param v
*/
void DFS(MatrixGraph graph, int v) {
int visited[MAX_VERTEX_NUM];
for (int i = 0; i < MAX_VERTEX_NUM; ++i) {
```
 visited[i] = 0;
```
}
// 从0开始遍历，保证所有结点都能被访问到
for (int i = 0; i < MAX_VERTEX_NUM; ++i) {
```
 if (0 != visited[i]) {
     _DFS(graph, v, visited);
 }
```
}
}
```
上述算法的时间复杂度为：$O(n^2)$，空间复杂度为：$O(n)$
邻接表的深度优先搜索遍历算法
邻接表的DFS序列不唯一，具体取决于邻接表中边表结点的链接次序
```C
/**
邻接表的深度优先搜索具体算法
@param graph 邻接表
@param v 顶点在邻接表顶点信息表中的数组下标值
@param visited 访问标记数组
/
void _DFS(VertexNode graph[], int v, int visited[]) {
AdjacencyNode p;
// 访问出发点
printf("%c ", graph[v].vertex);
// 标记已访问的出发点
visited[v] = 1;
p = graph[v].first;
// 搜索v的邻接点
while (NULL != p) {
```
 if (0 == visited[p->adjvex]) {
     _DFS(graph, p->adjvex, visited);
 }
 p = p->next;
```
}
}

/**

深度优先搜索包装算法，保证非连通图也能完全访问
@param graph
@param v
*/
void DFS(VertexNode graph[], int v) {
int visited[MAX_VERTEX_NUM];
for (int i = 0; i < MAX_VERTEX_NUM; ++i) {
```
 visited[i] = 0;
```
}
// 从0开始遍历，保证所有结点都能被访问到
for (int i = 0; i < MAX_VERTEX_NUM; ++i) {
```
 if (0 != visited[i]) {
     _DFS(graph, v, visited);
 }
```
}
}
```
上述算法的时间复杂度为：$O(2e + n)$，空间复杂度为：$O(n)$
广度优先搜索遍历（BFS）
图的广度优先搜索遍历（BFS）类似于树的层次遍历。
图的广度优先搜索遍历过程是：从图中某一结点$v_i$出发，访问$v_i$；然后依次访问$v_i$的邻接点$v_j$；在所有$v_j$都被访问后，再依次访问$v_j$的邻接点$v_k$，$\cdots$直到图中所有和$v_i$路径连通的顶点都被访问为止。若在非连通的情况下，图中还有另一顶点未被访问，则另选图中的另一个未被访问的结点作为出发点，重复上述过程，直到图中所有结点都被访问为止。
在图的广度优先搜索遍历过程中，先被访问的顶点，其邻接点也先被访问，具有先进先出的特性，所以可以使用一个队列来保存已访问过的顶点。
邻接矩阵的广度优先搜索遍历算法
对于邻接矩阵的BFS序列，若确定其出发点，邻接点的序号按次序排序进行选择，则邻接矩阵作为存储结构得到的DFS序列是唯一的。
```C
/**
零件矩阵的广度优先搜索具体算法
@param graph 邻接矩阵
@param v 顶点在邻接矩阵顶点信息表中的数组下标值
@param visited 访问标记数组
*/
void _BFS(MatrixGraph graph, int v, int visited[]) {
DataType data;
// 辅助队列
SequeenQueue queue;
// 队列初始化
InitQueue(&queue);
// 访问出发点
printf("%c ", graph.vertex[v]);
// 标记出发点
visited[v] = 1;
// 已访问结点入队
EnQueue(&queue, v);
while (!IsQueueEmpty(&queue)) {
```
 // 队头元素出队
 DeQueue(&queue, &data);
 // 访问其邻接点
 for (int j = 0; j < MAX_VERTEX_NUM; ++j) {
     if ((0 != graph.edges[data][j]) && (0 == visited[j])) {
         printf("%c ", graph.vertex[j]);
         visited[j] = 1;
         EnQueue(&queue, j);
     }
 }
```
}
}

/**

广度优先搜索包装算法，保证非连通图也能完全访问
@param graph
@param v
*/
void BFS(MatrixGraph graph, int v) {
int visited[MAX_VERTEX_NUM];
for (int i = 0; i < MAX_VERTEX_NUM; ++i) {
```
 visited[i] = 0;
```
}
// 从0开始遍历，保证所有结点都能被访问到
for (int i = 0; i < MAX_VERTEX_NUM; ++i) {
```
 if (0 != visited[i]) {
     _BFS(graph, v, visited);
 }
```
}
}
```
上述算法的时间复杂度为：$O(n^2)$，空间复杂度为：$O(n)$
邻接表的广度优先搜索遍历算法
邻接表的BFS序列不唯一，具体取决于邻接表中边表结点的链接次序
```C
/**
邻接表的广度优先搜索具体算法
@param graph 邻接表
@param v 顶点在邻接表顶点信息表中的数组下标值
@param visited 访问标记数组
/
void _BFS(VertexNode graph[], int v, int visited[]) {
AdjacencyNode p;
DataType data;
// 辅助队列
SequeenQueue queue;
// 队列初始化
InitQueue(&queue);
// 访问出发点
printf("%c ", graph[v].vertex);
// 标记出发点
visited[v] = 1;
// 已访问结点入队
EnQueue(&queue, v);
while (!IsQueueEmpty(&queue)) {
```
 // 队头元素出队
 DeQueue(&queue, &data);
 // 依次访问其邻接链表
 p = graph[data].first;
 while (NULL != p) {
     if (0 == visited[p->adjvex]) {
         printf("%c ", graph[v].vertex);
         visited[p->adjvex] = 1;
         EnQueue(&queue, p->adjvex);
     }
     p = p->next;
 }
```
}
}

/**

广度优先搜索包装算法，保证非连通图也能完全访问
@param graph
@param v
*/
void BFS(VertexNode graph[], int v) {
int visited[MAX_VERTEX_NUM];
for (int i = 0; i < MAX_VERTEX_NUM; ++i) {
```
 visited[i] = 0;
```
}
// 从0开始遍历，保证所有结点都能被访问到
for (int i = 0; i < MAX_VERTEX_NUM; ++i) {
```
 if (0 != visited[i]) {
     _DFS(graph, v, visited);
 }
```
}
}
```
上述算法的时间复杂度为：$O(2e + n)$，空间复杂度为：$O(n)$

数据结构-图

图（Graph）的基本概念

图的基本术语

图的存储方法

邻接矩阵（边多）

邻接矩阵的特点

邻接矩阵结点类型描述

define MAX_VERTEX_NUM 20

邻接表（顶点多）

邻接表的特点

邻接表结点类型描述

创建邻接表

图的遍历

深度优先搜索遍历（DFS）

邻接矩阵的深度优先搜索遍历算法

邻接表的深度优先搜索遍历算法

广度优先搜索遍历（BFS）

邻接矩阵的广度优先搜索遍历算法

邻接表的广度优先搜索遍历算法

热门文章

最新文章

相关课程

相关电子书