每日一言

As a sister, and our lovable Iris, violence does not become you. — Maki Oze from Fire Force

图形结构

基本概念：

非线性结构，数据元素之间呈多对多的关系。将数据元素作为顶点，数据元素间的关系作为顶点间的连接，即由顶点集合V和一个描述顶点之间关系——边的集合VR(或E)组成。

图的定义：

Graph = (V,VR) \\ 或 \\ Graph=(V,E)

V：顶点（数据元素）的又穷非空集合
VR（或E）：弧（关系）的又穷集合

图的存储结构

顺序存储结构

数组表示法（邻接矩阵）：

建立一个顶点表，记录各个顶点信息
建立一个邻接矩阵，表示各个顶点之间的关系

无向图的邻接矩阵表示法

有向图的邻接矩阵表示法

以邻接矩阵的行作为出度边，以邻接矩阵的列作为入度边。

对于顶点 $v_i$ ：

出度 = 第I行元素之和
入度 = 第i列元素之和
度 = 出度 + 入度

网(有权图)的邻接矩阵表示法

将不相连的为止记为 $\infty$ ，相连的位置则记为他们之间的权：

N\_Edge[i][j] = \left\{ \begin{array}{ll} W_{ij} & \text{如果} \ (vi, vj) \in VR \\ \infty & \text{否则} \end{array} \right.

1734342330931

邻接矩阵的存储结构定义

//邻接矩阵
#define MAX_VERTEX_NUM 20   //最大顶点数

typedef enum{DG,DN,UDG,UDN} GraphKind;  //图的类型，有向图、有向网、无向图、无向网
typedef int VertexType;     //顶点的数据类型
typedef int VRType;         //边的数据类型
typedef struct ArcCell {
    VRType adj;             //无权图为0、1,有权图为权重

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct MGraph{      //图的数据结构
    VertexType vexs[MAX_VERTEX_NUM];    //顶点的数组
    AdjMatrix arcs;         //邻接矩阵
    int vexnm,arcnum;       //顶点和边的个数
    GraphKind kind;         //图的类型
}Mgraph;

特点

优点：容易实现图的操作

缺点：存储空间效率低 $O(n^2)$

邻接表（链式表示法）

邻接表

邻接表是一种用于表示图的数据结构，它使用一个数组，其中每个元素是一个链表，链表中的每个节点表示与该顶点相邻的顶点。

如图：

1734342827997

空间效率为： $O(n+2e)$

邻接表的链式表示法

对于每个顶点 $v_i$ 建立一个单链表，把与 $v_i$ 有关联的边的信息连接起来。对于网图，结点中还需要保存他们之间边的权值。

1734343128714

存储结构定义

//邻接表的结构定义
#define MAX_VERTEX_NUM 20   //最大顶点数
typedef enum{DG,DN,UDG,UDN} GraphKind;  //四种图的类型
typedef int VertexType;     //顶点携带信息类型

typedef struct ArcNode{     //边结点
    int adjvex;     //该边的另一个顶点
    struct ArcNode *nextarc;    //下一条边的指针
    int weight;     //该边的权重
}ArcNode;

typedef struct VNode {      //顶点结点
    VertexType data;    //顶点存储信息
    ArcNode *firstarc;  //该顶点第一条边的指针
}Vnode,     //顶点结点重命名
AdjList[MAX_VERTEX_NUM];    //定义一个顶点数组

typedef struct{     //图的结构体定义
    AdjList vertices;   //顶点数组
    int vexnum,arcnum;  //顶点数和边数
    GraphKind kind;     //图的类型
}ALGraph;

邻接矩阵与邻接表表示法的关系

联系：邻接表中每个链表对应于邻接矩阵中的一行，但是只储存有邻接的结点，链表中结点个数等于一行中非零元素的个数。
区别：
1. 对于任一确定的无向图，邻接矩阵是唯一的，但是邻接表不唯一。
2. 邻接矩阵的空间复杂度为 $O(n^2)$ ，而邻接表的空间复杂度为 $O(n+e)$
3. 邻接表空间效率高，容易寻找顶点的邻接点；
4. 邻接矩阵空间效率低，但是容易找顶点相关的边或弧；
邻接矩阵多用于稠密图；而邻接表多用于稀疏图

十字链表

十字链表表示稀疏矩阵

十字链表将每个非零元素存储为一个结点，结点由五个数据域组成：

row域：存储元素的行号
col域：存储元素的列号
v域：存储本元素的值
right域：指向同行中该元素右边的第一个元素
down域：指向同列中下方最近的第一个元素

十字链表将矩阵从行方向和列方向链接起来。

十字链表表示有向图

十字链表的定义

在十字链表中，每个顶点和边都有专门的节点来存储它们的信息。以下是结构的详细定义：

顶点节点 (Vertex Node) :

data : 存储顶点的数据。
first_in : 指向以该顶点为终点的第一条边（入边）。
first_out : 指向以该顶点为起点的第一条边（出边）。

边节点 (Edge Node) :

tailvex : 该边的起点索引。
headvex : 该边的终点索引。
headlink : 指向下一条以相同终点为终点的边（入边链表）。
taillink : 指向下一条以相同起点为起点的边（出边链表）。
info : 存储该边的权值或其他附加信息。

邻接多重表

邻接多重表表示无向图

邻接多重表的定义

邻接多重表是一种边节点共享的链表结构，用来表示无向图。每条边只存储一次，并通过两个指针同时链接到其两个关联顶点。以下是邻接多重表的核心组成部分：

1. 顶点节点 (Vertex Node) :

每个顶点由一个节点表示，包含以下字段：

data : 存储顶点的数据。
firstedge : 指向该顶点的第一条边。

2. 边节点 (Edge Node) :

每条边由一个节点表示，包含以下字段：

ivex : 该边关联的一个顶点的索引。
jvex : 该边关联的另一个顶点的索引。
ilink : 指向下一个与 ivex 关联的边。
jlink : 指向下一个与 jvex 关联的边。
info : 存储该边的权值或附加信息（可选）。

图的遍历

遍历定义：从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算，是求解图的连通性、拓扑排序和求关键路径的基础。
遍历实质：找每个顶点的邻接点的过程。
图遍历的特点：由于图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点，需要在到达曾经访问过的点时回溯，算法实现时要考虑这一点和树的遍历不同的地方。

避免遍历重复访问

设置辅助数组 visited[n] ,用来标记每个被访问过的点。

// 初始化为0
int visited[n] = {0};
//被访问后
visited[i] = 1;

深度优先搜索(DFS)

DFS 的基本思想

从图中的某个顶点出发，将该顶点标记为已访问。
依次访问与该顶点直接相连的未访问顶点，继续递归进行搜索。
如果当前顶点的所有相邻顶点都已被访问，回溯到上一个顶点。
重复上述过程，直到所有顶点都被访问。

伪代码

DFS(v):
    标记 v 为已访问
    输出 v
    对于 v 的每个相邻顶点 u:
        如果 u 未被访问:
            DFS(u)

邻接矩阵实现DFS

void DFS(int vertex) {
    visited[vertex] = true;  // 标记当前顶点为已访问
    printf("%d ", vertex);   // 输出当前顶点

    // 遍历所有顶点，访问与当前顶点相连且未访问的顶点
    for (int i = 0; i < numVertices; i++) {
        if (graph[vertex][i] != 0 && !visited[i]) {
            DFS(i);  // 递归访问
        }
    }
}

时间复杂度

时间复杂度 : $O(V^2)$ ，其中 V 是顶点数。因为邻接矩阵需要遍历每一行来查找邻接点。
空间复杂度 : $O(V^2)$ ，用于存储邻接矩阵。

示例：

1734586469967

图的邻接表进行DFS

// 深度优先搜索
void DFS(Graph* graph, int vertex) {
    graph->visited[vertex] = true;  // 标记当前顶点为已访问
    printf("%d ", vertex);          // 输出当前顶点

    Node* temp = graph->adjList[vertex];  // 遍历邻接表
    while (temp) {
        int connectedVertex = temp->vertex;
        if (!graph->visited[connectedVertex]) {
            DFS(graph, connectedVertex);  // 递归访问未访问的邻接点
        }
        temp = temp->next;
    }
}

时间复杂度

时间复杂度 : $O(V + E)$ ，其中 $V$ 是顶点数， $E$ 是边数。
空间复杂度 : $O(V + E)$ ，存储邻接表和递归调用栈。

广度（宽度）优先遍历（BFS）

BFS的基本思想

将起始顶点标记为已访问，并入队。
当队列不为空时，执行以下操作：

从队列中取出一个顶点。
遍历该顶点的所有邻接顶点，若邻接顶点未被访问：
将其标记为已访问。
将其入队。

若队列为空，算法结束。

邻接表实现BFS

// BFS 实现
void BFS(Graph* graph, int startVertex) {
    Queue* queue = createQueue();

    // 标记起始顶点并入队
    graph->visited[startVertex] = true;
    enqueue(queue, startVertex);

    while (!isEmpty(queue)) {
        int currentVertex = dequeue(queue);
        printf("%d ", currentVertex);  // 访问顶点

        // 遍历邻接顶点
        Node* temp = graph->adjLists[currentVertex];
        while (temp) {
            int adjVertex = temp->vertex;
            if (!graph->visited[adjVertex]) {
                graph->visited[adjVertex] = true;
                enqueue(queue, adjVertex);
            }
            temp = temp->next;
        }
    }
    free(queue);
}

时间复杂度

$O(V+E)$

数据结构-图_

每日一言

图形结构

图的存储结构

顺序存储结构

无向图的邻接矩阵表示法

有向图的邻接矩阵表示法

网(有权图)的邻接矩阵表示法

邻接矩阵的存储结构定义

特点

邻接表（链式表示法）

邻接表

邻接表的链式表示法

存储结构定义

邻接矩阵与邻接表表示法的关系

十字链表

十字链表表示稀疏矩阵

十字链表表示有向图

十字链表的定义

邻接多重表

邻接多重表表示无向图

邻接多重表的定义

1. 顶点节点 (Vertex Node) :

2. 边节点 (Edge Node) :

图的遍历

避免遍历重复访问

深度优先搜索(DFS)

DFS 的基本思想

伪代码

邻接矩阵实现DFS

时间复杂度

图的邻接表进行DFS

时间复杂度

广度（宽度）优先遍历（BFS）

BFS的基本思想

邻接表实现BFS

时间复杂度

数据结构-图