| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛 | 
登录
注册
用户控制面板
搜索
道具
风格
短消息
论坛展区
帮助
编程论坛 → 开发语言 → 『 数据结构与算法 』 → [开源]有向图和无向图的基本操作(VC)
我的收件箱(0)
欢迎加入我们，一同切磋技术
用户名：   
 
密　码：  
共有 2980 人关注过本帖
标题：[开源]有向图和无向图的基本操作(VC)
只看楼主 加入收藏
longfeng867
Rank: 1
来　自：重庆
等　级：新手上路
威　望：1
帖　子：182
专家分：0
注　册：2007-5-20
楼主
收藏
 问题点数：0 回复次数：5 
[开源]有向图和无向图的基本操作(VC)
I0KM6OL1.rar (4.34 KB) [开源]有向图和无向图的基本操作(VC)


运行环境：VC
//有向图,无向图基本操作,包括:
1、邻接矩阵
2、邻接表
3、深度优先遍历
4、广度优先遍历
5、最小生成树
6、拓扑排序
7、每一对顶点之间的最短路径（Dijkstra,Floyd两种算法）

有疑问的地方可以发邮件或MSN:longfeng867@163.com.

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <limits.h>
#define MaxStr 20
#define inf 999
typedef int Status ;
typedef int ElemType ;
typedef struct
{
ElemType VNode ;
int indgree ;
}
VexType ;
typedef struct Arc
{
VexType Adj ;
unsigned int Weight ;
struct Arc*NextArc ;
}
ArcType ;
typedef struct
{
VexType*Vex ;
ArcType**FirstArc ;
//顶点总数;
int VexNums ;
//边数
int ArcNums ;

}
DLGraph ;
//图的邻接表结构定义;
typedef struct
{
ElemType*Vex ;
int kind ;
unsigned int**Arc ;
int VexNums ;
int ArcNums ;
}
DMGraph ;
//图的邻接矩阵结构定义;
//========================================================================================
Status Create(DMGraph*DMG);
Status CreateDMGraph(DMGraph*DMG);
//创建图的邻接矩阵;
Status DMG_Traver(DMGraph DMG);
//邻接矩阵的遍历;
Status DMG_DFS(DMGraph DMG,int v,int*Visited);
//邻接矩阵深度遍历(递 归);
Status DMG_DFS_Uni(DMGraph DMG,int v,int*Visited);
//邻接矩阵深度遍历(非递归);
Status DMG_BFS(DMGraph DMG,int v,int*Visited);
//邻接矩阵广度遍历;
Status DMG2DLG(DMGraph DMG,DLGraph*DLG);
//邻接矩阵转换为邻接表;
Status DLG_Traver(DLGraph DLG);
//邻 接 表的遍历;
Status DLG_DFS(DLGraph DLG,int v,int*Visited);
//邻 接 表深度遍历(递 归);
Status DLG_DFS_Uni(DLGraph DLG,int v,int*Visited);
//邻 接 表深度遍历(非递归);
Status DLG_BFS(DLGraph DLG,int v,int*Visited);
//邻 接 表广度遍历;
//---------------------------------------------------------
Status Topsort(DLGraph DLG,ElemType**ts);
//邻接表有向图的Topsort;
Status Dijkstra(DMGraph DMG,ElemType v,unsigned int*dist);
//Dijkstra;
Status PRN_DK(DMGraph DMG,unsigned int***dis);
//输出Dijkstra算法;
Status Floyd(DMGraph DMG,unsigned int***flyd);
//Floyd;
Status PRN_DMGraph(DMGraph DMG);
//输出邻接矩阵;
Status PRN_DLGraph(DLGraph DLG);
//输出邻接表;
//========================================================================================
/*最小生成树*/
Status Prim(DMGraph*g)
{
int closest[MaxStr],i,j,k,min ;
unsigned int lowcost[MaxStr];
//VexNums个顶点，VexNums-1条边
for(i=2;i<=g->VexNums;i++)
{
lowcost[i]=g->Arc[1][i];
//初始化
closest[i]=1 ;
//顶点未加入到最小生成树
}
lowcost[1]=0 ;
//标志顶点1加入U集合
//形成VexNums-1条边的生成
for(i=2;i<=g->VexNums;i++)
{
min=inf ;
k=0 ;
//寻找满足边的一个顶点在U,另一个顶点在V的最小边
for(j=2;j<=g->VexNums;j++)if((lowcost[j]<min)&&(lowcost[j]!=0))
{
min=lowcost[j];
k=j ;
}
printf("(%d,%d)%d\t",closest[k],k,min);
lowcost[k]=0 ;
//顶点k加入U
//修改由顶点k到其他顶点边的路径
for(j=2;j<=g->VexNums;j++)if(g->Arc[k][j]<lowcost[j])
{
lowcost[j]=g->Arc[k][j];
closest[j]=k ;
}
printf("\n");
}
return 0 ;
}
//========================================================================================
void Menu(DMGraph DMG,DLGraph DLG)
{
char c ;
int i,j ;
unsigned int**dist,**flyd ;
ElemType*ts ;
for(;;)
{
printf("\t　 ╭──────────────────────╮\n");
printf("\t ｜ 图的基本操作实现 ｜\n");
printf("\t　 ｜──────────────────────｜\n");
printf("\t ｜ 1__邻接矩阵 ｜\n");
printf("\t　 ｜──────────────────────｜\n");
printf("\t ｜ 2__邻接表 ｜\n");
printf("\t　 ｜──────────────────────｜\n");
printf("\t ｜ 3__深度优先搜索 ｜\n");
printf("\t　 ｜──────────────────────｜\n");
printf("\t ｜ 4__广度优先搜索 ｜\n");
printf("\t　 ｜──────────────────────｜\n");
printf("\t ｜ 5__最小生成树 ｜\n");
printf("\t　 ｜──────────────────────｜\n");
printf("\t ｜ 6__拓扑排序 ｜\n");
printf("\t　 ｜──────────────────────｜\n");
printf("\t ｜ 7__每一对顶点之间的最短路径 ｜\n");
printf("\t　 ｜──────────────────────｜\n");
printf("\t ｜ 8__返回重新操作... ｜\n");
printf("\t　 ｜──────────────────────｜\n");
printf("\t ｜ Q__退出程序... ｜\n");
printf("\t ╰──────────────────────╯\n");
printf("\t 请选择图的实现:\t");
scanf("%s",&c);
switch(c)
{
case '1' :
system("cls");
printf(" 图的邻接矩阵：\n");
PRN_DMGraph(DMG);
system("pause");
system("cls");
break ;
case '2' :
system("cls");
printf("\n\n 邻接矩阵转换为邻接表：\n");
DMG2DLG(DMG,&DLG);
PRN_DLGraph(DLG);
printf("\n");
system("pause");
system("cls");
break ;
case '3' :
system("cls");
DMG_Traver(DMG);
printf("\n");
system("pause");
system("cls");
break ;
case '4' :
system("cls");
DLG_Traver(DLG);
printf("#");
printf("\n");
system("pause");
system("cls");
break ;
case '5' :
system("cls");
if(DMG.kind==2)
Prim(&DMG);
if(DMG.kind==1)
printf("\n\n\n\n\t\t\t Error: 不能最小生成数树!!!\n");
system("pause");
system("cls");
break ;
case '6' :
system("cls");
printf("\n\n 图的拓扑排序：\n");
Topsort(DLG,&ts);
printf("\n\n\n");
system("pause");
system("cls");
break ;
case '7' :
system("cls");
printf("\n 图的各点最短路径：\n\n 1. Dijkstra(迪杰斯特拉算法):\n");
PRN_DK(DMG,&dist);
printf("\n\n");
system("pause");
system("cls");
printf(" 2. Floyd(弗洛伊德算法):\n");
Floyd(DMG,&flyd);
printf("\n\n");
system("pause");
system("cls");
printf("\nDijkstra最短路径测试输出：\n 某两点 ： 最短路径");
for(i=1;i<=DMG.VexNums;i++)
for(j=1;j<=DMG.VexNums;j++)
if(dist[i][j]<INT_MAX&&j!=i)
printf("\n[%2d,%2d] : %5d ",i,j,dist[i][j]);
printf("\n\n");
system("pause");
system("cls");
printf("\nFloyd最短路径测试输出：\n 某两点 ： 最短路径");
for(i=1;i<=DMG.VexNums;i++)
for(j=1;j<=DMG.VexNums;j++)
if(flyd[i][j]<INT_MAX&&j!=i)
printf("\n[%2d,%2d] : %5d ",i,j,flyd[i][j]);
printf("\n\n");
system("pause");
system("cls");
break ;
case '8' :
system("cls");
Create(&DMG);
system("cls");
break ;
case 'Q' :
case 'q' :
system("cls");
printf("\n\n\n\n\t\t\t 谢 谢 使 用!!!\n");
printf("\t\t\t");
exit(0);
break ;
default :
printf("输入有错,请重试!!!\n");
getch();
system("cls");
break ;
}
}
}
DMGraph DMG ;
DLGraph DLG ;
int main(void)
{
Create(&DMG);
system("cls");
Menu(DMG,DLG);
return 0 ;
}
//========================================================================================
//创建无向图
Status CreateDMGraph1(DMGraph*g)
{
int i,j,k,l,v1,v2,w ;
printf("\n请输入要创建的顶点数:");
scanf("%d",&g->VexNums);
printf("\n请输入要创建的边数:");
scanf("%d",&g->ArcNums);
if(!(g->Vex=(ElemType*)malloc((g->VexNums+1)*sizeof(ElemType))))
{
printf("\n内存溢出。");
return 1 ;
}
if(!(g->Arc=(unsigned int**)malloc((g->VexNums+1)*sizeof(unsigned int*))))
{
printf("\n内存溢出。");
return 1 ;
}
printf("无向图的接点的代号为:");
for(i=1;i<=g->VexNums;i++)
{
g->Vex[i]=i ;
if(!(g->Arc[i]=(unsigned int*)malloc((g->VexNums+1)*sizeof(unsigned int))))
{
printf("\n内存溢出。");
return 1 ;
}
for(j=1;j<=g->VexNums;j++)
{
g->Arc[i][j]=INT_MAX ;
}
printf("%d ",g->Vex[i]);
}
printf("\n");
for(j=1;j<=g->VexNums;j++)
for(k=1;k<=g->VexNums;k++)
g->Arc[j][k]=inf ;
//邻接矩阵初始化
for(l=1;l<=g->ArcNums;l++)
{
loop1 :
;
printf("\n输入第%d条边的起点v1(1-%d):",l,g->VexNums);
scanf("%d",&v1);
if(v1<0||v1>g->VexNums)
{
printf("\t\t\tError: 超出范围,重新输入!!!\n");
goto loop1 ;
}
loop :
;
printf("\n输入第%d条边的终点v2(1-%d):",l,g->VexNums);
scanf("%d",&v2);
if(v2<0||v2>g->VexNums||v1==v2)
{
printf("\t\t\tError: 超出范围或输入不合法,重新输入!!!\n");
goto loop ;
}
printf("\n输入第%d条边的路径w(编号为数字):",l);
scanf("%d",&w);
g->Arc[v1][v2]=w ;
g->Arc[v2][v1]=w ;
}
return 0 ;
}
//==========================================================================
//创建图的邻接矩阵;
Status CreateDMGraph(DMGraph*DMG)
{
int i,j,k,w ;
printf("请输入有向图的顶点数目:");
scanf("%d",&DMG->VexNums);
printf("\n请输入要创建的边数:");
scanf("%d",&DMG->ArcNums);
if(!(DMG->Vex=(ElemType*)malloc((DMG->VexNums+1)*sizeof(ElemType))))
{
printf("\n内存溢出。");
return 1 ;
}
if(!(DMG->Arc=(unsigned int**)malloc((DMG->VexNums+1)*sizeof(unsigned int*))))
{
printf("\n内存溢出。");
return 1 ;
}
//邻接矩阵初始化;
printf("有向图的接点代号为:");
for(i=1;i<=DMG->VexNums;i++)
{
DMG->Vex[i]=i ;
if(!(DMG->Arc[i]=(unsigned int*)malloc((DMG->VexNums+1)*sizeof(unsigned int))))
{
printf("\n内存溢出。");
return 1 ;
}
for(j=1;j<=DMG->VexNums;j++)
{
DMG->Arc[i][j]=INT_MAX ;
}
printf("%d ",DMG->Vex[i]);
}
printf("\n");
for(i=1;i<=DMG->ArcNums;i++)
{
loop1 :
;
printf("请输入第%d组边的起点(1-%d):",i,DMG->VexNums);
scanf("%d",&k);
if(k<0||k>DMG->VexNums)
{
printf("\t\t\tError: 超出范围,重新输入!!!\n");
goto loop1 ;
}
loop :
;
printf("请输入第%d组边的终点(1-%d):",i,DMG->VexNums);
scanf("%d",&j);
if(j<0||j>DMG->VexNums||j==k)
{
printf("\t\t\tError: 超出范围或输入不合法,重新输入!!!\n");
goto loop ;
}
printf("请输入第%d组边的路径:",i);
scanf("%d",&w);
DMG->Arc[k][j]=w ;
}
return 0 ;
}
//====================================================================
//创建图的邻接矩阵;
Status Create(DMGraph*DMG)
{
char c ;
loop :
;
printf("\n\n\n");
printf("\t　 ╭─────────────────────╮\n");
printf("\t ｜ 图的基本操作实现 ｜\n");
printf("\t　 ｜─────────────────────｜\n");
printf("\t ｜ 1、有向图 ｜\n");
printf("\t　 ｜─────────────────────｜\n");
printf("\t ｜ 2、无向图 ｜\n");
printf("\t　 ｜─────────────────────｜\n");
printf("\t ｜ 3、退 出 ｜\n");
printf("\t ╰─────────────────────╯\n");
printf("\t 请选择:");
scanf("%s",&c);
if(c=='2')
{
DMG->kind=2 ;
system("cls");
CreateDMGraph1(DMG);
system("cls");
}
else if(c=='1')
{
DMG->kind=1 ;
system("cls");
CreateDMGraph(DMG);
system("cls");
}
else if(c=='3')
{
system("cls");
printf("\n\n\n\n\t\t\t 谢 谢 使 用!!!\n");
printf("\t\t\t");
exit(0);
}
else
{
printf("\t\t Error: 输入错误,请重新选择!!!\n");
getch();
system("cls");
goto loop ;
}
return 0 ;
}
//========================================================================================

