データ構造の簡単な授業の無方向図の簡単な経路を覚える
4018 ワード
2つの要件のみ:
1)無方向図における始点から終点までのすべての単純な経路を求める.ここで、始点と終点はユーザが自分で設定することができる.
2)無方向図における始点から終点までの指定長さ(例えばK)の全ての単純パスを求める.ここで始点と終点はユーザが自ら設定することができる.
1)無方向図における始点から終点までのすべての単純な経路を求める.ここで、始点と終点はユーザが自分で設定することができる.
2)無方向図における始点から終点までの指定長さ(例えばK)の全ての単純パスを求める.ここで始点と終点はユーザが自ら設定することができる.
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define MAXV 100 //
int visited[MAXV];
//
typedef struct
{
int no; //
int info; //
}Vertextype; //
typedef struct
{
int edges[MAXV][MAXV];//
int n,e; // ,
Vertextype vexs[MAXV];//
}Mgraph;
//
typedef struct Anode //
{
int adjvex; //
struct Anode *next;//
int info;//
}ArcNode;
typedef struct Vnode
{
int data; //
ArcNode * first;//
}Vnode;
typedef struct
{
Vnode adjlist[MAXV];//
int n,e;// ,
}AlGraph;
void Change(Mgraph g,AlGraph *&G)//
{
int i,j,n =g.n;
ArcNode *p;
G= (AlGraph *)malloc(sizeof(AlGraph));
for(i=0;iadjlist[i].first = NULL;
}
for(i=0;i=0;j--) //
{
if(g.edges[i][j]!=0)
{
p=(ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;//
p->info = g.edges[i][j];//
p->next = G->adjlist[i].first;
G->adjlist[i].first = p;//
}
}
G->n = n;//
G->e =g.e;//
}
void DisADJ(AlGraph *G)//
{
int i;
ArcNode *p;
printf("************ *************
");
for(i = 0;in;i++)
{
p=G->adjlist[i].first;//
if(p!=NULL)printf("%d: ",i);
while(p!=NULL)
{
printf("%3d",p->adjvex);
p=p->next;
}
printf("
");
}
}
void showways1(AlGraph *G,int x,int y,int path[],int i)//
{
ArcNode *p;
int j,n;
visited[x] = 1;//
p=G->adjlist[x].first;
while(p!=NULL)
{
n=p->adjvex;
if(n==y) //
{
path[i+1] = y;
for(j=0;j<=i+1;j++)
printf(" %3d",path[j]);
printf("
");
}
else if(visited[n]==0) //
{
path[i+1] = n;//
showways1(G,n,y,path,i+1); //
}
p=p->next;
}
visited[x] =0;
}
void showways2(Mgraph g,int x,int y,int path[],int i)//
{
visited[x]=1;//
int j;
path[i] = x;//
for(j = 0;jadjlist[x].first;
while(p!=NULL) //
{
m = p->adjvex;
if(visited[m]==0)//
showways3(G,m,y,l,path,d);
p=p->next;
}
visited[x] = 0;
}
void showways4(Mgraph g,int x,int y,int l,int path[],int d)
{
visited[x]=1;
int j;
d++;
path[d] = x;
for(j = 0;j>g.edges[i][j];
}
break;
}
}
G =(AlGraph *)malloc(sizeof(AlGraph));
Change(g,G); //
DisADJ(G);//
printf("**************** ***********************
");
int k,u,v,m;
int path[MAXV];
printf("1.
");
printf("2.
");
printf("**********************************************
");
while(true){
for(i=0;i