单源无权最短路径 C实现~
本文共 4855 字，大约阅读时间需要 16 分钟。
利用广度优先搜索实现（BFS应用）
文件头:
#include#include #include #define INFINITY 65535#define NOTEXIST -1#define MAXVEX 100int path[MAXVEX];int dist[MAXVEX];typedef char VertexType;typedef struct QNode { int front, rear; int data[MAXVEX]; int size;}Queue;typedef struct ENode { int ivex;//顶点 索引 struct ENode* next_edge;}ENode;typedef struct VNode { VertexType data; // 顶点 信息 ENode* first_edge;}VNode;typedef struct Graph { VNode vex[MAXVEX]; int vex_num, edge_num;}Graph;
核心代码：
void unweight_path(Graph g, int start){ Queue q; init_queue(&q); enqueue(start, &q); int v; while (!is_empty(q)) { v = get_front(q); dequeue(&q); ENode* p; p = g.vex[v].first_edge; while (p != NULL) { if (dist[p->ivex] == INFINITY) { dist[p->ivex] = dist[v] + 1; path[p->ivex] = v; enqueue(p->ivex, &q); } p = p->next_edge; } }} 补充一种打印最短路径方法:(类似后续遍历)
void print_path2(Graph g, int index)//这里 直接传递最后位置的索引 { if (path[index] != NOTEXIST) { print_path2(g, path[index]); printf("->"); } printf("%c", g.vex[index].data);} 完整代码实现：
#include#include #include #define INFINITY 65535#define NOTEXIST -1#define MAXVEX 100int path[MAXVEX];int dist[MAXVEX];typedef char VertexType;typedef struct QNode { int front, rear; int data[MAXVEX]; int size;}Queue;typedef struct ENode { int ivex;//顶点 索引 struct ENode* next_edge;}ENode;typedef struct VNode { VertexType data; // 顶点 信息 ENode* first_edge;}VNode;typedef struct Graph { VNode vex[MAXVEX]; int vex_num, edge_num;}Graph;int init_queue(Queue *q){ //q = (Queue*)malloc(sizeof(Queue));// 不能加这个 切记 q->size = 0; q->rear = 0; q->front = 0; return 1;}int is_full(Queue q){ return (q.rear + 1) % MAXVEX == q.front;}int is_empty(Queue q){ return q.front == q.rear;}void enqueue(int x, Queue *q){ if (!is_full(*q)) { q->data[q->rear] = x; q->rear = (q->rear + 1) % MAXVEX; q->size++; }}void dequeue(Queue *q){ if (!is_empty(*q)) { q->front = (q->front + 1) % MAXVEX; q->size--; }}int get_front(Queue q){ if (!is_empty(q)) { return q.data[q.front]; }}char read_char(){ char ch; do { ch = getchar(); } while (!isalpha(ch)); return ch;}int get_pos(Graph g, char ch){ int i; for (i = 0; i < g.vex_num; i++) { if (ch == g.vex[i].data) return i; } return -1;}void link_last(ENode* list, ENode *last){ ENode* p; p = list; while (p->next_edge != NULL) { p = p->next_edge; } p->next_edge = last;}void create_graph(Graph *g){ int i; printf("请输入顶点数和边数:\n"); scanf("%d%d", &g->vex_num, &g->edge_num); printf("请输入顶点信息:\n"); for (i = 0; i < g->vex_num; i++) { g->vex[i].first_edge = NULL; g->vex[i].data = read_char(); } printf("请输入边 :\n"); for (i = 0; i < g->edge_num; i++) { int p1, p2; char c1, c2; c1 = read_char(); c2 = read_char(); p1 = get_pos(*g, c1); p2 = get_pos(*g, c2); ENode* node1; node1 = (ENode*)malloc(sizeof(ENode)); if (node1 == NULL) { printf("error"); return; } node1->next_edge = NULL; node1->ivex = p2; if (g->vex[p1].first_edge == NULL) g->vex[p1].first_edge = node1; else link_last(g->vex[p1].first_edge, node1); }}void print_graph(Graph g){ int i; ENode* p; for (i = 0; i < g.vex_num; i++) { printf("%c", g.vex[i].data); p = g.vex[i].first_edge; while (p != NULL) { printf("(%c, %c)", g.vex[i].data, g.vex[p->ivex].data); p = p->next_edge; } printf("\n"); }}void init_graph(Graph g, int start){ int i; for (i = 0; i < g.vex_num; i++) { dist[i] = INFINITY; path[i] = NOTEXIST; } dist[start] = 0;}void unweight_path(Graph g, int start){ Queue q; init_queue(&q); enqueue(start, &q); int v; while (!is_empty(q)) { v = get_front(q); dequeue(&q); ENode* p; p = g.vex[v].first_edge; while (p != NULL) { if (dist[p->ivex] == INFINITY) { dist[p->ivex] = dist[v] + 1; path[p->ivex] = v; enqueue(p->ivex, &q); } p = p->next_edge; } }}int print_path(Graph g, int end){ int pos, i; pos = end; i = pos; int cnt = 1;// 记录该最短路径有几个元素 int count; for (; path[i] != NOTEXIST; i = path[i]) { cnt++; } count = cnt; char* ins = (char*)malloc(sizeof(char)*cnt); if (cnt == 1) { printf("不存在该路径"); return 0; } ins[0] = g.vex[i].data;//路径初始位置 i = pos;//把 路径 反序记入 数组 for (; path[i] != NOTEXIST; i = path[i]) { ins[--cnt] = g.vex[i].data; } //打印 该路径 int flag = 1; for (i = 0; i < count; i++) { if (flag == 1) { flag = 0; printf("%c", ins[i]); } else { printf("->%c", ins[i]); } }}void print_path2(Graph g, int index)//这里 直接传递最后位置的索引 { if (path[index] != NOTEXIST) { print_path2(g, path[index]); printf("->"); } printf("%c", g.vex[index].data);}int main(){ Graph g; int start, end; char ch1, ch2; create_graph(&g); printf("请输入起始点与终点:\n"); ch1 = read_char(); ch2 = read_char(); start = get_pos(g, ch1); end = get_pos(g, ch2); init_graph(g, start); unweight_path(g, start); end = get_pos(g, ch2); print_path(g, end); //print_path2(g, end); //print_graph(g); getchar(); getchar(); return 0;}
你可能感兴趣的文章
Web前端学习笔记——JavaScript之对象
查看>>
Web前端学习笔记——JavaScript之数组、函数、作用域
查看>>
Web前端学习笔记——JavaScript之变量、操作符、表达式和语句
查看>>
Web前端学习笔记——JavaScript之WEBAPI、BOM、DOM及获取页面元素
查看>>
Web前端学习笔记——JavaScript之特效
查看>>
Web前端学习笔记——JavaScript之事件详解
查看>>
Web前端学习笔记——JavaScript之事件、创建元素、节点操作
查看>>
Web前端学习笔记——JavaScript之正则表达式、伪数组、垃圾回收
查看>>
Web前端学习笔记——JavaScript 之继承、函数进阶
查看>>
Web前端学习笔记——JavaScript之面向对象游戏案例：贪吃蛇
查看>>
Web前端学习笔记——JavaScript之面向对象编程
查看>>
上海控安成功举办普陀区科普创新专项智能网联车学术活动
查看>>
控安轩辕实验室：利用开源项目实现定位和时间欺骗（二）
查看>>
基于预测的自动驾驶全球导航卫星系统欺骗攻击检测
查看>>
上海工业互联网协会安全专委会成立，加快提升工业互联网安全保障能力
查看>>
普陀区委副书记顾军、区政府副区长魏静带队调研上海控安
查看>>
上海市水务工控系统安全联合研究实验室正式启用
查看>>
基于数字孪生的水务系统安全试验床正式上线
查看>>
上海控安成功入选“2020年度上海市工业互联网平台和专业服务商推荐目录”
查看>>
多传感器融合定位是否足够安全？(一)
查看>>