[此贴子已经被作者于2007-10-10 10:44:39编辑过]

搜索更多相关主题的帖子: 有向图　开源　
2007-09-29 15:06
aipb2OO7
Rank: 1
等　级：新手上路
帖　子：41
专家分：0
注　册：2007-8-30
第 2 楼
收藏
 得分:0 
正在看这些，收藏了！

[glow=255,yellow,5]菜鸟一个.以后靠你们了..[/glow]
2007-09-29 20:00
longfeng867
Rank: 1
来　自：重庆
等　级：新手上路
威　望：1
帖　子：182
专家分：0
注　册：2007-5-20
第 3 楼
收藏
 得分:0 
大家看了还是给点指点啊~~~
//图的邻接矩阵转换为邻接表;
Status DMG2DLG(DMGraph DMG,DLGraph*DLG)
{
int i,j ;
ArcType*p=NULL ;
DLG->VexNums=DMG.VexNums ;
if(!(DLG->Vex=(VexType*)malloc((DLG->VexNums+1)*sizeof(VexType))))
{
printf("\n内存溢出。");
return 1 ;
}
if(!(DLG->FirstArc=(ArcType**)malloc((DLG->VexNums+1)*sizeof(ArcType*))))
{
printf("\n内存溢出。");
return 1 ;
}
for(i=1;i<=DLG->VexNums;i++)
{
DLG->Vex[i].VNode=DMG.Vex[i];
DLG->FirstArc[i]=NULL ;
DLG->Vex[i].indgree=0 ;
for(j=1;j<=DMG.VexNums;j++)
{
if(DMG.Arc[i][j]<INT_MAX)
{
if(!(p=(ArcType*)malloc(sizeof(ArcType))))
{
printf("\n内存溢出。");
return 1 ;
}
p->Adj.VNode=DMG.Vex[j];
p->Weight=DMG.Arc[i][j];
p->NextArc=DLG->FirstArc[i];
DLG->FirstArc[i]=p ;
}
}
for(j=1;j<=DMG.VexNums;j++)
{
if(DMG.Arc[j][i]<INT_MAX)
++DLG->Vex[i].indgree ;
}
}
return 0 ;
}
//========================================================================================
//邻接矩阵的遍历;
Status DMG_Traver(DMGraph DMG)
{
int i,*Visited ;
if(!(Visited=(int*)malloc((DMG.VexNums+1)*sizeof(int))))
{
printf("\n内存溢出。");
return 1 ;
}
printf("\n 图的深度优先搜索：\n递 归：");
for(i=1;i<=DMG.VexNums;i++)
Visited[i]=0 ;
for(i=1;i<=DMG.VexNums;i++)
if(Visited[i]==0)
DMG_DFS(DMG,i,Visited);
printf("#");
printf("\n非递归：");
for(i=1;i<=DMG.VexNums;i++)
Visited[i]=0 ;
for(i=1;i<=DMG.VexNums;i++)
if(Visited[i]==0)
DMG_DFS_Uni(DMG,i,Visited);
printf("#");
return 0 ;
}
//========================================================================================
//邻 接 表的广度优先遍历;
Status DLG_Traver(DLGraph DLG)
{
int i,*Visited ;
if(!(Visited=(int*)malloc((DLG.VexNums+1)*sizeof(int))))
{
printf("\n内存溢出。");
return 1 ;
}
printf("\n\n 图的广度遍历：\n\t");
for(i=1;i<=DLG.VexNums;i++)
Visited[i]=0 ;
for(i=1;i<=DLG.VexNums;i++)
if(Visited[i]==0)
DLG_BFS(DLG,i,Visited);
return 0 ;
}
//========================================================================================
//邻接矩阵深度遍历(递 归);
Status DMG_DFS(DMGraph DMG,int v,int*Visited)
{
int i ;
Visited[v]=1 ;
printf("%2d-->",v);
for(i=1;i<=DMG.VexNums;i++)
if(Visited[i]==0&&DMG.Arc[v][i]<INT_MAX)
DMG_DFS(DMG,i,Visited);
return 0 ;
}
//========================================================================================
//邻接矩阵深度遍历(非递归);
Status DMG_DFS_Uni(DMGraph DMG,int v,int*Visited)
{
int i,*Stack,top=-1 ;
if(!(Stack=(int*)malloc((DMG.VexNums+1)*sizeof(int))))
{
printf("\n内存溢出。");
return 1 ;
}
Visited[v]=1 ;
printf("%2d-->",v);
Stack[++top]=v ;
while(top!=-1)
{
for(i=1;i<=DMG.VexNums;i++)
if(Visited[i]==0&&DMG.Arc[Stack[top]][i]<INT_MAX)
{
Visited[i]=1 ;
printf("%2d-->",i);
Stack[++top]=i ;
break ;
}
if(i==DMG.VexNums+1)
--top ;
}
return 0 ;
}
//========================================================================================
//邻 接 表广度遍历;
Status DLG_BFS(DLGraph DLG,int v,int*Visited)
{
ArcType*p=NULL ;
int*Queue,rear,front ;
if(!(Queue=(int*)malloc((DLG.VexNums+1)*sizeof(int))))
{
printf("\n内存溢出。");
return 1 ;
}
rear=front=0 ;
Visited[v]=1 ;
printf("%2d -->",v);
rear=(rear+1)%DLG.VexNums ;
Queue[rear]=v ;
while(rear!=front)
{
front=(front+1)%DLG.VexNums ;
p=DLG.FirstArc[Queue[front]];
while(p!=NULL)
{
if(Visited[p->Adj.VNode]==0)
{
Visited[p->Adj.VNode]=1 ;
printf("%2d-->",p->Adj);
rear=(rear+1)%DLG.VexNums ;
Queue[rear]=p->Adj.VNode ;
}
p=p->NextArc ;
}

}
return 0 ;
}
//========================================================================================
//邻接表有向图的Topsort拓扑排序;
Status Topsort(DLGraph DLG,ElemType**ts)
{
int i,j,k,m=0,top=-1 ;
ArcType*tp,*p ;
if(!(*ts=(ElemType*)malloc((DLG.VexNums+1)*sizeof(ElemType))))
{
printf("\n内存溢出。");
return 1 ;
}
if(!(tp=(ArcType*)malloc((DLG.VexNums+1)*sizeof(ArcType))))
{
printf("\n内存溢出。");
return 1 ;
}
printf(" Topsort：\n\n ");
//初始化tp;
for(i=1;i<=DLG.VexNums;i++)
{
tp[i].Adj.VNode=DLG.Vex[i].VNode ;
tp[i].NextArc=DLG.FirstArc[i];
tp[i].Adj.indgree=DLG.Vex[i].indgree ;
if(DLG.Vex[i].indgree==0)
{
tp[i].Adj.indgree=top ;
top=i ;
}
}
while(top!=-1)
{
j=top ;
top=tp[top].Adj.indgree ;
printf("%2d ,",tp[j].Adj.VNode);
++m ;
p=tp[j].NextArc ;
while(p!=NULL)
{
k=p->Adj.VNode ;
--tp[k].Adj.indgree ;
if(tp[k].Adj.indgree==0)
{
tp[k].Adj.indgree=top ;
top=k ;
}
p=p->NextArc ;
}
}
if(m<DLG.VexNums)
printf("\n\t\t不能拓扑!\n");
return 0 ;
}
//========================================================================================
//输出Dijkstra最短路径;
Status PRN_DK(DMGraph DMG,unsigned int***dis)
{
int i,j,flag ;
unsigned int**dist ;
if(!(dist=(unsigned int**)malloc((DMG.VexNums+1)*sizeof(unsigned int*))))
{
printf("\n内存溢出。");
return 1 ;
}
*dis=dist ;
for(i=1;i<=DMG.VexNums;i++)
{
if(!(dist[i]=(unsigned int*)malloc((DMG.VexNums+1)*sizeof(unsigned int))))
{
printf("\n内存溢出。");
return 1 ;
}
Dijkstra(DMG,i,dist[i]);
//Dijkstra最短路径;
}
for(i=1;i<=DMG.VexNums;i++)
{
flag=0 ;
printf("\n从%d出发的最短路径：",i);
for(j=1;j<=DMG.VexNums;j++)
{
if(j!=i&&dist[i][j]<INT_MAX)
{
printf("\n\t自%d ==>%d点,路径长:%d",i,j,dist[i][j]);
flag=1 ;
}
}
if(flag==0)
printf("\n\t没有任何路径...");
}
return 0 ;
}
//========================================================================================
//最短路径Dijkstra(迪杰斯特拉);
Status Dijkstra(DMGraph DMG,ElemType v,unsigned int*dist)
{
int i,j,t ;
ElemType*flag ;
unsigned int min ;
if(!(flag=(ElemType*)malloc((DMG.VexNums+1)*sizeof(ElemType))))
{
printf("\n内存溢出。");
return 1 ;
}
//初始化,置U={v}到V-U到各点最短路径;
for(i=1;i<=DMG.VexNums;i++)
{
flag[i]=0 ;
dist[i]=DMG.Arc[v][i];
}
flag[v]=1 ;
//v并入U;
for(i=1;i<=DMG.VexNums;i++)
{
min=INT_MAX ;
t=i ;
//找到U到V-U最小路径(最短路径);
for(j=1;j<=DMG.VexNums;j++)
{
if(flag[j]==0&&min>dist[j])
{
min=dist[j];
t=j ;
}
}
flag[t]=1 ;
//t并入U;
//重置U到V-U各点最短路径;
for(j=1;j<=DMG.VexNums;j++)
{
if(flag[j]==0&&dist[t]+DMG.Arc[t][j]<dist[j])
{
dist[j]=dist[t]+DMG.Arc[t][j];
}
}
}
return 0 ;
}
//========================================================================================
//Floyd(弗洛伊德)最短路径;
Status Floyd(DMGraph DMG,unsigned int***flyd)
{
int i,j,k,**Path=NULL ;
unsigned int**Weight=NULL ;
if(!(Path=(int**)malloc((DMG.VexNums+1)*sizeof(int*))))
{
printf("\n内存溢出。");
return 1 ;
}
if(!(Weight=(unsigned int**)malloc((DMG.VexNums+1)*sizeof(unsigned int*))))
{
printf("\n内存溢出。");
return 1 ;
}
*flyd=Weight ;
//初始化;
for(i=1;i<=DMG.VexNums;i++)
{
if(!(Path[i]=(int*)malloc((DMG.VexNums+1)*sizeof(int))))
{
printf("\n内存溢出。");
return 1 ;
}
if(!(Weight[i]=(unsigned int*)malloc((DMG.VexNums+1)*sizeof(unsigned int))))
{
printf("\n内存溢出。");
return 1 ;
}
for(j=1;j<=DMG.VexNums;j++)
{
Weight[i][j]=DMG.Arc[i][j];
Path[i][j]=0 ;
}
}
//Floyd迭代算法;
for(k=1;k<=DMG.VexNums;k++)
for(i=1;i<=DMG.VexNums;i++)
for(j=1;j<=DMG.VexNums;j++)
if(Weight[i][j]>(Weight[i][k]+Weight[k][j]))
{
Weight[i][j]=Weight[i][k]+Weight[k][j];
Path[i][j]=k ;
}
//输出;
for(i=1;i<=DMG.VexNums;i++)
{
printf("\n从%d出发的最短路径：",i);
for(j=1;j<=DMG.VexNums;j++)
{
if(j!=i&&Weight[i][j]<INT_MAX)
printf("\n\t自%d ==>%d点,路径:%4d",i,j,Weight[i][j]);
}
}
return 0 ;
}
//========================================================================================
//输出邻接矩阵;
Status PRN_DMGraph(DMGraph DMG)
{
int i,j ;
for(i=1;i<=DMG.VexNums;i++)
{
printf("\n\t");
for(j=1;j<=DMG.VexNums;j++)
{
if(DMG.Arc[i][j]<INT_MAX)
printf(" %3d ",DMG.Arc[i][j]);
else
printf(" ∞ ");
}
printf("\n");
}
return 0 ;
}
//========================================================================================
//输出邻接表;
Status PRN_DLGraph(DLGraph DLG)
{
int i ;
ArcType*p=NULL ;
for(i=1;i<=DLG.VexNums;i++)
{
printf("\n %2d(入度%d) ==>",i,DLG.Vex[i].indgree);
p=DLG.FirstArc[i];
while(p!=NULL)
{
if(p->NextArc)
printf("%d(%d)-->",p->Adj.VNode,p->Weight);
else printf("%d(%d)",p->Adj.VNode,p->Weight);
p=p->NextArc ;
}

}
return 0 ;
}

[此贴子已经被作者于2007-10-10 10:32:49编辑过]


在这个连处女膜都可以伪造的世界里,还有什么值得我相信!
2007-10-10 10:29
云中游子
Rank: 1
等　级：新手上路
帖　子：6
专家分：0
注　册：2012-12-18
第 4 楼
收藏
 得分:0 
高手
2012-12-18 23:25
云中游子
Rank: 1
等　级：新手上路
帖　子：6
专家分：0
注　册：2012-12-18
第 5 楼
收藏
 得分:0 
虽然我看不太懂，但是我运行了，你的无向图功能结果是错误的
2012-12-19 22:15
快速回复：[开源]有向图和无向图的基本操作(VC)
数据加载中...
 
　　　



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有，并保留所有权利。
Powered by Discuz, Processed in 0.046152 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved