竞赛常考的知识点大总结(七)图论

news/2024/7/15 19:46:43 标签: 图论

最短路

最短路问题（Shortest Path Problem）是图论中的一个经典问题，它要求在给定的图中找到两个顶点之间的最短路径。最短路问题可以是单源最短路问题（从一个顶点到其他所有顶点的最短路径）或所有对最短路问题（任意两个顶点之间的最短路径）。

特点：

1.图论问题：最短路问题是图论中的一个基本问题，通常在加权图中求解。

2.权重：图中的边具有权重，最短路问题的目标是最小化路径的权重总和。

3.多种算法：存在多种算法可以解决最短路问题，如迪杰斯特拉算法（Dijkstra's Algorithm）、贝尔曼-福特算法（Bellman-Ford Algorithm）、Floyd-Warshall算法等。

4.应用广泛：最短路问题在现实世界中有广泛的应用，如网络路由、交通规划、物流调度等。

常见用法：

1.网络路由：在网络设计中，最短路算法用于确定数据包的最佳传输路径。

2.交通规划：在交通规划中，最短路算法用于计算两点之间的最短行驶路径。

3.物流调度：在物流调度中，最短路算法用于优化货物的配送路径。

4.游戏开发：在游戏开发中，最短路算法用于AI寻路和地图探索。

经典C语言例题：

题目： 使用迪杰斯特拉算法解决单源最短路问题。

示例代码：

#include <stdio.h>
#include <limits.h>

// 定义图的结构体
typedef struct Graph {
    int V; // 顶点数量
    int** adjMatrix; // 邻接矩阵
} Graph;

// 创建图的函数
Graph* createGraph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;
    graph->adjMatrix = (int**)malloc(V * sizeof(int*));
    for (int i = 0; i < V; i++) {
         graph->adjMatrix[i] = (int*)malloc(V * sizeof(int));
         memset(graph->adjMatrix[i], INT_MAX, V * sizeof(int));
         graph->adjMatrix[i][i] = 0;
       }
    return graph;
}

// 添加边的函数
void addEdge(Graph* graph, int src, int dest, int weight) {
    graph->adjMatrix[src][dest] = weight;
    graph->adjMatrix[dest][src] = weight; // 无向图
}

// 迪杰斯特拉算法函数
void dijkstra(Graph* graph, int src) {
    int* dist = (int*)malloc(graph->V * sizeof(int));
    int* sptSet = (int*)malloc(graph->V * sizeof(int));
    for (int i = 0; i < graph->V; i++) {
         dist[i] = INT_MAX;
         sptSet[i] = 0;
       }
    dist[src] = 0;
    for (int count = 0; count < graph->V - 1; count++) {
         int u = -1, min = INT_MAX;
         for (int v = 0; v < graph->V; v++) {
              if (sptSet[v] == 0 && dist[v] <= min) {
                   u = v;
                   min = dist[v];
                 }
             }
         sptSet[u] = 1;
         for (int v = 0; v < graph->V; v++) {
              if (sptSet[v] == 0 && graph->adjMatrix[u][v] && dist[u] != INT_MAX && dist[u] + graph->adjMatrix[u][v] < dist[v]) {
                   dist[v] = dist[u] + graph->adjMatrix[u][v];
                 }
             }
       }
    printf("Vertex\tDistance from Source\n");
    for (int i = 0; i < graph->V; i++) {
         printf("%d\t\t%d\n", i, dist[i]);
       }
    free(dist);
    free(sptSet);
}

int main() {
    Graph* graph = createGraph(9);
    addEdge(graph, 0, 1, 4);
    addEdge(graph, 0, 7, 8);
    addEdge(graph, 1, 2, 8);
    addEdge(graph, 1, 7, 11);
    addEdge(graph, 2, 3, 7);
    addEdge(graph, 2, 8, 2);
    addEdge(graph, 2, 5, 4);
    addEdge(graph, 3, 4, 9);
    addEdge(graph, 3, 5, 14);
    addEdge(graph, 4, 5, 10);
    addEdge(graph, 5, 6, 2);
    addEdge(graph, 6, 8, 6);
    addEdge(graph, 6, 7, 1);
    addEdge(graph, 7, 8, 7);
    dijkstra(graph, 0);
    free(graph->adjMatrix[0]);
    free(graph->adjMatrix);
    free(graph);
    return 0;
}

