数据结构-图的邻接表表示（C语言）

数据结构-图的邻接表表示（C语言）
数据结构-图的邻接表表示（C语言）

数据结构-图的邻接表表示（C语言）

// grap_theory.cpp : 定义控制台应用程序的入口点.

//

//#include "stdafx.h" //VS2010头文件

#include<stdio.h>

#define NTOTAL (26*4) //最大路径数目

#define MAX_DISTANCE  10000.0

struct piont{

int line_adjacency_list;

int num_piont;

int test_num[2];

char from[NTOTAL];

char to[NTOTAL];

char all_piont[NTOTAL];

int  all_piont_num[NTOTAL];

float distance[NTOTAL];

float distance_all[NTOTAL][NTOTAL];

};//结构体定义

void read(piont *test){

int i;

char temp[100];

scanf("%d",&test->line_adjacency_list);//读取行数

gets(temp);//读取回车字符

for(i=0;i<test->line_adjacency_list;i++){//读取列表

scanf("%c %c %f",&test->from[i],&test->to[i],&test->distance[i]);

gets(temp);//读取回车字符

}

scanf("%c %c",&test->from[i],&test->to[i]);//读取短短路径名称

}

void cal_num_piont(piont *test){

int i,j;

int from_num,to_num;

test->num_piont=0;

for(i=0;i<NTOTAL;i++){

test->all_piont_num[i]=0;//点的度数清零

test->distance_all[i][i]=0.0;

for(j=i+1;j<NTOTAL;j++){

test->distance_all[i][j]=MAX_DISTANCE;

test->distance_all[j][i]=MAX_DISTANCE;

}

}

for(i=0;i<test->line_adjacency_list;i++){

//判断from

for(j=0;j<test->num_piont;j++){

if(test->from[i]==test->all_piont[j]){

from_num=j;

test->all_piont_num[j]++;

break;

}

}

if(j==test->num_piont){

test->all_piont[j]=test->from[i];

from_num=j;

test->all_piont_num[j]++;

test->num_piont++;

}

//判断end

for(j=0;j<test->num_piont;j++){

if(test->to[i]==test->all_piont[j]){

to_num=j;

test->all_piont_num[j]++;

break;

}

}

if(j==test->num_piont){

test->all_piont[j]=test->to[i];

to_num=j;

test->all_piont_num[j]++;

test->num_piont++;

}

test->distance_all[from_num][to_num]=test->distance[i];

test->distance_all[to_num][from_num]=test->distance[i];

}

//判断所求点的位置

for(i=0;i<test->num_piont;i++){

if(test->from[test->line_adjacency_list]==test->all_piont[i])

test->test_num[0]=i;

if(test->to[test->line_adjacency_list]==test->all_piont[i])

test->test_num[1]=i;

}

}

float min_distance(piont *test){

int i,j,k,n;

float min_dis;

float dis_i_k_add_k_j;

n=test->num_piont;

//Floyd-Warshall算法

for(k=0;k<n;k++){

for(i=0;i<n;i++){

for(j=0;j<n;j++){

dis_i_k_add_k_j=(test->distance_all[i][k]+test->distance_all[k][j]);

if(test->distance_all[i][j]>dis_i_k_add_k_j)

test->distance_all[i][j]=dis_i_k_add_k_j;

}

}

}

min_dis=test->distance_all[test->test_num[0]][test->test_num[1]]; 

return min_dis;

}

void test_printf(piont *test,float min_dis){

int i;

printf("%d\n",test->num_piont);

for(i=0;i<test->num_piont;i++){

printf("%d\n",test->all_piont_num[i]);

}

printf("%-8.0f\n",min_dis);

}

void main()

{

float min_dis;

piont test1;//结构体声明

read(&test1);

cal_num_piont(&test1);

min_dis=min_distance(&test1);

test_printf(&test1,min_dis);

}