C语音算法图的广度优先算法实现代码

[求进程调度算法]进程调度源程序如下： jingchendiaodu.cpp #include ＂stdio.h＂ #include#include#define getpch(type) (type*)malloc(sizeof(type)) #define NULL 0 struct pcb { /* 定义进程...+阅读

深度优先遍历算法（Depth-first-search），重点关注的是图的连通性（connectivity），即从图中给定的一点都能访问到哪些点。不仅如此，在遍历这些点的过程中，通过记录访问次序，可以实现其他功能，比如测试该图是否有闭环等。广度优先遍历算法（Breadth-first-search），是为了寻找两个节点之间的最短路径。如果把图中每一点看作是一个乒乓球，每一条边都用线连起来，那么提起图中的某一点，即可形成一棵广度优先遍历树。

在学习C的过程中，Valgrind是一个很好的工具，用来测试有没有内存泄漏，对提高自己的代码质量有很大的帮助！具体代码如下： graph.h [cpp] view plaincopyprint? #ifndef H_GRAPH #define H_GRAPH typedef struct _node { char *data; char flag; struct _node **adjacency_nodes; int alength; } vertex; typedef struct _graph { vertex **node_list; int length; } graph; #endif #ifndef H_GRAPH #define H_GRAPH typedef struct _node { char *data; char flag; struct _node **adjacency_nodes; int alength; } vertex; typedef struct _graph { vertex **node_list; int length; } graph; #endif dfs.h [cpp] view plaincopyprint? #ifndef H_DFS #define H_DFS #include ＂graph.h＂ char **pre, **post; int explore(vertex *); int previsit(vertex *); int postvisit(vertex *); int dfs(graph *); int explore(vertex *node) { if (node->flag == 1) return; previsit(node); int i = 0; while (i++alength) { explore(*node->adjacency_nodes++); } postvisit(node); } int previsit(vertex *node) { *pre = (char *)malloc(sizeof(char)); *pre++ = node->data; } int postvisit(vertex *node) { *post = (char *)malloc(sizeof(char)); *post++ = node->data; node->flag = 1; } int dfs(graph *list) { int i = 0; while (i++length & (*list->node_list)->flag == 0 ) explore(*list->node_list++); } #endif #ifndef H_DFS #define H_DFS #include ＂graph.h＂ char **pre, **post; int explore(vertex *); int previsit(vertex *); int postvisit(vertex *); int dfs(graph *); int explore(vertex *node) { if (node->flag == 1) return; previsit(node); int i = 0; while (i++alength) { explore(*node->adjacency_nodes++); } postvisit(node); } int previsit(vertex *node) { *pre = (char *)malloc(sizeof(char)); *pre++ = node->data; } int postvisit(vertex *node) { *post = (char *)malloc(sizeof(char)); *post++ = node->data; node->flag = 1; } int dfs(graph *list) { int i = 0; while (i++length & (*list->node_list)->flag == 0 ) explore(*list->node_list++); } #endif queue.h [cpp] view plaincopyprint? #ifndef H_QUEUE #define H_QUEUE #includetypedef struct _nodes { vertex *data; struct _nodes *next; } node; typedef struct _queue { int length; node *front; node *end; } queue; int push(queue *, vertex *); int pop(queue *); int push(queue *q, vertex *v) { node *element; element = (node *)malloc(sizeof(node)); element->data = v; element->next = NULL; if (q->length == 0) { q->front = element; q->end = element; } else { node *temp; temp = q->front; while (temp->next != NULL) temp = temp->next; temp->next = element; q->end = element; } q->length++; } int pop(queue *q) { if (q->length == 0) return -1; node *temp; temp = q->front; q->front = q->front->next; q->length--; if (q->length == 1) q->end = NULL; free(temp); } #endif #ifndef H_QUEUE #define H_QUEUE #includetypedef struct _nodes { vertex *data; struct _nodes *next; } node; typedef struct _queue { int length; node *front; node *end; } queue; int push(queue *, vertex *); int pop(queue *); int push(queue *q, vertex *v) { node *element; element = (node *)malloc(sizeof(node)); element->data = v; element->next = NULL; if (q->length == 0) { q->front = element; q->end = element; } else { node *temp; temp = q->front; while (temp->next != NULL) temp = temp->next; temp->next = element; q->end = element; } q->length++; } int pop(queue *q) { if (q->length == 0) return -1; node *temp; temp = q->front; q->front = q->front->next; q->length--; if (q->length == 1) q->end = NULL; free(temp); } #endif bfs.h [cpp] view plaincopyprint? #ifndef H_BFS #define H_BFS #include ＂graph.h＂ #include ＂queue.h＂ #includeint bfs(graph *); int bfs(graph *g) { queue q; q.length = 0; push(&q, g->node_list[0]); int i; vertex *temp; temp = g->node_list[0]; while (q.length >0) { if (temp->alength >0) { for (i = 0; ialength; i++) push(&q, temp->adjacency_nodes[i]); temp = temp->adjacency_nodes[0]; } pop(&q); } } #endif