图

图的结构定义

图是由一个顶点集V和一个边集S组成的数据结构。 其中，V是顶点的集合，S是边的集合。

图的边有两种：

  • 有向边：有向边是指从一个顶点指向另一个顶点的边。
    • 有向图：有向图是指图中的边都是有向边的图。
  • 无向边：无向边是指两个顶点之间没有方向的边。
    • 无向图：无向图是指图中的边都是无向边的图。

Graph = (V, S) 而 R={VR}

度：和顶点v相关联的边的数目。

对于有向图来说，由于弧是有方向的，所以有入度和出度的概念：
入度：以顶点v为终点的边的数目。
出度：以顶点v为起点的边的数目。

路径

在图论中，路径是指连接图中两个或多个顶点的一系列边的序列。 更正式地说，从顶点 u 到顶点 v 的路径是一个顶点序列：

P = (v1, v2, …, vk)

其中：

v1 = u （路径的起点是 u） vk = v （路径的终点是 v） 对于所有的 i (1 <= i < k)，顶点 vi 和 vi+1 之间都存在一条边。 路径的长度

路径的长度是指路径中边的数量。 在上面的例子中，路径 P 的长度是 k - 1。

路径的类型

根据路径中是否允许重复顶点和边，可以将路径分为以下几种类型：

  • 简单路径 (Simple Path)：

路径中的所有顶点都是不同的，即没有重复的顶点。
因此，简单路径中也不会有重复的边。
例如： A -> B -> C (A, B, C 各不相同)

  • 非简单路径 (Non-Simple Path)：

路径中可以包含重复的顶点和边。
例如： A -> B -> C -> B (B 重复出现)

  • 环 (Cycle)：

是一种特殊的路径，它的起点和终点是同一个顶点。
例如： A -> B -> C -> A

  • 简单环 (Simple Cycle)：

除了起点和终点相同外，环中的所有其他顶点都是不同的。
例如： A -> B -> C -> A (A, B, C 各不相同)

如果图中任意两个顶点之间都存在路径，则该图被称为连通图。 也就是说，从任何一个顶点出发，都可以到达图中的任何其他顶点

图的存储

邻接矩阵

无向图

邻接矩阵是一种表示图的方法，它使用一个二维数组来表示图中顶点之间的连接关系。

在邻接矩阵中，数组的行和列分别表示图中的顶点，而数组元素的值则表示两个顶点之间是否有边。

如果两个顶点之间有边，则数组元素的值为 1；否则，数组元素的值为 0。

数学表示为:

$$ M_{ij} = \begin{cases} 1, & \text{如果顶点 i 和顶点 j 之间有边} \ 0, & \text{否则} \end{cases}\ A = \begin{bmatrix} 0 & 1 & 0 \ 1 & 0 & 1 \ 0 & 1 & 0 \end{bmatrix} $$

矩阵的主对角线始终为0，因为一个顶点不可能与自己相邻。

邻接矩阵的转置矩阵和邻接矩阵始终相同，也就意味着矩阵中1的个数始终是偶数且为图中边的两倍。

有向图

如果顶点 i 和顶点 j 之间存在一条从 i 到 j 的边，那么 $adjacency_matrix[i][j] = 1$。

但是，即使 adjacency_matrix[i][j] = 1，也不能保证 $adjacency_matrix[j][i] = 1$，除非也存在一条从 j 到 i 的边。

因此，有向图的邻接矩阵通常是不对称的。

例题

有n个城市，其中一些城市彼此连接，有的城市之间没有直接的连接。

给定一个二维数组 isConnected，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

省份是一组直接或间接相连的城市，而组内不含其他没有相连的城市。

返回矩阵中省份的数量。

  • 思路：

    1. 遍历矩阵，找到与当前城市直接相连的城市。
    2. 标记这些城市为已访问。（为了避免重复访问，我们可以使用一个数组来记录每个城市是否已被访问。把数组中的1改为0）
    3. 继续遍历，直到所有城市都被访问。
void DFs(int n, int row){
    int j;
    visited[row] = 1;
    for(j = 0; j < n; j++){
        if(isConnected[row][j] == 1 && !visited[j]){
            isConnected[row][j] = 0;
            isConnected[j][row] = 0;// 标记已访问
            DFS(n, j);// 递归遍历
        }
    }
}