例题分析：

1.创建图：createGraph函数创建一个图的结构体，包括顶点数量和邻接矩阵。

2.添加边：addEdge函数向图中添加边，并设置边的权重。

3.迪杰斯特拉算法：dijkstra函数实现迪杰斯特拉算法，计算从源点src到其他所有顶点的最短路径。函数使用一个数组dist来存储到每个顶点的最短路径权重，另一个数组sptSet来标记已经找到最短路径的顶点。

4.打印结果：函数最后打印出每个顶点到源点的最短路径权重。

5.主函数：在main函数中，创建了一个图，并添加了一些边。调用dijkstra函数计算从顶点0到其他所有顶点的最短路径，并打印结果。

这个例题展示了如何在C语言中使用迪杰斯特拉算法解决单源最短路问题。通过这个例子，可以更好地理解迪杰斯特拉算法在解决最短路问题中的应用，以及如何使用邻接矩阵来存储图的信息。迪杰斯特拉算法是一种贪心算法，它通过逐步选择最短的未处理路径来找到最短路径，适用于加权图中的单源最短路问题。

树的直径

树的直径（Diameter of a Tree）是指树中任意两点之间的最长路径的长度。在图论中，树是一种特殊的无向图，它没有环，并且任意两个顶点之间有且仅有一条路径。

特点：

1.最长路径：树的直径是树中任意两点之间的最长路径的长度。

2.无环：树是一种无环的图，这意味着树中不存在循环依赖。

3.唯一路径：在树中，任意两个顶点之间有且仅有一条路径。

4.连通性：树中的任意两个顶点都是连通的。

常见用法：

1.网络设计：在计算机网络中，树的直径可以用来衡量网络的效率，最长路径越短，网络的响应时间越短。

2.数据结构：在数据结构中，树的直径可以用来衡量树的深度，有助于优化树的存储和查询效率。

3.算法设计：在算法设计中，树的直径可以用来衡量算法的性能，最长路径越短，算法的效率越高。

经典C语言例题：

题目： 计算树的直径。

示例代码：

#include <stdio.h>
#include <limits.h>

// 定义树的结构体
typedef struct Node {
    int vertex;
    struct Node* left;
    struct Node* right;
} Node;

// 创建树的节点
Node* newNode(int v) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->vertex = v;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 计算树的直径
int treeDiameter(Node* root) {
    if (root == NULL) {
         return 0;
      }
      // 计算左右子树的高度
      int leftHeight = treeDiameter(root->left);
      int rightHeight = treeDiameter(root->right);
      // 更新直径
      int diameter = leftHeight + rightHeight;
      // 返回当前子树的高度
      return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
}

// 主函数
int main() {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    printf("Diameter of the tree is: %d\n", treeDiameter(root));
    return 0;
}

例题分析：

1.创建树的节点：newNode函数创建树的节点，并初始化节点的值。

2.计算树的直径：treeDiameter函数递归地计算树的直径。函数首先计算左右子树的高度，然后更新直径，最后返回当前子树的高度。

3.主函数：在main函数中，创建了一个树的实例，并调用treeDiameter函数计算树的直径，最后打印结果。

这个例题展示了如何在C语言中使用递归方法来计算树的直径。通过这个例子，可以更好地理解树的直径在解决树形结构问题中的应用，以及如何使用递归技术来高效地解决问题。树的直径是树中任意两点之间的最长路径的长度，通过计算左右子树的高度并更新直径，可以得到整个树的直径。

拓扑排序

拓扑排序（Topological Sorting）是图论中的一种算法，用于对有向无环图（DAG）的顶点进行排序，使得对于图中的每一条有向边(u, v)，u在排序中都出现在v之前。拓扑排序通常用于解决依赖关系问题，如课程安排、任务调度等。

特点：

1.有向无环图：拓扑排序只适用于有向无环图，即图中不存在环。

2.排序结果：拓扑排序的结果可能不唯一，因为可能存在多个合法的排序。

