图（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）

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

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

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

数据结构-图

图（Graph）的基本概念

图的基本术语

图的存储方法

邻接矩阵（边多）

邻接矩阵的特点

邻接矩阵结点类型描述

define MAX_VERTEX_NUM 20

邻接表（顶点多）

邻接表的特点

邻接表结点类型描述

创建邻接表

图的遍历

深度优先搜索遍历（DFS）

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

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

广度优先搜索遍历（BFS）

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

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

热门文章

最新文章

相关课程

相关电子书