基础数据结构【c语言版】之 “图” 详细讲述

🕗 发布于 2024-11-11 23:04 数据结构 c语言 算法 c++ 链表

1. 图的定义和术语

1.1 图的定义

**图（Graph）**是由顶点（Vertex）和边（Edge）组成的一个集合，可以表示顶点之间的关系。通常，图可以表示为 G=(V,E)G = (V, E)G=(V,E)，其中：

VVV 是顶点集合，表示图中的所有顶点。
EEE 是边集合，表示图中顶点之间的连接关系。

图的类型：：：

根据边的不同特性，图可以分为以下几种常见类型：

无向图（Undirected Graph）：边没有方向，连接两个顶点的边可以双向访问。例如，表示朋友关系的社交网络图通常为无向图。
有向图（Directed Graph）：边具有方向，从一个顶点指向另一个顶点。通常用箭头表示边的方向，例如，表示课程的先修关系图。
带权图（Weighted Graph）：每条边上都有一个权重（Weight），表示从一个顶点到另一个顶点的“代价”，如距离、时间或费用。例如，道路图中可以用权重表示每条道路的长度。

1.2 图的术语

在学习图结构时，我们需要掌握一些常用的术语，以便更好地理解图的概念。

顶点（Vertex）：图中的基本单位，每个顶点用来表示一个对象，通常记为 VVV 或者用 V1,V2,…,VnV_1, V_2, \dots, V_nV1,V2,…,Vn 来表示多个顶点。
边（Edge）：顶点与顶点之间的连接，用来表示对象之间的关系，通常记为 EEE。在无向图中，边用无序对 (Vi,Vj)(V_i, V_j)(Vi,Vj) 表示，而在有向图中，边用有序对 (Vi,Vj)(V_i, V_j)(Vi,Vj) 表示，其中边的方向从 ViV_iVi 指向 VjV_jVj。
度（Degree）：
- 无向图的度：在无向图中，顶点的度是连接该顶点的边的数量。例如，一个度为3的顶点表示有3条边连接到该顶点。
- 有向图的入度和出度：在有向图中，入度（In-degree）表示指向该顶点的边数，出度（Out-degree）表示从该顶点出发的边数。
路径（Path）：从一个顶点到另一个顶点所经过的顶点序列。路径的长度是路径上边的数目。
- 简单路径：不包含重复顶点的路径。
- 回路（Cycle）：起点和终点相同的路径称为回路。
连通图（Connected Graph）：在无向图中，如果任意两个顶点之间都存在路径，则称该图为连通图。否则称为非连通图。
强连通图（Strongly Connected Graph）：在有向图中，如果任意两个顶点之间都存在路径（即双向可达），则称该图为强连通图。
稀疏图（Sparse Graph）和稠密图（Dense Graph）：
- 稀疏图：边数远小于顶点数的平方，常常用邻接表表示。
- 稠密图：边数接近顶点数的平方，常常用邻接矩阵表示。

1.3 C语言中的图表示

在C语言中，我们通常使用邻接矩阵或邻接表来存储图。以下是用邻接矩阵表示无向图的简单示例代码：

#include <stdio.h>

#define MAX_VERTICES 5  // 假设顶点数量最大为5

void initializeGraph(int graph[MAX_VERTICES][MAX_VERTICES]) {
    for (int i = 0; i < MAX_VERTICES; i++) {
        for (int j = 0; j < MAX_VERTICES; j++) {
            graph[i][j] = 0;  // 初始化图中所有边为0（即无连接）
        }
    }
}

void addEdge(int graph[MAX_VERTICES][MAX_VERTICES], int u, int v) {
    graph[u][v] = 1;
    graph[v][u] = 1;  // 无向图，边(u, v) 和 (v, u) 都需设置为1
}

