设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › 数据结构与算法 › 迪杰斯特拉算法用邻接表存储赋权图
返回列表 发新帖
查看: 387|回复: 1

[已解决]迪杰斯特拉算法用邻接表存储赋权图

[复制链接]
好故事慢慢来
发表于 2023-6-13 20:48:31 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
迪杰斯特拉算法用邻接表存储赋权图怎么实现；用c语言，谢谢嘞
最佳答案
月排行榜 / 总排行榜
isdkz
2023-6-13 20:56:40
Dijkstra算法是一种常用的最短路径算法，下面我会用C语言展示一个利用邻接表来存储赋权图的版本。首先，我们需要定义邻接表的节点结构和邻接表本身的结构：

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define INFINITY 999999
  4. #define MAX 10

  6. // 邻接表的节点结构
  7. typedef struct node {
  8.     int vertex;     // 顶点编号
  9.     int weight;     // 边的权值
  10.     struct node* next;  // 指向下一个节点的指针
  11. } node;

  13. // 邻接表的结构
  14. typedef struct Graph {
  15.     int numVertices;   // 顶点数量
  16.     struct node** adjLists; // 邻接表数组
  17.     int* distance;   // 保存每个顶点到源顶点的最短距离
  18. } Graph;

  20. // 创建节点
  21. node* createNode(int v, int weight) {
  22.     node* newNode = malloc(sizeof(node));
  23.     newNode->vertex = v;
  24.     newNode->weight = weight;
  25.     newNode->next = NULL;
  26.     return newNode;
  27. }

  29. // 创建图
  30. Graph* createGraph(int vertices) {
  31.     Graph* graph = malloc(sizeof(Graph));
  32.     graph->numVertices = vertices;
  33.     graph->adjLists = malloc(vertices * sizeof(node*));
  34.     graph->distance = malloc(vertices * sizeof(int));
  35.    
  36.     int i;
  37.     for (i = 0; i < vertices; i++) {
  38.         graph->adjLists[i] = NULL;
  39.         graph->distance[i] = INFINITY;
  40.     }
  41.     return graph;
  42. }

  44. // 添加边
  45. void addEdge(Graph* graph, int src, int dest, int weight) {
  46.     // 从src到dest的边
  47.     node* newNode = createNode(dest, weight);
  48.     newNode->next = graph->adjLists[src];
  49.     graph->adjLists[src] = newNode;

  51.     // 在无向图中添加从dest到src的边
  52.     newNode = createNode(src, weight);
  53.     newNode->next = graph->adjLists[dest];
  54.     graph->adjLists[dest] = newNode;
  55. }
复制代码


然后，我们需要实现Dijkstra算法本身：

  1. // 找到距离源顶点最近的顶点
  2. int findMinVertex(Graph* graph, int* visited) {
  3.     int minVertex = -1;
  4.     for (int i = 0; i < graph->numVertices; i++) {
  5.         if (!visited[i] && (minVertex == -1 || graph->distance[i] < graph->distance[minVertex])) {
  6.             minVertex = i;
  7.         }
  8.     }
  9.     return minVertex;
  10. }

  12. // 执行Dijkstra算法
  13. void dijkstra(Graph* graph, int startVertex) {
  14.     int visited[MAX] = {0};
  15.     graph->distance[startVertex] = 0;

  17.     for (int i = 0; i < graph->numVertices - 1; i++) {
  18.         int minVertex = findMinVertex(graph, visited);
  19.         visited[minVertex] = 1;

  21.         node* adjList = graph->adjLists[minVertex];
  22.         while (adjList != NULL) {
  23.             int adjVertex = adjList->vertex;
  24.             if (!visited[adjVertex] && graph->distance[minVertex] != INFINITY
  25.                 && graph->distance[adjVertex] > graph->distance[minVertex] + adjList->weight) {
  26.                 graph->distance[adjVertex] = graph->distance[minVertex] + adjList->weight;
  27.             }
  28.             adjList = adjList->next;
  29.         }
  30.     }
  31. }

  33. // 打印结果
  34. void printGraph(Graph* graph) {
  35.     for (int i = 0; i < graph->numVertices; i++)
  36.         printf("Vertex %d -> distance = %d\n", i, graph->distance[i]);
  37. }
复制代码


最后，我们可以在main函数中测试这个算法：

  1. int main() {
  2.     Graph* graph = createGraph(6);
  3.     addEdge(graph, 0, 1, 4);
  4.     addEdge(graph, 0, 2, 2);
  5.     addEdge(graph, 1, 2, 1);
  6.     addEdge(graph, 1, 3, 5);
  7.     addEdge(graph, 2, 3, 8);
  8.     addEdge(graph, 2, 4, 10);
  9.     addEdge(graph, 3, 5, 6);
  10.     addEdge(graph, 4, 5, 2);
  11.    
  12.     dijkstra(graph, 0);
  13.     printGraph(graph);
  14.    
  15.     return 0;
  16. }
