const int Max_vertex=5
const int Max_Edge=8
int visited[Max_vertex+1]//访问标志数组
struct ArcNode
{
int adjvex
ArcNode *nextarc //指向下一条弧
}
struct Vnode
{
int v//顶点信息
ArcNode *next
}a[Max_vertex+1]
/* 无向图的建立 */
void creategraph()
{
int i,j,k
ArcNode *s
//初始化
for(i=1i<=Max_vertexi++)
{
a[i].v=i
a[i].next=NULL
}
/*以头插法建立 */
for(k=1k<=Max_Edgek++)
{
cout<<"请输入第"<<k<<"条边:"
cin>>i>>j
if(i>9||i<0||j<0||j>9)
{
cout<<"输入错误!!\n"<<endl
break
}
else{
cout<<endl
s=new ArcNode
s->adjvex=j
s->nextarc=a[i].next
a[i].next=s
s=new ArcNode
s->adjvex=i
s->nextarc=a[j].next
a[j].next=s
}
}
}
void display()
{
ArcNode *p
cout<<"你建立的图为:"<<endl
for(int i=1i<=Max_vertexi++)
{
p=a[i].next
cout<<a[i].v<<"->"
while(p->nextarc!=NULL)
{
cout<<p->adjvex<<"->"
p=p->nextarc
}
cout<<p->adjvex<<endl
}
}
void main()
{
cout<<"/******\t本算法以关插法建立无向图的邻接表为例!\t******/"<<endl
char yn='y'int k
creategraph()
display()
}
// 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=0i<test->line_adjacency_listi++){//读取列表
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=0i<NTOTALi++){
test->all_piont_num[i]=0//点的度数清零
test->distance_all[i][i]=0.0
for(j=i+1j<NTOTALj++){
test->distance_all[i][j]=MAX_DISTANCE
test->distance_all[j][i]=MAX_DISTANCE
}
}
for(i=0i<test->line_adjacency_listi++){
//判断from
for(j=0j<test->num_piontj++){
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=0j<test->num_piontj++){
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=0i<test->num_pionti++){
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=0k<nk++){
for(i=0i<ni++){
for(j=0j<nj++){
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=0i<test->num_pionti++){
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)
}
