作业帮用矩阵表示一个图形,矩阵中为1的部分表示该两点间有连接,怎样根据矩阵来求任意两点间的最短距离的数量啊
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/04 05:53:10
用矩阵表示一个图形,矩阵中为1的部分表示该两点间有连接,怎样根据矩阵来求任意两点间的最短距离的数量啊
用矩阵表示一个图形,矩阵中为1的部分表示该两点间有连接,怎样根据矩阵来求任意两点间的最短距离的数量啊
用矩阵表示一个图形,矩阵中为1的部分表示该两点间有连接,怎样根据矩阵来求任意两点间的最短距离的数量啊
其实你可以换种方法来做,这种做的话比较困难.可以再思考下.
就是把整个的图像来表示吧，整个区域就是一个数组。
当方块来到的时候就把图像当中的所在位置变为1。
好像一个长条数组为Long[4][4],它的颜色位置为
Long[1][0]、Long[1][1]、Long[1][2]、Long[1][3]。
当它去到其中一个位置，就把当中位置的背景区域变为
ARER[X][Y]=Long[1][0]
ARER[X]...
全部展开
就是把整个的图像来表示吧，整个区域就是一个数组。
当方块来到的时候就把图像当中的所在位置变为1。
好像一个长条数组为Long[4][4],它的颜色位置为
Long[1][0]、Long[1][1]、Long[1][2]、Long[1][3]。
当它去到其中一个位置，就把当中位置的背景区域变为
ARER[X][Y]=Long[1][0]
ARER[X][Y+1]=Long[1][1]
ARER[X][Y+2]=Long[1][2]
ARER[X][Y+3]=Long[1][3]
而整个图像的表示方法就是IF(p==1)为色块颜色、IF(p==0)为背景色
收起
对任意的n阶方阵A，令B = (A+A')/2，C = (A-A')/2，则容易验证
A = B + C
并且B是对称的(B'=B)，C是反对称的(C'=-C)。
这里X'表示X的转置。
其实你可以换种方法来做，这种做的话比较困难。可以再思考下。。
行列式的值是该行列式所代表的有向区域的体积（或者是面积、长度），比如一阶行列式代表的是一个“线元”（可以理解为一个矢量）的有向长度，而二阶行列式自然的就表示着一个面元（平面单元可以看作是由两个线元的矢量积）的有向面积，而三阶行列式对应着空间的一个平行六面体的有向体积...以此类推。
如果一个行列式的值为一，则说明这个行列式所代表的有向的n维多面体的体积为单位一，即它和一个单位矩阵（主元为一...
全部展开
行列式的值是该行列式所代表的有向区域的体积（或者是面积、长度），比如一阶行列式代表的是一个“线元”（可以理解为一个矢量）的有向长度，而二阶行列式自然的就表示着一个面元（平面单元可以看作是由两个线元的矢量积）的有向面积，而三阶行列式对应着空间的一个平行六面体的有向体积...以此类推。
如果一个行列式的值为一，则说明这个行列式所代表的有向的n维多面体的体积为单位一，即它和一个单位矩阵（主元为一其他为零）所代表的正n方体(n>3是不太好理解，反正是各条边彼此垂直)体积相同。
下面说下三类初等矩阵，
第一类：某一行或某一列乘以k,这是要把多面体的某一条边加倍；
第二类：交换行或列，可以理解为把一块积木正着摆换成侧着摆，或者躺着摆，这不影响体积变化。
第三类：这是一种剪切变化，好像有一副扑克牌，本来整齐叠在一起，然后从一个方向推它，让他层与层之间发生侧移（错位），从而变成了平行四边形，但不会影响它的体积（这很容易想到，你没有增加or减少扑克牌的数量）
最后，对于一个行列式，值为一（体积不变），这就好像是为你准备好一摞扑克牌，要你全部用上，不多一张不少一张，把它组合堆积在一起形成一个整体，当然你可以先让它变成最初的整齐排列（如同单位行列式那样），然后你在慢慢的一步一步推动它...很好想象了吧....
收起
就是把整个的图像来表示吧，整个区域就是一个数组。
当方块来到的时候就把图像当中的所在位置变为1。
好像一个长条数组为Long[4][4],它的颜色位置为
Long[1][0]、Long[1][1]、Long[1][2]、Long[1][3]。
当它去到其中一个位置，就把当中位置的背景区域变为
ARER[X][Y]=Long[1][0]
ARER[X]...
全部展开
就是把整个的图像来表示吧，整个区域就是一个数组。
当方块来到的时候就把图像当中的所在位置变为1。
好像一个长条数组为Long[4][4],它的颜色位置为
Long[1][0]、Long[1][1]、Long[1][2]、Long[1][3]。
当它去到其中一个位置，就把当中位置的背景区域变为
ARER[X][Y]=Long[1][0]
ARER[X][Y+1]=Long[1][1]
ARER[X][Y+2]=Long[1][2]
ARER[X][Y+3]=Long[1][3]
而整个图像的表示方法就是IF(p==1)为色块颜色、IF(p==0)为背景色
收起
假设8个方位被简单定义为 char a[8];
int path(point *location)
{
if(“location不为出口”&&“location.a[0]未涉足过”)
path(location->a[0]);
else if(“location不为出口”&&“location.a[1]未涉足过”)
p...
全部展开
假设8个方位被简单定义为 char a[8];
int path(point *location)
{
if(“location不为出口”&&“location.a[0]未涉足过”)
path(location->a[0]);
else if(“location不为出口”&&“location.a[1]未涉足过”)
path(location->a[0]);
else if(“location不为出口”&&“location.a[2]未涉足过”)
path(location->a[0]);
` ````````````````````
``````````
``````
``
else return 0;
}
这是一个迭代过程，需要对每一个方位的位置都遍历一遍，也是一个深度优先的遍历过程。
我在这只给lz一个示意，具体的算法在《数据结构》的书上基本都有，蛮经典的。希望能对lz有所帮组。
加油！
收起
将城市看成是点，城市之间的距离看成是点之间的权值。
下面是PRIM算法实现的最小生成树代码。，利用邻接矩阵存储边的信息。程序已通过编译了，可以直接运行。
#include <stdio.h>
#include <string.h>
typedef int VRType;
typedef char InfoType;
#defi...
全部展开
将城市看成是点，城市之间的距离看成是点之间的权值。
下面是PRIM算法实现的最小生成树代码。，利用邻接矩阵存储边的信息。程序已通过编译了，可以直接运行。
#include <stdio.h>
#include <string.h>
typedef int VRType;
typedef char InfoType;
#define MAX_NAME 3
/*顶点字符串的最大长度+1*/
#define MAX_INFO 20
/*相关信息字符串的最大长度+1*/
typedef char VertexType[MAX_NAME];
#define INFINITY 32767
/*用整型最大值代替无穷大*/
#define MAX_VERTEX_NUM 20
/*最大顶点个数*/
typedef enum{DG,DN,AG,AN} GraphKind;
/*{有向图，有向网，无向图，无向网}*/
typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int ShortPathTable[MAX_VERTEX_NUM];
typedef struct
{
VRType adj;
/*顶点关系类型。对无权图，用1（是）或0(否）表示相邻否*/
/*对带全图，则为权值类型*/
InfoType *info;
/*该弧相关信息的指针（可无）*/
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM];
/*顶点向量*/
AdjMatrix arcs;
/*邻接矩阵*/
int vexnum,arcnum;
/*图的当前顶点数和弧数*/
GraphKind kind;
/*图的种类标志*/
}MGraph;
int LocateVex(MGraph G,VertexType u)
{ /*初始条件：图G存在，u和G中顶点有相同特征*/
/*操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1*/
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vexs[i])==0)
return i;
return -1;
}
int CreateAN(MGraph *G)
{/*采用数组（邻接矩阵）表示法，构造无向网G*/
int i,j,k,w,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("please input number of acmes and arcs in G,and there is some information in arc,if yes is 1,else is 0:");
scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("please input the value of %d acmes(<%d character):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i)
/*构造顶点向量*/
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i)
/*初始化邻接矩阵*/
for(j=0;j<(*G).vexnum;++j)
{(*G).arcs[i][j].adj=INFINITY;
/*网*/
(*G).arcs[i][j].info=NULL;
}
printf("please input %d the first and the second of acr and weigh:\n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s %s %d",va,vb,&w);
/*%*c吃掉回车符*/
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=w;
/*无向*/
if(IncInfo)
{
printf("please input some information about the arc(<%d character): ",MAX_INFO);
gets(s);
w=strlen(s);
if(w)
{
info=(char*)malloc((w+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[i][j].info=(*G).arcs[j][i].info=info;
/*无向*/
}
}
}
(*G).kind=DN;
return 1;
}
typedef struct
{/*记录从顶点集U到V-U的代价最小的边的辅助数组定义*/
VertexType adjvex;
VRType lowcost;
}minside[MAX_VERTEX_NUM];
int mininum(minside SZ,MGraph G)
{/*求closedege,lowcost的最小正值*/
int i=0,j,k,min;
while(!SZ[i].lowcost)
i++;
min=SZ[i].lowcost;
k=i;
for(j=i+1;j<G.vexnum;j++)
if(SZ[j].lowcost>0)
if(min>SZ[j].lowcost)
{
min=SZ[j].lowcost;
k=j;
}
return k;
}
void MiniSpanTree_PRIM(MGraph G,VertexType u)
{/*用普利姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边*/
int i,j,k;
minside closedge;
k=LocateVex(G,u);
for(j=0;j<G.vexnum;++j)
/*辅助数组初始化*/
{
if(j!=k)
{ strcpy(closedge[j].adjvex,u);
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
closedge[k].lowcost=0;
/*初始U={n}*/
printf("zuixiaodaijiashengchengshudegetiaobianwei:\n");
for(i=1;i<G.vexnum;++i)
{/*选择其余G.vexnum-1个顶点*/
k=mininum(closedge,G);
/*求出T的下一个结点：第K顶点*/
printf("(%s-%s)\n",closedge[k].adjvex,G.vexs[k]);
/*输出生成树的边*/
closedge[k].lowcost=0;
/*第K顶点并入U集*/
for(j=0;j<G.vexnum;++j)
if(G.arcs[k][j].adj<closedge[j].lowcost)
{/*新顶点并入U集后重新选择最小边*/
strcpy(closedge[j].adjvex,G.vexs[k]);
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
}
void main()
{
MGraph G;
CreateAN(&G);
MiniSpanTree_PRIM(G,G.vexs[0]);
getch();
}
收起
好好看看运筹学里的邻接矩阵、权矩阵 根据lz要求，最合适的是floyd算法 下面就是根据这个算法写的代码，lz可以自己改成函数 D=[0 1 0 1 0 0 1