3.依赖关系：拓扑排序反映了图中顶点之间的依赖关系，即如果存在一条路径从u到v，则u在排序中必须出现在v之前。

4.应用广泛：拓扑排序在编译器设计、软件工程、项目管理等领域都有广泛应用。

常见用法：

1.课程安排：在大学课程安排中，拓扑排序可以用来确定课程的先修关系。

2.任务调度：在项目管理中，拓扑排序可以用来确定任务的执行顺序。

3.依赖解析：在软件构建系统中，拓扑排序可以用来解析模块之间的依赖关系。

经典C语言例题：

题目： 使用拓扑排序解决课程安排问题。

示例代码：

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

// 定义图的结构体
typedef struct Graph {
    int V; // 顶点数量
    int* adjMatrix; // 邻接矩阵
} Graph;

// 创建图的函数
Graph* createGraph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;
    graph->adjMatrix = (int*)malloc(V * V * sizeof(int));
    return graph;
}

// 添加边的函数
void addEdge(Graph* graph, int src, int dest) {
    graph->adjMatrix[src * graph->V + dest] = 1;
}

// 拓扑排序函数
void topologicalSort(Graph* graph, int V, int* order) {
    int* indegree = (int*)calloc(V, sizeof(int));
    for (int i = 0; i < V; i++) {
         for (int j = 0; j < V; j++) {
              if (graph->adjMatrix[i * V + j] == 1) {
                   indegree[j]++;
                  }
              }
         }
    int queue[V];
    int front = 0, rear = -1;
    for (int i = 0; i < V; i++) {
         if (indegree[i] == 0) {
              queue[++rear] = i;
              }
         }
    int count = 0;
    while (front <= rear) {
         int v = queue[front++];
         order[count++] = v;
         for (int i = 0; i < V; i++) {
              if (graph->adjMatrix[v * V + i] == 1 && --indegree[i] == 0) {
                   queue[++rear] = i;
                  }
              }
         }
    if (count != V) {
         printf("Graph has a cycle\n");
         free(indegree);
         free(queue);
         return;
       }
    printf("Topological order: ");
    for (int i = 0; i < count; i++) {
         printf("%d ", order[i]);
       }
    printf("\n");
    free(indegree);
    free(queue);
}

int main() {
    Graph* graph = createGraph(6);
    addEdge(graph, 5, 2);
    addEdge(graph, 5, 0);
    addEdge(graph, 4, 0);
    addEdge(graph, 4, 1);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 1);
    int order[6];
    topologicalSort(graph, 6, order);
    return 0;
}

例题分析：

1.创建图：createGraph函数创建一个图的结构体，包括顶点数量和邻接矩阵。

2.添加边：addEdge函数向图中添加边。

3.拓扑排序：topologicalSort函数实现拓扑排序算法。函数首先计算每个顶点的入度，然后将入度为0的顶点入队列。接着，从队列中取出顶点，将其加入排序结果，并将其所有出边对应的顶点的入度减1，如果入度变为0，则加入队列。最后，如果排序结果的顶点数量不等于图的顶点数量，则说明图中有环。

4.打印结果：函数最后打印出拓扑排序的结果。

5.主函数：在main函数中，创建了一个图，并添加了一些边。调用topologicalSort函数计算拓扑排序，并打印结果。

这个例题展示了如何在C语言中使用拓扑排序解决课程安排问题。通过这个例子，可以更好地理解拓扑排序在解决依赖关系问题中的应用，以及如何使用邻接矩阵来存储图的信息。拓扑排序是一种有效的算法，可以用来确定有向无环图中顶点的合法排序，从而解决依赖关系问题。

最小生成树

最小生成树（Minimum Spanning Tree，MST）是图论中的一个概念，它是指在一个加权连通图中，选取的边的权重之和最小，并且包括图中的所有顶点的生成树。最小生成树具有以下特点：

特点：

1.连通性：最小生成树包含图中的所有顶点。

2.无环：最小生成树是一棵树，因此它不包含任何环。

3.权重最小：最小生成树的边的权重之和是所有生成树中最小的。