int CountNum(int n){
    int i;
    int count = 0;
    for (i = 0; i < n; i++){
        if(!visited[i]){
            DFS(n, i);
            count++;
        }
    }
    return count;
}

int main(){
   int n;
   scanf("%d", &n);
   int isConnected[n][n];
   int i, j; 
   for (i = 0; i < n; i++){
    for (j = 0; j < n; j++){
        scanf("%d", &isConnected[i][j]);
    } 
   }
   int count = CountNum(n);
   printf("%d", count);
   return 0;
}

邻接表(不常用)

邻接表是一种表示图的方法，它使用一个数组和链表来表示图中顶点之间的连接关系。

在邻接表中，数组的每个元素表示一个顶点，而链表则表示与该顶点相邻的其他顶点。

例如，如果顶点 A 与顶点 B 和顶点 C 相邻，则在邻接表中，A 的链表中就会包含 B 和 C。

基本思想： 为图中的每个顶点创建一个链表。 每个链表存储与该顶点相邻的所有顶点。

具体实现：

可以使用数组来存储顶点，数组的每个元素指向一个链表，该链表存储与该顶点相邻的所有顶点。 链表可以使用单链表来实现。

链式前向星

链式前向星主要由两个数组和一个结构体组成。

head[]: 表示以i为起点的第一条边的编号 edge[]: 表示所有边的信息 cnt: 表示边的数量

结构体：

struct edge{ int w; // 表示边的权值 int to; // 表示边的终点 int next; // 表示与起点相同的下一条边的编号 }edge[maxn]; // 表示边的信息

struct edge{
    int w; // 表示边的权值
    int to; // 表示边的终点
    int next; // 表示与起点相同的下一条边的编号 
}edge[maxn]; // 表示边的信息

int head[maxn]; // 表示以i为起点的第一条边的编号
int cnt=0; // 表示边的数量

void add(int from, int to, int w){
    edge[cnt].w = w; // 表示边的权值
    edge[cnt].to = to; // 表示边的终点
    edge[cnt].next = head[from]; // 表示与起点相同的下一条边的编号
    head[from] = cnt++; // 表示以i为起点的第一条边的编号
}

适用于稀疏图。

当链式前向星用于存储无向图时，每条边会被存储两次，一次是从起点到终点，一次是从终点到起点。

链式前向星的基本思想是：

  1. 为图中的每个顶点创建一个链表。
  2. 每个链表存储与该顶点相邻的所有顶点。
  3. 链表中的每个节点存储与该顶点相邻的顶点的编号。

链式前向星的优点是：

  1. 链式前向星的空间复杂度比邻接表低。
  2. 链式前向星的时间复杂度比邻接表低。
  3. 链式前向星的实现比邻接表简单。

十字链表

十字链表是一种表示图的方法，它使用一个数组和链表来表示图中顶点之间的连接关系。

在十字链表中，数组的每个元素表示一个顶点，而链表则表示与该顶点相邻的其他顶点。

图的搜索算法

深度优先搜索

深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索树或图的算法。

连通图的遍历

从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。

如果此时图中尚有顶点未被访问，则另选一个未曾被访问过的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。

  • 从深度优先搜索遍历图的过程类似于树的先序遍历。
  • 为了判别已访问的顶点，可设置一个访问标志数组visited[n]，其初值为FALSE（未访问）。
void DFS(Graph G, int v){
    visited[v] = TRUE;
    //do what u want here
    for(w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)){
        if(!visited[w]){
            DFS(G, w);
        }
    }
}

非连通图的遍历

对于非连通图，需要对每个连通分量分别进行遍历。

广度优先搜索

广度优先搜索（Breadth-First Search，BFS）是一种用于遍历或搜索树或图的算法。

BFS是按照路径的长度递增的次序来访问顶点的。

过程：

  1. 首先访问起始顶点v；
  2. 接着由v出发，依次访问v的各个未访问过的邻接点；
  3. 然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。

为了保证访问的顺序，在BFS中会使用队列来存储顶点。

（但是广度优先的题都可以使用深度优先算法解，并且还不用使用队列，所以BFS采用的比较少）