キーパス探索(C言語)
24882 ワード
キーパスは、キーボードからエッジ単位で入力された所定の工事施工図に対して、その図のキーパスを見つけることができるプログラムを記述する.コードは次のとおりです.
#include <stdio.h>
#include <stdlib.h>
struct TU
{
int index;
int dut;
int vex;
char act[5];
struct TU *link;
};
struct TU s[100];
struct TU *p;
struct TU *creat()
{
int i =0;
int a,d,v,u;
struct TU *p;
printf("
");
while(1)
{
printf(" , (u,a),(u == 0 )
");
scanf("%d,%d",&u,&a);
if(u == 0)
break;
else
{
i = i+1;
s[i].index = a;
s[i].vex = u;
s[i].link = NULL;
printf(" , , (act v,d),( 0 )
");
while(1)
{
p = (struct TU *)malloc(sizeof(struct TU));
scanf("%s%d,%d",&p->act,&v,&d);
if(d == 0 || v ==0)
break;
else
{
p->dut = d;
p->vex = v;
p->link = s[i].link;
s[i].link = p;
}
}
}
}
s[0].vex = i;
return 0;
};
void topsort()
{
int vltop = 0,vetop = 0;
int i,b=1;
int m = 0,n,j,k,endnode;
n = s[0].vex;/* */
int Ve[n];
int Vl[n];
for(int i = 1;i<=n;i++)
{
if(s[i].index == 0)
{
s[i].index = vetop;
vetop = i;
}
Ve[i] = 0;
}
/* */
while(vetop !=0)
{
j = vetop;
m = m+1;
vetop = s[vetop].index;
s[j].index = vltop;
vltop = j;
p = s[j].link;
while(p)
{
k = p->vex;
s[k].index = s[k].index -1;
if(s[k].index == 0)
{
s[k].index = vetop;
vetop = k;
}
if(Ve[k]<Ve[j]+p->dut)
Ve[k] = Ve[j]+p->dut;
p = p->link;
}
}
if(m<n)
{
printf("
");
return;
}
endnode = vltop;
for(int i = 1;i<=endnode;i++)
Vl[i] = Ve[endnode];
/* */
while(vltop != 0)
{
j = vltop;
vltop = s[vltop].index;
p = s[j].link;
while(p)
{
k = p->vex;
if(Vl[j]>Vl[k]-(p->dut))
Vl[j] = Vl[k]-p->dut;
p = p->link;
}
}
for(i = 1;i<=n;i++)
printf("Ve(%d)= %d, Vl(%d)=%d
",i,Ve[i],i,Vl[i]);
printf("
");
for(b=1;b<=s[0].vex;b++)
{
if(Ve[b]==Vl[b])
{
printf("V(%d)->",b);
}
}
printf("
");
}
int main()
{
struct TU *p;
creat();
printf("
");
for(int i = 1;i<=s[0].vex;i++)
{
printf("s[%d]=%d/ ",i,s[i].vex);
p = s[i].link;
while(p)
{
printf("-%s-[%d(%d)]",p->act,p->vex,p->dut);
p = p->link;
}
printf("
");
}
topsort();
return 0;
}