求助关于图的矩阵表示的程序（离散数学）
求助关于图的矩阵表示的程序（离散数学）
用c语言编写,能够实现下列功能.任意给定一个图,能够求得此图的邻接矩阵,距离矩阵,可达矩阵,关联矩阵.任意给定一个图,能够判断这个图是否是欧拉图,平面图,树.
要求：首先要输入一个节点关系；屏幕文字提示并等待.并能够辨别出集合中节点的个数,并能将图画出来.程序必须能够求解这些节点关系的如下性质：邻接矩阵,可达矩阵,关联矩阵,距离矩阵,判定欧拉图,平面图,或者有向树.
选择完成：根据要求计算任何两个节点之间特定长度的节点的数量；判定哈密顿图；对节点进行着色；求出最小生成树.
编程；首先哪个讲节点关表示成矩阵形式,例如,输入可以采用逐个询问有序对,利用字母加逗号方式.输入完成采用输入特定符号方式.
// z2.cpp :Defines the entry point for the console application.
//
#include "stdafx.h"
//#include
//void main()
//{
#define MAXNUM 30
#define INFINITY 10000
#define FALSE 0
#define TRUE 1
#define BACK -1
#include "stdio.h"
#include
#include "malloc.h"
typedef struct{
char vexs[MAXNUM];
int edges[MAXNUM][MAXNUM];
int n,e;
}Mgraph;
void CreateGraph(Mgraph *g)
{
int i,j,k,w;
char ch;
printf("请输入结点数与弧数,如：3,2：");
scanf("%d,%d",&(g->n),&(g->e));
for(i=0;in;i++)
{
for(j=0;jn;j++)
{
if(i==j){
g->edges[i][j]=0;
}else
{
g->edges[i][j]=INFINITY;
}
}
}
//获取权值
printf("\n为方便演示,结点内容默认为结点序号,无需输入.\n\n下面请输入弧及权值,例如：若点0到1有弧可达,且权值为10,则输入:0,1,10.注意：输入时不区分弧的顺序.\n");
for(k=0;ke;k++){
printf("\t请输入第%d个弧及权值：",k+1);
scanf("%d,%d,%d",&i,&j,&w);
g->edges[i][j]=w;
}
//输出邻接矩阵
printf("\n邻接矩阵：\n",k);
for(i=0;in;i++){
printf("\t");
for(j=0;jn;j++){
if(g->edges[i][j]>=INFINITY){
printf("∞\t");
}else{
printf("%d\t",g->edges[i][j]);
}
}
printf("\n");
}
}
void ShortPath(Mgraph *g,int v0)
{
/*定义多个变量与数组,其中R数组为记录路径的数组,iterator为游标,
D为距离数组,final数组记录是否已取到最短路径
*/
int i,j,v,w,min;
int R[MAXNUM][MAXNUM];
int iterator[MAXNUM];
int D[MAXNUM];
int final[MAXNUM];
//初始化游标为零
for(i=0;in; ++v){
final[v] = FALSE;
D[v] = g->edges[v0][v];
}
//初始化v0的路径距离为零,设置已获取最短路径
D[v0] = 0;
final[v0] = TRUE;
//主循环,获取其他的最短路径
for(i = 1;i n; ++i){
min = INFINITY;
//寻找最小的D[w]
for(w = 0;w n; ++w){
if(final[w] != TRUE){
if(D[w]n; ++w){
if((final[w] != TRUE) && (min+g->edges[v][w] //更新路径
iterator[w]=iterator[v];
for(j=0;jedges[v][w];
}
}
}
//若final始终为FALSE,则不可达
for(w = 0;wn; ++w){
if(final[w] != TRUE){
printf("\t点%d到点%d不可达\n",v0,w);
}
}
}
//主方法
void main()
{
Mgraph * g;
int i=0;
g=(Mgraph *)malloc(sizeof(Mgraph));
printf("该程序实现了Dijkstra算法,支持路径显示,请按提示输入数据：\n\n");
CreateGraph(g);
printf("\n最小路径判断(以0点为起点)：\n");
ShortPath(g,0);
getchar();
}