复制代码


以上就是一个基于邻接表实现的Dijkstra算法的例子。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

isdkz
发表于 2023-6-13 20:56:40 | 显示全部楼层    本楼为最佳答案   
Dijkstra算法是一种常用的最短路径算法，下面我会用C语言展示一个利用邻接表来存储赋权图的版本。首先，我们需要定义邻接表的节点结构和邻接表本身的结构：

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define INFINITY 999999
  4. #define MAX 10

  6. // 邻接表的节点结构
  7. typedef struct node {
  8.     int vertex;     // 顶点编号
  9.     int weight;     // 边的权值
  10.     struct node* next;  // 指向下一个节点的指针
  11. } node;

  13. // 邻接表的结构
  14. typedef struct Graph {
  15.     int numVertices;   // 顶点数量
  16.     struct node** adjLists; // 邻接表数组
  17.     int* distance;   // 保存每个顶点到源顶点的最短距离
  18. } Graph;

  20. // 创建节点
  21. node* createNode(int v, int weight) {
  22.     node* newNode = malloc(sizeof(node));
  23.     newNode->vertex = v;
  24.     newNode->weight = weight;
  25.     newNode->next = NULL;
  26.     return newNode;
  27. }

  29. // 创建图
  30. Graph* createGraph(int vertices) {
  31.     Graph* graph = malloc(sizeof(Graph));
  32.     graph->numVertices = vertices;
  33.     graph->adjLists = malloc(vertices * sizeof(node*));
  34.     graph->distance = malloc(vertices * sizeof(int));
  35.    
  36.     int i;
  37.     for (i = 0; i < vertices; i++) {
  38.         graph->adjLists[i] = NULL;
  39.         graph->distance[i] = INFINITY;
  40.     }
  41.     return graph;
  42. }

  44. // 添加边
  45. void addEdge(Graph* graph, int src, int dest, int weight) {
  46.     // 从src到dest的边
  47.     node* newNode = createNode(dest, weight);
  48.     newNode->next = graph->adjLists[src];
  49.     graph->adjLists[src] = newNode;

  51.     // 在无向图中添加从dest到src的边
  52.     newNode = createNode(src, weight);
  53.     newNode->next = graph->adjLists[dest];
  54.     graph->adjLists[dest] = newNode;
  55. }
复制代码


然后，我们需要实现Dijkstra算法本身：

  1. // 找到距离源顶点最近的顶点
  2. int findMinVertex(Graph* graph, int* visited) {
  3.     int minVertex = -1;
  4.     for (int i = 0; i < graph->numVertices; i++) {
  5.         if (!visited[i] && (minVertex == -1 || graph->distance[i] < graph->distance[minVertex])) {
  6.             minVertex = i;
  7.         }
  8.     }
  9.     return minVertex;
  10. }

  12. // 执行Dijkstra算法
  13. void dijkstra(Graph* graph, int startVertex) {
  14.     int visited[MAX] = {0};
  15.     graph->distance[startVertex] = 0;

  17.     for (int i = 0; i < graph->numVertices - 1; i++) {
  18.         int minVertex = findMinVertex(graph, visited);
  19.         visited[minVertex] = 1;

  21.         node* adjList = graph->adjLists[minVertex];
  22.         while (adjList != NULL) {
  23.             int adjVertex = adjList->vertex;
  24.             if (!visited[adjVertex] && graph->distance[minVertex] != INFINITY
  25.                 && graph->distance[adjVertex] > graph->distance[minVertex] + adjList->weight) {
  26.                 graph->distance[adjVertex] = graph->distance[minVertex] + adjList->weight;
  27.             }
  28.             adjList = adjList->next;
  29.         }
  30.     }
  31. }

  33. // 打印结果
  34. void printGraph(Graph* graph) {
  35.     for (int i = 0; i < graph->numVertices; i++)
  36.         printf("Vertex %d -> distance = %d\n", i, graph->distance[i]);
  37. }
复制代码


最后，我们可以在main函数中测试这个算法：

  1. int main() {
  2.     Graph* graph = createGraph(6);
  3.     addEdge(graph, 0, 1, 4);
  4.     addEdge(graph, 0, 2, 2);
  5.     addEdge(graph, 1, 2, 1);
  6.     addEdge(graph, 1, 3, 5);
  7.     addEdge(graph, 2, 3, 8);
  8.     addEdge(graph, 2, 4, 10);
  9.     addEdge(graph, 3, 5, 6);
  10.     addEdge(graph, 4, 5, 2);
  11.    
  12.     dijkstra(graph, 0);
  13.     printGraph(graph);
  14.    
  15.     return 0;
  16. }
复制代码


以上就是一个基于邻接表实现的Dijkstra算法的例子。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-4-28 20:36

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表