4.唯一性：在权重不相等的图中，最小生成树是唯一的；如果图中存在权重相同的边，则可能存在多个最小生成树。

常见用法：

1.网络设计：在计算机网络中，最小生成树用于设计最经济的网络连接。

2.电路设计：在电路设计中，最小生成树用于寻找连接所有元件的最短路径。

3.城市规划：在城市规划中，最小生成树用于确定城市中各个区域的最短道路连接。

4.图像处理：在图像处理中，最小生成树用于图像分割和特征提取。

经典C语言例题：

题目： 使用普里姆算法（Prim's Algorithm）解决最小生成树问题。

示例代码：

#include <stdio.h>
#include <limits.h>

// 定义图的结构体
typedef struct Graph {
    int V; // 顶点数量
    int** adjMatrix; // 邻接矩阵
} Graph;

// 创建图的函数
Graph* createGraph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;
    graph->adjMatrix = (int**)malloc(V * sizeof(int*));
    for (int i = 0; i < V; i++) {
         graph->adjMatrix[i] = (int*)malloc(V * sizeof(int));
         memset(graph->adjMatrix[i], INT_MAX, V * sizeof(int));
         graph->adjMatrix[i][i] = 0;
        }
    return graph;
}

// 添加边的函数
void addEdge(Graph* graph, int src, int dest, int weight) {
    graph->adjMatrix[src][dest] = weight;
    graph->adjMatrix[dest][src] = weight; // 无向图
}

// 普里姆算法函数
void primMST(Graph* graph, int start) {
    int* key = (int*)malloc(graph->V * sizeof(int));
    int* parent = (int*)malloc(graph->V * sizeof(int));
    int* inMST = (int*)calloc(graph->V, sizeof(int));
    for (int i = 0; i < graph->V; i++) {
         key[i] = INT_MAX;
         parent[i] = -1;
        }
    key[start] = 0;
    parent[start] = -1;
    for (int count = 0; count < graph->V - 1; count++) {
         int u = -1, min = INT_MAX;
         for (int v = 0; v < graph->V; v++) {
              if (inMST[v] == 0 && key[v] <= min) {
                   u = v;
                   min = key[v];
                  }
              }
         inMST[u] = 1;
         for (int v = 0; v < graph->V; v++) {
              if (graph->adjMatrix[u][v] && inMST[v] == 0 && graph->adjMatrix[u][v] < key[v]) {
                   parent[v] = u;
                    key[v] = graph->adjMatrix[u][v];
                  }
              }
        }
    printf("Edge \tWeight\n");
    for (int i = 1; i < graph->V; i++) {
         printf("%d - %d \t%d\n", parent[i], i, graph->adjMatrix[i][parent[i]]);
        }
    free(key);
    free(parent);
    free(inMST);
}

int main() {
    Graph* graph = createGraph(9);
    addEdge(graph, 0, 1, 4);
    addEdge(graph, 0, 7, 8);
    addEdge(graph, 1, 2, 8);
    addEdge(graph, 1, 7, 11);
    addEdge(graph, 2, 3, 7);
    addEdge(graph, 2, 8, 2);
    addEdge(graph, 2, 5, 4);
    addEdge(graph, 3, 4, 9);
    addEdge(graph, 3, 5, 14);
    addEdge(graph, 4, 5, 10);
    addEdge(graph, 5, 6, 2);
    addEdge(graph, 6, 8, 6);
    addEdge(graph, 6, 7, 1);
    addEdge(graph, 7, 8, 7);
    primMST(graph, 0);
    free(graph->adjMatrix[0]);
    free(graph->adjMatrix);
    free(graph);
    return 0;
}

例题分析：

1.创建图：createGraph函数创建一个图的结构体，包括顶点数量和邻接矩阵。

2.添加边：addEdge函数向图中添加边，并设置边的权重。

3.普里姆算法：primMST函数实现普里姆算法，计算从源点start到其他所有顶点的最小生成树。函数使用三个数组key、parent和inMST来存储每个顶点的最小权重、前驱顶点和是否在最小生成树中。

4.打印结果：函数最后打印出最小生成树的边和权重。

