c写的贪心算法，利用指针来搜索最短路径，以及可以扩展成一般最短路径的求法.zip

#include<stdlib.h> #include<stdio.h> #include<time.h> #undef TRUE #undef FALSE #define TRUE 1 #define FALSE 0 #define MAX_WEIGHT 200 typedef int boolean; typedef struct { int **h_graph; int vertex_num; boolean *final; } hamilton_graph; typedef struct { int *cycle; //最优路径 int weigth; //最优路径权值 int top; //栈顶 } hamilton_graph_cycle; boolean hamilton_graphs_initial(hamilton_graph * graph,int vertex) { int i; if (graph==NULL) return FALSE; graph->vertex_num=0; if ((graph->final=(boolean *)malloc(vertex*sizeof(boolean)))==NULL) return FALSE; if ((graph->h_graph=(int **)malloc(vertex*sizeof(int *)))==NULL) return FALSE; for (i=0; i<vertex; i++) { if ((graph->h_graph[i]=(int *)malloc(vertex*sizeof(int)))==NULL) return FALSE; graph->final[i]=FALSE; } return TRUE; } boolean hamilton_graphs_delete(hamilton_graph * graph,int vertex) { int i; if (graph==NULL) return FALSE; graph->vertex_num=0; free(graph->final); graph->final=NULL; for (i=0; i<vertex; i++) { free(graph->h_graph[i]); graph->h_graph[i]=NULL; } free(graph->h_graph); graph->h_graph=NULL; return TRUE; } boolean hamilton_graph_new(hamilton_graph * graph,int vertex) { int i,j,temp=0; if (graph==NULL) return FALSE; graph->vertex_num=vertex; srand(time(NULL)); for (i=0; i<vertex; i++) { for (j=temp; j<vertex; j++) { if (i==j) graph->h_graph[i][j]=MAX_WEIGHT; else { graph->h_graph[i][j]=(int)(100*rand()/(RAND_MAX+1.0));//保证1到100. graph->h_graph[j][i]=graph->h_graph[i][j]; } } temp++; } return TRUE; } hamilton_graph_cycle greedy_algorithm_hamilton_cycle(hamilton_graph *graph) { hamilton_graph_cycle *temp_cycle; int i,j,min_weight,temp_vexrtex,count=0; if (graph==NULL) return ; if ((temp_cycle->cycle=(int *)malloc(graph->vertex_num*sizeof(int)))==NULL) //注意释放 return ; temp_cycle->weigth=0; temp_cycle->top=-1; for (i=0; i<graph->vertex_num&&count<graph->vertex_num; count++) { for (j=0; j<graph->vertex_num; j++) { if (graph->final[j]==FALSE) min_weight=graph->h_graph[i][j]; } for (j=0; j<graph->vertex_num; j++) { if (graph->final[j]==FALSE) { if (graph->h_graph[i][j]<=min_weight) { min_weight=graph->h_graph[i][j]; temp_vexrtex=j; } } } temp_cycle->top++; temp_cycle->cycle[temp_cycle->top]=temp_vexrtex; //记录要并入的顶点 graph->final[temp_vexrtex]=TRUE; temp_cycle->weigth+=graph->h_graph[i][temp_vexrtex]; i=temp_vexrtex; } //free(temp_cycle->cycle); //temp_cycle->cycle=NULL; return *temp_cycle; } int main(void) { int i,j; hamilton_graph graph ; hamilton_graph_cycle mycycle; hamilton_graphs_initial(&graph,10); hamilton_graph_new(&graph,10); for (i=0; i<10; i++) { for (j=0; j<10; j++) printf("%4d ",graph.h_graph[i][j]); printf("\n"); } mycycle=greedy_algorithm_hamilton_cycle(&graph); for (j=0; j<10; j++) printf("%2d ",mycycle.cycle[i]); printf("%d",mycycle.weigth); hamilton_graphs_delete(&graph,10); }