8.6. .

 


, ( ). (), . . ( ) ( ), (, ) ( ). , , (, , ..). , , . .

. 86-1.

. . , . i,j m Aij=m, . , . :

 

int A[7][7]={

{ 0, 5, 8, 0, 0, 0, 0},

{ 5, 0, 0,12, 0, 9, 0},

{ 8, 0, 0, 0, 8, 4, 2},

{ 0,12, 0, 0, 3, 6, 0},

{ 0, 0, 8, 3, 0, 0, 7},

{ 0, 9, 4, 6, 0, 0, 0},

{ 0, 0, 2, 0, 7, 0, 0}};

. . .

 

struct link2 { int v1,v2,lnt; }

A[]={{0,1,5},{0,2,8},{1,3,12},{1,5,9},{3,5,6},

{2,5,4},{3,4,3},{2,4,8},{2,6,2},{4,6,7} ,{-1,-1,0}};

, . , , .

 

struct link4{ int v2; lnt;};

link4 a0[]={{1,5},{2,8},{-1,-1}};

link4 a1[]={{0,5},{3,12},{5,9},{-1,-1}};

link4 a2[]={{0,8},{4,8},{5,4},{6,2},{-1,-1}};

link4 a3[]={{1,12},{4,3},{5,6},{-1,-1}};

link4 a4[]={{2,8},{3,3},{6,7},{-1,-1}};

link4 a5[]={{1,9},{2,4},{3,6},{-1,-1}};

link4 a5[]={{2,2},{4,7},{-1,-1}};

link *pp[]={a0,a1,a2,a3,a4,a5,a6};

 

struct link3{

int v2,lnt;

link3 *next; };

//--------------------------------------------------------------------------86-01.cpp

//

link3 **create(int *pp[],int N){

int i,j;

link3 **M=new link3*[N];

for (i=0;i<N;i++) M[i]=NULL;

for (i=0;i<N;i++)

for (j=0;j<N;j++)

if (pp[i][j]!=0){

int vv2,l2;

link3 *q=new link3(j,pp[i][j]);

q->next=M[i]; M[i]=q;

}

return M;}

. (. 3.4) . :

        , T=O(N2), N , . , ;

        , , . , m , T=O((m-1)N).

. , (), . (). , . . , .

//--------------------------------------------------------------------------86-01.cpp

//--- ,

void scan_1(int i,int **M, int n, int D[]){

D[i]=1;

for (int j=0;j<n;j++)

if (M[i][j]!=0 && D[j]==0) scan_1(j,M,n,D);

D[i]=0;}

//--- ,

void scan_2(int i,link2 M[], int D[]){

D[i]=1;

for (int j=0; M[j].v1!=-1;j++){

if (M[j].v1==i && D[M[j].v2]==0) scan_2(M[j].v2,M,D);

if (M[j].v2==i && D[M[j].v1]==0) scan_2(M[j].v1,M,D);

}

D[i]=0;}

//--- ,

void scan_3(int i,link3 *M[], int n, int D[]){

D[i]=1;

link3 *q;

for (q=M[i];q!=NULL;q=q->next)

if (D[q->v2]==0) scan_3(q->v2,M,n,D);

D[i]=0;}

//--- ,

void scan_4(int i,link4 *M[], int n, int D[]){

D[i]=1;

for (int j=0;M[i][j].v2!=-1;j++)

if (D[M[i][j].v2]==0) scan_4(M[i][j].v2,M,n,D);

D[i]=0;}

. D, . , . .

(. 7.4). : ( ) () .

, . , , .. . .

. . - Di. , ( ) :

        ( ) Di=, D0=0, ;

        k Sk, ;

        , , Di=Dk+Mk,i , , Di.

 

//-------------------------------------------------------------------86-02.cpp

// -

void min_way(int N, int **M){

int i,k,j;

int *P=new int[N],*D=new int[N];

for (i=0;i<N;i++) P[i]=0,D[i]=100000; //

D[0]=0; // , - 0

while(1){

for (k=-1,i=0;i<N;i++){

if (P[i]==1) continue; //

if (k==-1 || D[i] < D[k])

k=i; } //

if (k==-1) break; //

P[k]=1; //

for (i=0;i<N;i++){

if (M[k][i]==0) continue; //

if (D[k] + M[k][i] < D[i]) // -

D[i] = D[k] + M[k][i];

}}

. :

        , Di , ;

        , , Di, ;

        Di;

        .

. -. , . , . , , . ( ). ( , ) . : ( ) - . .

 

//------------------------------------------------------86-03.cpp

// - -

// " "-" "

#include "86-00.cpp"

void main(){

int N,**M,*P,i,k,j;

int sum=0,sum0=0;

if ((M=load_1("86-011.txt",N))==NULL) return;

P=new int[N]; //

for (i=0;i<N;i++) P[i]=0;

P[0]=1; //

while(1){

int i1=-1,j1=-1; //

for (i=0;i<N;i++) // ,

for (j=i+1;j<N;j++){ //

if (M[i][j]<=0 || P[i]==P[j]) continue;

if (j1==-1 || M[i][j]<M[i1][j1])

{ i1=i; j1=j; }

} //

if (j1==-1) break; //

sum+=M[i1][j1]; //

M[i1][j1]=-M[i1][j1]; //

M[j1][i1]=-M[j1][i1]; //

if (P[i1]==1) P[j1]=1; else P[i1]=1;

}}

. . . - . , , , , . .

 

//--------------------------------------------------------86-04.cpp

// -

//

void main(){

int N,**M,*D;

int i,k,j;

int sum=0;

if ((M=load_1("86-011.txt",N))==NULL) return;

D=new int[N];

for (i=0;i<N;i++) D[i]=i; //

while(1){

int i1=-1,j1=-1; //

for (i=0;i<N;i++) // ,

for (j=i+1;j<N;j++){ //

if (M[i][j]<=0 || D[i]==D[j]) continue;

if (j1==-1 || M[i][j]<M[i1][j1])

{ i1=i; j1=j; }

} //

if (j1==-1) break; //

sum+=M[i1][j1]; //

M[i1][j1]=-M[i1][j1]; //

M[j1][i1]=-M[j1][i1];

int P=D[j1]; //

for (j=0;j<N;j++) if (D[j]==P) D[j]=D[i1];

}}

, . 7.5 . , . , . , (.. ). , , . .