void printGraph(int graph[MAX_VERTICES][MAX_VERTICES]) {
    for (int i = 0; i < MAX_VERTICES; i++) {
        for (int j = 0; j < MAX_VERTICES; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int graph[MAX_VERTICES][MAX_VERTICES];
    initializeGraph(graph);

    // 添加边
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    printf("图的邻接矩阵表示：\n");
    printGraph(graph);

    return 0;
}

initializeGraph：初始化邻接矩阵，将所有元素设为0，表示无边。
addEdge：在无向图中添加边。由于是无向图，边(u,v)(u, v)(u,v) 和 (v,u)(v, u)(v,u) 都设置为1。
printGraph：输出邻接矩阵，方便观察图的结构。

运行上述代码会输出邻接矩阵，通过该矩阵可以查看每个顶点之间是否有边连接。

2. 图的存储结构

图的存储结构影响图的操作效率和存储空间。具体的存储结构包括：

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

邻接矩阵是一种顺序存储结构，使用二维数组来表示顶点之间的连接关系。适合用于稠密图（边数接近于顶点数平方）。

定义：假设图有 VVV 个顶点，用一个 V×VV \times VV×V 的二维数组 graph 表示图的邻接矩阵。
有向图：若存在从顶点 iii 到顶点 jjj 的边，则 graph[i][j] = 1。
无向图：如果 iii 和 jjj 之间有边，则 graph[i][j] = graph[j][i] = 1。
加权图：若有边权重，则使用权重值代替 1。

#include <stdio.h>

#define MAX_VERTICES 4

void printGraph(int graph[MAX_VERTICES][MAX_VERTICES]) {
    for (int i = 0; i < MAX_VERTICES; i++) {
        for (int j = 0; j < MAX_VERTICES; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int graph[MAX_VERTICES][MAX_VERTICES] = { {0, 1, 0, 0}, {1, 0, 1, 1}, {0, 1, 0, 1}, {0, 1, 1, 0} };
    printf("邻接矩阵表示的图：\n");
    printGraph(graph);
    return 0;
}

2.2 邻接表

邻接表使用链表来存储顶点的邻接关系，适合用于稀疏图（边数较少）。

定义：用数组 graph 存储每个顶点的邻接链表。graph[i] 指向顶点 iii 的链表，链表中包含所有与顶点 iii 相连的顶点。
优点：节省空间，适合边较少的图。

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

#define MAX_VERTICES 4

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* createNode(int vertex) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = vertex;
    newNode->next = NULL;
    return newNode;
}

void addEdge(Node* graph[], int u, int v) {
    Node* newNode = createNode(v);
    newNode->next = graph[u];
    graph[u] = newNode;

    newNode = createNode(u);
    newNode->next = graph[v];
    graph[v] = newNode;
}

void printGraph(Node* graph[]) {
    for (int i = 0; i < MAX_VERTICES; i++) {
        Node* temp = graph[i];
        printf("顶点 %d:", i);
        while (temp) {
            printf(" -> %d", temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }
}

int main() {
    Node* graph[MAX_VERTICES] = {NULL};
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);

    printf("邻接表表示的图：\n");
    printGraph(graph);
    return 0;
}

2.3 十字链表

十字链表是一种用于存储有向图的结构，每条边包含指向起点和终点的两个指针，适合于表示入度和出度。

定义：每个顶点包含两个链表，一个存储出边，一个存储入边。
适用场景：用于需要频繁操作边的有向图。

typedef struct ArcNode {
    int tailvex, headvex;
    struct ArcNode *hlink, *tlink;
} ArcNode;

typedef struct VNode {
    int data;
    ArcNode *firstin, *firstout;
} VNode;

VNode graph[MAX_VERTICES];

2.4 邻接多重表

邻接多重表适合用于存储无向图，特别是在边的操作频繁时。每条边的节点结构包括两个顶点及其各自的相邻边指针。

定义：每条边包含两个指针，分别指向两个顶点的邻接表节点。
适用场景：用于表示无向图的连通性。

typedef struct EdgeNode {
    int ivex, jvex;
    struct EdgeNode *ilink, *jlink;
} EdgeNode;

typedef struct VertexNode {
    int data;
    EdgeNode *firstedge;
} VertexNode;

VertexNode graph[MAX_VERTICES];

3. 图的遍历

图的遍历是指从一个顶点出发，沿着边遍历每一个顶点。常用的图的遍历方法有两种：深度优先搜索和广度优先搜索。

3.1 深度优先搜索（DFS）

深度优先搜索是一种尽可能“深入”访问图中顶点的遍历方法。其特点是沿着路径深入到某一分支的末端，然后回溯到上一个节点再遍历其他分支。

DFS 实现代码

以下是一个使用邻接矩阵表示图，并实现DFS的C语言示例代码：

#include <stdio.h>

#define MAX_VERTICES 10  // 定义最大顶点数
#define TRUE 1
#define FALSE 0

// 定义图结构
typedef struct {
    int vertices[MAX_VERTICES][MAX_VERTICES];  // 邻接矩阵
    int vertex_count;  // 顶点数量
} Graph;

// 初始化图
void initGraph(Graph *g, int vertex_count) {
    g->vertex_count = vertex_count;
    for (int i = 0; i < vertex_count; i++) {
        for (int j = 0; j < vertex_count; j++) {
            g->vertices[i][j] = 0;
        }
    }
}

// 添加边
void addEdge(Graph *g, int start, int end) {
    g->vertices[start][end] = 1;
    g->vertices[end][start] = 1;  // 如果是无向图，则双向连接
}

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

    for (int i = 0; i < g->vertex_count; i++) {
        if (g->vertices[v][i] == 1 && !visited[i]) {  // 找到未访问的相邻顶点
            DFS(g, i, visited);  // 递归访问相邻顶点
        }
    }
}

// 调用DFS遍历整个图
void depthFirstSearch(Graph *g) {
    int visited[MAX_VERTICES] = {FALSE};  // 初始化访问标记
    printf("深度优先搜索遍历结果: ");
    for (int i = 0; i < g->vertex_count; i++) {
        if (!visited[i]) {
            DFS(g, i, visited);  // 对未访问的顶点进行DFS
        }
    }
    printf("\n");
}

3.2 广度优先搜索（BFS）

广度优先搜索是一种“逐层”访问图中顶点的遍历方法，使用队列存储待访问的顶点。先访问当前层的所有顶点，再逐层深入，适合查找最短路径。

BFS 实现代码

以下代码使用邻接矩阵表示图，并实现BFS算法：

#include <stdbool.h>

#define QUEUE_SIZE MAX_VERTICES

typedef struct {
    int items[QUEUE_SIZE];
    int front, rear;
} Queue;

// 初始化队列
void initQueue(Queue *q) {
    q->front = 0;
    q->rear = -1;
}

// 入队
void enqueue(Queue *q, int value) {
    if (q->rear < QUEUE_SIZE - 1) {
        q->items[++q->rear] = value;
    }
}

// 出队
int dequeue(Queue *q) {
    if (q->front <= q->rear) {
        return q->items[q->front++];
    }
    return -1;
}

// 判断队列是否为空
bool isEmpty(Queue *q) {
    return q->front > q->rear;
}

// 广度优先搜索
void breadthFirstSearch(Graph *g, int start) {
    int visited[MAX_VERTICES] = {FALSE};
    Queue q;
    initQueue(&q);

    printf("广度优先搜索遍历结果: ");
    enqueue(&q, start);   // 起点入队
    visited[start] = TRUE;

    while (!isEmpty(&q)) {
        int v = dequeue(&q);  // 获取队首顶点
        printf("%d ", v);

        for (int i = 0; i < g->vertex_count; i++) {
            if (g->vertices[v][i] == 1 && !visited[i]) {
                enqueue(&q, i);   // 相邻未访问顶点入队
                visited[i] = TRUE;  // 标记为已访问
            }
        }
    }
    printf("\n");
}

主函数调用示例

在主函数中初始化图、添加边并调用DFS和BFS函数进行遍历：

int main() {
    Graph g;
    initGraph(&g, 5);  // 假设图中有5个顶点

    // 添加一些边
    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    addEdge(&g, 1, 3);
    addEdge(&g, 2, 4);

    depthFirstSearch(&g);  // 执行深度优先搜索
    breadthFirstSearch(&g, 0);  // 从顶点0执行广度优先搜索

    return 0;
}

4 图的连通性问题

图的连通性问题在很多算法中是重要的基础。连通性问题主要涉及图的连通分量、生成树、强连通分量、最小生成树等。

4.1 无向图的连通分量和生成树

无向图的连通分量是一个最大连通子图。一个无向图可能包含多个连通分量。生成树是一个连通分量中包含所有顶点的最小边集合，且不包含环。

4.1.1 连通分量的DFS实现

可以通过深度优先搜索（DFS）找到所有连通分量。

#include <stdio.h>

#define MAX_VERTICES 10

typedef struct {
    int vertices[MAX_VERTICES][MAX_VERTICES];  // 邻接矩阵
    int vertex_count;  // 顶点数
} Graph;

void DFS(Graph *g, int v, int visited[]) {
    visited[v] = 1;
    printf("%d ", v);

    for (int i = 0; i < g->vertex_count; i++) {
        if (g->vertices[v][i] == 1 && !visited[i]) {
            DFS(g, i, visited);
        }
    }
}

void findConnectedComponents(Graph *g) {
    int visited[MAX_VERTICES] = {0};
    printf("连通分量:\n");
    for (int i = 0; i < g->vertex_count; i++) {
        if (!visited[i]) {
            DFS(g, i, visited);  // 每找到一个未访问顶点即代表一个连通分量
            printf("\n");
        }
    }
}

4.1.2 最小生成树的Kruskal算法

Kruskal算法通过对所有边进行排序并逐步选择权值最小的边来构造最小生成树。

4.2 有向图的强连通分量

在有向图中，强连通分量是一个子图，其中任意两个顶点都是互相可达的。通常可以使用Kosaraju算法实现，它包含两次DFS遍历。

// 示例：通过Kosaraju算法找出强连通分量
void kosarajuSCC(Graph *g) {
    // 1. 执行第一次DFS，记录顶点的完成时间
    // 2. 反转图
    // 3. 按照完成时间降序执行第二次DFS，找出所有强连通分量
}

4.3 最小生成树

最小生成树（MST）是一个加权连通图的子图，它连接了所有顶点并且总权值最小。常用的算法有Kruskal和Prim。

4.3.1 Kruskal算法

Kruskal算法基于边的排序实现MST。主要步骤是将图中的边按权重排序，从小到大依次选择，如果加入一条边不构成环，则将其加入MST中。

// Kruskal算法代码示例
void kruskalMST(Graph *g) {
    // 对所有边按权重排序
    // 依次选择权重最小且不构成环的边
}

4.4 关节点和重连通分量

关节点（Articulation Point）是指在无向图中去掉该顶点后，图的连通性减少的点。可以通过DFS和时间戳的递归算法（Tarjan算法）找到关节点。

#include <limits.h>

void articulationPoints(Graph *g) {
    int visited[MAX_VERTICES] = {0}, parent[MAX_VERTICES], disc[MAX_VERTICES], low[MAX_VERTICES];
    for (int i = 0; i < g->vertex_count; i++) {
        if (!visited[i]) {
            dfsArticulation(g, i, visited, disc, low, parent);
        }
    }
}

void dfsArticulation(Graph *g, int u, int visited[], int disc[], int low[], int parent[]) {
    static int time = 0;
    visited[u] = 1;
    disc[u] = low[u] = ++time;
    int children = 0;

    for (int v = 0; v < g->vertex_count; v++) {
        if (g->vertices[u][v]) {  // 如果u和v之间有边
            if (!visited[v]) {  // v未访问
                parent[v] = u;
                children++;
                dfsArticulation(g, v, visited, disc, low, parent);

                low[u] = (low[u] < low[v]) ? low[u] : low[v];

                if (parent[u] == -1 && children > 1) {
                    printf("关节点: %d\n", u);
                }
                if (parent[u] != -1 && low[v] >= disc[u]) {
                    printf("关节点: %d\n", u);
                }
            } else if (v != parent[u]) {
                low[u] = (low[u] < disc[v]) ? low[u] : disc[v];
            }
        }
    }
}

原文地址：https://blog.csdn.net/Asuna666w/article/details/143695390

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：《Windows 11系统》VMware创建 Windows 10操作系统虚拟机安装和配置ISO镜像文件详细教程和使用
下一篇：双指针_移动零和_复写零_c++

目标检测(object detection)
目标检测广泛应用在多个领域：无人驾驶，机器人…那么如何去定位一个目标的位置呢？
阅读更多2024-11-15
目标检测评估指标详解
特别是IoU，它在目标检测中用于评估预测框的定位准确性，是其他指标（如TP、FP、FN等）的基础。1.正样本（Positive Sample）：在目标检测任务中，指的是那些确实包含目标物体的图像区域。
阅读更多2024-11-15
《目标检测》R-CNN网络基础（RCNN，Fast-RCNN）
训练阶段多，训练耗时：微调CNN⽹络+训练SVM+训练边框回归器。预测速度慢: 使⽤GPU, VGG16模型处理⼀张图像需要47s。占⽤磁盘空间⼤：5000张图像产⽣⼏百G的特征⽂件。数据的形状变化
阅读更多2024-11-15
第5章: 图像变换与仿射操作
在 Pillow 中，我们将此矩阵简化为六个参数。# 创建自定义仿射变换案例：生成透视效果通过调整仿射变换矩阵的参数，可以创建透视效果，使图像看起来像从不同角度拍摄。# 创建透视效果。
阅读更多2024-11-15
itss认证的作用
认证的作用
阅读更多2024-11-15
什么是HTTP，什么是HTTPS？HTTP和HTTPS都有哪些区别？
什么是HTTP，什么是HTTPS？HTTP和HTTPS都有哪些区别？
阅读更多2024-11-15
kafka中topic的数据抽取不到hdfs上问题解决
将json文件抽取到kafka的消息队列（topic）中，再从topic中将数据抽取到hdfs。我们在从kafka中topic的数据抽到hdfs上的时候会出现 flume不报错，但也不抽取的情况。其实
阅读更多2024-11-15
聊天服务器(5)数据库环境搭建和编程
设置中文。
阅读更多2024-11-15
Ubuntu 22.04.4 LTS + certbot 做自动续签SSL证书(2024-11-14亲测)
在运行上述命令时，Certbot 可能会提示您选择一个或多个域名，并询问您是否希望将所有流量重定向到 HTTPS。Certbot 是一个易于使用的客户端，它可以自动获取和安装 SSL/TLS 证书，以
阅读更多2024-11-15
探秘 RPC：揭开远程过程调用的实现原理
概念理解RPC 旨在让开发人员在构建分布式系统时，无需过多关注底层网络通信的细节，就能够像在本地调用函数那样去调用远程服务器上的服务或方法。例如，在一个电商系统中，订单服务可能部署在一台服务器上，而库
阅读更多2024-11-15