5.主函数：在main函数中，创建了一个图，并添加了一些边。调用primMST函数计算从顶点0到其他所有顶点的最小生成树，并打印结果。

这个例题展示了如何在C语言中使用普里姆算法解决最小生成树问题。通过这个例子，可以更好地理解普里姆算法在解决最小生成树问题中的应用，以及如何使用邻接矩阵来存储图的信息。普里姆算法是一种贪心算法，它通过逐步选择最小权重的边来构建最小生成树，适用于加权图中的最小生成树问题。


http://www.niftyadmin.cn/n/5464442.html

相关文章

入门教程：Windows搭建C语言和EasyX开发环境

入门教程：Windows搭建C语言和EasyX开发环境

&#x1f31f; 前言 欢迎来到我的技术小宇宙&#xff01;&#x1f30c; 这里不仅是我记录技术点滴的后花园&#xff0c;也是我分享学习心得和项目经验的乐园。&#x1f4da; 无论你是技术小白还是资深大牛&#xff0c;这里总有一些内容能触动你的好奇心。&#x1f50d; 如果对你…
阅读更多...
瑞吉外卖实战学习--10、完成新增菜品分类

瑞吉外卖实战学习--10、完成新增菜品分类

完成新增菜品分类 前言1、前期准备定义实体类和实体对象 2、创建修改的接口 前言 1、前期准备 定义实体类和实体对象 package com.example.ruiji_demo.entity;import com.baomidou.mybatisplus.annotation.FieldFill; import com.baomidou.mybatisplus.annotation.TableField; …
阅读更多...
【虚幻引擎】C++ slate全流程开发教程

【虚幻引擎】C++ slate全流程开发教程

本套课程介绍了使用我们的虚幻C去开发我们的编辑器&#xff0c;扩展我们的编辑器&#xff0c;设置我们自定义样式&#xff0c;Slate架构设计&#xff0c;自定义我们的编辑器样式&#xff0c;从基础的Slate控件到我们的布局&#xff0c;一步步的讲解我们的的Slate基础知识&#…
阅读更多...
HarmonyOS 应用开发之XML生成、解析与转换

HarmonyOS 应用开发之XML生成、解析与转换

XML&#xff08;可扩展标记语言&#xff09;是一种用于描述数据的标记语言&#xff0c;旨在提供一种通用的方式来传输和存储数据&#xff0c;特别是Web应用程序中经常使用的数据。XML并不预定义标记。因此&#xff0c;XML更加灵活&#xff0c;并且可以适用于广泛的应用领域。 …
阅读更多...
2024蓝桥杯每日一题（树形DP）

2024蓝桥杯每日一题（树形DP）

备战2024年蓝桥杯 -- 每日一题 Python大学A组 试题一&#xff1a;病毒溯源 试题二&#xff1a;没有上司的舞会 试题三&#xff1a;生命之树 试题一&#xff1a;病毒溯源 【题目描述】 病毒容易发生变异。某种病毒可以通过突变产生若干变异的毒株&#xff0c;而…
阅读更多...
星际门计划：微软与OpenAI联手打造未来AI超级计算机

星际门计划：微软与OpenAI联手打造未来AI超级计算机

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…
阅读更多...
HTML——4.表格、列表、区块

HTML——4.表格、列表、区块

一、表格 HTML 表格是用于展示结构化数据的重要元素&#xff0c;它允许将数据以行和列的形式组织和显示。 基本结构和常见元素&#xff1a; 1. <table> 元素 <table> 元素是 HTML 表格的根元素&#xff0c;它用于定义整个表格的开始和结束。 2. <thead>、…
阅读更多...
Redis开源协议调整，我们怎么办？

Redis开源协议调整，我们怎么办？

2024年3月20日, Redis官方宣布&#xff0c;从 Redis 7.4版本开始&#xff0c;Redis将获得源可用许可证 ( RSALv2 ) 和服务器端公共许可证 ( SSPLv1 ) 的双重许可&#xff0c;时间点恰逢刚刚完成最新一轮融资&#xff0c;宣布的时机耐人寻味。 Redis协议调整&#xff0c;对云计算…
阅读更多...
最新文章

Copyright @ 2022~2023