你是大二的计算机学生，实在不清楚你是否学过“代数组合”，你这个问题用代数组合的方式处理是最方便的，算一下k个矩阵相乘即可——设矩阵A的第i行第j列的整数为从顶点i到顶点j的路径数（特别的，矩阵对角线全部设为零，反正你不要回路），那么A的k次方这个矩阵的第i行第j列整数就表示从顶点i到顶点j长度为k的路径数，这个不难证明的自己琢磨一下就好了，矩阵相乘的程序很简单的，你如果对代数组合或者这类图计算比较感兴趣，那就给你一本书吧，上传不了附件如果需要留个邮箱我发给你。
/
图的遍历演示
以邻接多重表为存储结构,实现连通无向图的深度优先和广度优先遍历
以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集
/
#include<iostream>
# include <stringh>
# include <malloch>
# include <conioh>
using namespace std;
int visited[30];
# define MAX_VERTEX_NUM 30
# define OK 1
//typedef int VertexType;
typedef int InfoType;
typedef struct ArcNode //弧
{
int adjvex;
struct ArcNode nextarc;
}ArcNode;
typedef struct VNode//表头
{
int data;
ArcNode firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct//图
{
AdjList vertices;
int vexnum,arcnum;
int kind;
}ALGraph;
void CreateDG(ALGraph &G)
{
int k,i,v1;
cout<<endl<<"请输入结点个数: ";
cin>>Gvexnum;
cout<<"请输入弧的个数: ";
cin>>Garcnum;
for(i=1;i<=Gvexnum;i++)//初使化表头
{
Gvertices[i]data=i;
Gvertices[i]firstarc=NULL;
}
for(k=1;k<=Gvexnum;k++) //输入边
{
int v2;
cout<<"请输入与结点"<<k<<"相邻的边数:";
cin>>v2;
cout<<"请输入与第"<<k<<"个结点相连的结点编号: ";
cin>>v1;
ArcNode p;
p=(ArcNode)malloc(sizeof(ArcNode));
if(!p) exit(-1);
p->adjvex=v1;
p->nextarc=NULL;
Gvertices[k]firstarc=p;
for(int i=1;i<v2;i++)
{
int m;
cout<<"请输入与第"<<k<<"个结点相连的结点编号: ";
cin>>m;
ArcNode q;
q=(ArcNode )malloc(sizeof(ArcNode));//动态指针
if(!q) exit(-1);
q->adjvex=m; //顶点给P
q->nextarc=NULL;
p->nextarc=q;
p=q;
//free(q);
}
//free(p);
}
}
void DFS (ALGraph G,int v )//深度搜索
{
visited[v]=1;
cout<<Gvertices[v]data<<" ";
ArcNode x;
x=(ArcNode)malloc(sizeof(ArcNode));
if(!x) exit(-1);
x=Gvertices[v]firstarc;
int w;
for (;x;x=x->nextarc)
{ w=x->adjvex;
if(visited[w]==0)
DFS(G,w);
}
}
void DFSB (ALGraph G,int v)//深度搜索的边集
{
visited[v]=1;
ArcNode y;
y=(ArcNode)malloc(sizeof(ArcNode));
if(!y) exit(-1);
y=Gvertices[v]firstarc;
int u=Gvertices[v]data;
int w;
for(;y;y=y->nextarc)
{ w=y->adjvex;
if(visited[w]==0)
{
cout<<u<<"--->"<<w<<endl;
DFSB(G,w);
}
}
}
typedef struct QNode
{
int data;
QNode next;
}QNode,QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
void InitQueue (LinkQueue &Q)//建立一个空队列
{
Qfront=Qrear=(QueuePtr)malloc(sizeof(QNode));
if(!Qfront) exit(-1);
Qfront->next=NULL;
}
void EnQueue (LinkQueue &Q,int e)//进队
{
QNode p;
p=(QNode)malloc(sizeof(QNode));
if(!p) exit(-1);
p->data=e;
p->next=NULL;
Qrear->next=p;
Qrear=p;
//free(p);
}
int DeQueue (LinkQueue &Q,int &e)//出队
{
if(Qfront==Qrear)
return -1;
QNode p;
p=(QNode)malloc(sizeof(QNode));
if(!p) exit(-1);
p=Qfront->next;
e=p->data;
Qfront->next=p->next;
if(Qrear==p)
Qrear=Qfront;
free(p);
return e;
}
int QueueEmpty (LinkQueue Q)//判断队列是否为空
{
if(Qfront==Qrear)
return 1;
return 0;
}
void BFS(ALGraph G,int v)//广度搜索
{
int u;
LinkQueue Q;
InitQueue(Q);
if(visited[v]==0)
{
visited[v]=1;
cout<<Gvertices[v]data<<" ";
EnQueue(Q,v);
while(QueueEmpty(Q)!=1)
{
DeQueue(Q,u);
ArcNode z;
z=(ArcNode)malloc(sizeof(ArcNode));
if(!z) exit(-1);
z=Gvertices[u]firstarc;
/
for(int w=z->adjvex;w>=0;w=z->nextarc->adjvex)
{
if(visited[w]==0)
{
visited[w]=1;
cout<<w<<" ";
EnQueue(Q,w);
}
}/
int w;
for(;z;z=z->nextarc)
{ w=z->adjvex;
if(visited[w]==0)
{
visited[w]=1;
cout<<w<<" ";
EnQueue(Q,w);
}
}
}
}
}
void BFSB (ALGraph G,int v)//广度搜索的边集
{
int u;
LinkQueue Q;
InitQueue(Q);
if(visited[v]==0)
{
visited[v]=1;
EnQueue(Q,v);
while(QueueEmpty(Q)!=1)
{
DeQueue(Q,u);
ArcNode r;
r=(ArcNode)malloc(sizeof(ArcNode));
if(!r) exit(-1);
r=Gvertices[u]firstarc;
int w;
for(;r!=NULL;r=r->nextarc)
{ w=r->adjvex;
if(visited[w]==0)
{
visited[w]=1;
cout<<u<<"--->"<<w<<endl;
EnQueue(Q,w);
}
}
}
}
}
int main()
{
int i;
ALGraph G;
CreateDG(G);
int x;
cout<<"请输入结点数:";
cin>>x;
cout<<"邻接表为："<<endl;
for(int j=1;j<=x;j++)
{
cout<<Gvertices[j]data<<" ";
ArcNode p;
p=(ArcNode)malloc(sizeof(ArcNode));
if(!p) exit(-1);
p=Gvertices[j]firstarc;
while(p)
{
cout<<p->adjvex<<" ";
p=p->nextarc;
}
cout<<endl;
}
cout<<"请输入第一个要访问的结点序号："<<endl;
int n;
cin>>n;
for( i=0;i<30;i++)
visited[i]=0;
cout<<"广度搜索："<<endl;
BFS(G,n);
for( i=0;i<30;i++)
visited[i]=0;
cout<<endl;
cout<<"边集："<<endl;
BFSB(G,n);
for( i=0;i<30;i++)
visited[i]=0;
cout<<"深度搜索："<<endl;
DFS(G,n);
for( i=0;i<30;i++)
visited[i]=0;
cout<<endl;
cout<<"边集："<<endl;
DFSB(G,n);
//system("pause");
return 0;
}
前几天上机刚好做了这个,个人感觉很完美,尽管老师说用的是邻接表而不是多重表,太简单,但还不错,界面输入过程比较繁琐,要严格按照提示来输入,是无向图,等级太低,没办法把执行结果粘出来,应该能看懂吧
根据lz要求，最合适的是floyd算法
下面就是根据这个算法写的代码，lz可以自己改成函数
D=[0 1 0 1 0 0
1 0 1 0 0 0
0 1 0 1 1 1
1 0 1 0 1 0
0 0 1 1 0 1
0 0 1 0 1 0];
n=length(D);
for k=1:n
for i=1:n
for j=1:n
if 0<D(i,k) & 0<D(k,j)
if D(i,j)==0 & i~=j
D(i,j)=D(i,k)+D(k,j);
else
D(i,j)=min(D(i,j),D(i,k)+D(k,j));
end
end
end
end
end
答案就储存在D矩阵当中，这里
D =
0 1 2 1 2 3
1 0 1 2 2 2
2 1 0 1 1 1
1 2 1 0 1 2
2 2 1 1 0 1
3 2 1 2 1 0
算法为O(n3)的，256^3=2^24 大概等于1600万
效率上完全能够忍受。
参考楼上给的链接，稍微做了一点修改，供参考。
修改的地方包括：
1、原程序为函数，提供了邻接矩阵和关联矩阵的双向转换，这里针对楼主的需求改为脚本，直接运行即可将邻接矩阵转为关联矩阵。
2、部分语句修改更符合MATLAB的通行写法，如：
sum(sum(F))改为sum(F(:))，
W(i,k)=1; W(j,k)=1;改为W([i j],k)=1;
3、考虑到邻接矩阵为对称阵，第二个for循环改为只针对半个矩阵，减少计算量（对于楼主的这个具体作用微乎其微）。
4、原程序有错误，在else分支fprint为fprintf之误（其实我看到该程序的第一眼就注意到了这个错误，担心还存在其它问题，所以进行了改写）。
F=[0 1 1 1;1 0 1 1;1 1 0 1;1 1 1 0]; % 邻接矩阵
m = sum(F(:))/2; % 图的边数
n = size(F,1); % 顶点数
W = zeros(n,m);
k=1;
for i = 1:n
for j = 1:i
if F(i,j)~=0
W([i j],k)=1;
k = k + 1;
end
end
end
W
以上就是关于在以邻接矩阵方式存储的有向图G中求顶点i到顶点j的不含回路的,长度为k的路径数的完整程序全部的内容，包括:在以邻接矩阵方式存储的有向图G中求顶点i到顶点j的不含回路的,长度为k的路径数的完整程序、编程实现以邻接表或邻接矩阵为存储结构，图的广度和深度优先搜索、求邻接矩阵任意两点间的最短距离。matlab。程序在下面有没有哪位大神能给解释一下后边的是什么意思等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）