第12週目プロジェクト4-遍歴思想を利用して図問題を解く
7776 ワード
/*
*Copyright(c++)2014
*All rights reserved.
* :graph.h/graph.cpp/main.cpp
* :
* :2015.11.20
* :v1.0
* : , 、 。 , :
* : g1 :
0 5 0 7 0 0
0 0 4 0 0 0
8 0 0 0 0 9
0 0 5 0 0 6
0 0 0 5 0 0
3 0 0 0 1 0
G1 :
0: -->1/5 -->3/7
1: -->2/4
2: -->0/8 -->5/9
3: -->2/5 -->5/6
4: -->3/5
5: -->0/3 -->4/1
g1 G2:
0: -->1/5 -->3/7
1: -->2/4
2: -->0/8 -->5/9
3: -->2/5 -->5/6
4: -->3/5
5: -->0/3 -->4/1
G1 g2:
0 5 0 7 0 0
0 0 4 0 0 0
8 0 0 0 0 9
0 0 5 0 0 6
0 0 0 5 0 0
3 0 0 0 1 0
Press any key to continue
*/
#include <stdio.h>
#include <malloc.h>
#include "graph.h"
int main()
{
MGraph g1,g2;
ALGraph *G1,*G2;
int A[6][6]=
{
{0,5,0,7,0,0},
{0,0,4,0,0,0},
{8,0,0,0,0,9},
{0,0,5,0,0,6},
{0,0,0,5,0,0},
{3,0,0,0,1,0}
};
ArrayToMat(A[0], 6, g1); // , A[0], ,
printf(" g1 :
");
DispMat(g1);
ArrayToList(A[0], 6, G1);
printf(" G1 :
");
DispAdj(G1);
MatToList(g1,G2);
printf(" g1 G2:
");
DispAdj(G2);
ListToMat(G1,g2);
printf(" G1 g2:
");
DispMat(g2);
printf("
");
return 0;
}
#ifndef GRAPH_H_INCLUDED
#define GRAPH_H_INCLUDED
#define MAXV 100 //
#define INF 32767 //INF ∞
typedef int InfoType;
//
typedef struct
{
int no; //
InfoType info; // ,
} VertexType; //
typedef struct //
{
int edges[MAXV][MAXV]; //
int n,e; // ,
VertexType vexs[MAXV]; //
} MGraph; //
//
typedef struct ANode //
{
int adjvex; //
struct ANode *nextarc; //
InfoType info; // ,
} ArcNode;
typedef int Vertex;
typedef struct Vnode //
{
Vertex data; //
int count; // ,
ArcNode *firstarc; //
} VNode;
typedef VNode AdjList[MAXV]; //AdjList
typedef struct
{
AdjList adjlist; //
int n,e; // n e
} ALGraph; //
// : ,
// :Arr - , , Arr ( int )
// n -
// g -
void ArrayToMat(int *Arr, int n, MGraph &g); //
void ArrayToList(int *Arr, int n, ALGraph *&); //
void MatToList(MGraph g,ALGraph *&G);// g G
void ListToMat(ALGraph *G,MGraph &g);// G g
void DispMat(MGraph g);// g
void DispAdj(ALGraph *G);// G
#endif // GRAPH_H_INCLUDED
#include <stdio.h>
#include <malloc.h>
#include "graph.h"
// : ,
// :Arr - , , Arr ( int )
// n -
// g -
void ArrayToMat(int *Arr, int n, MGraph &g)
{
int i,j,count=0; //count , 0
g.n=n;
for (i=0; i<g.n; i++)
for (j=0; j<g.n; j++)
{
g.edges[i][j]=Arr[i*n+j]; // Arr n×n ,Arr[i*n+j] Arr[i][j],
if(g.edges[i][j]!=0)
count++;
}
g.e=count;
}
void ArrayToList(int *Arr, int n, ALGraph *&G)
{
int i,j,count=0; //count , 0
ArcNode *p;
G=(ALGraph *)malloc(sizeof(ALGraph));
G->n=n;
for (i=0; i<n; i++) //
G->adjlist[i].firstarc=NULL;
for (i=0; i<n; i++) //
for (j=n-1; j>=0; j--)
if (Arr[i*n+j]!=0) // , Arr n×n ,Arr[i*n+j] Arr[i][j]
{
p=(ArcNode *)malloc(sizeof(ArcNode)); // *p
p->adjvex=j;
p->info=Arr[i*n+j];
p->nextarc=G->adjlist[i].firstarc; // *p
G->adjlist[i].firstarc=p;
}
G->e=count;
}
void MatToList(MGraph g, ALGraph *&G)
// g G
{
int i,j;
ArcNode *p;
G=(ALGraph *)malloc(sizeof(ALGraph));
for (i=0; i<g.n; i++) //
G->adjlist[i].firstarc=NULL;
for (i=0; i<g.n; i++) //
for (j=g.n-1; j>=0; j--)
if (g.edges[i][j]!=0) //
{
p=(ArcNode *)malloc(sizeof(ArcNode)); // *p
p->adjvex=j;
p->info=g.edges[i][j];
p->nextarc=G->adjlist[i].firstarc; // *p
G->adjlist[i].firstarc=p;
}
G->n=g.n;
G->e=g.e;
}
void ListToMat(ALGraph *G,MGraph &g)
// G g
{
int i,j;
ArcNode *p;
g.n=G->n; // “ ” 。g.n ,
g.e=G->e;
for (i=0; i<g.n; i++) //
for (j=0; j<g.n; j++)
g.edges[i][j]=0;
for (i=0; i<G->n; i++) // ,
{
p=G->adjlist[i].firstarc;
while (p!=NULL)
{
g.edges[i][p->adjvex]=p->info;
p=p->nextarc;
}
}
}
void DispMat(MGraph g)
// g
{
int i,j;
for (i=0; i<g.n; i++)
{
for (j=0; j<g.n; j++)
if (g.edges[i][j]==INF)
printf("%3s","∞");
else
printf("%3d",g.edges[i][j]);
printf("
");
}
}
void DispAdj(ALGraph *G)
// G
{
int i;
ArcNode *p;
for (i=0; i<G->n; i++)
{
p=G->adjlist[i].firstarc;
printf("%3d: ",i);
while (p!=NULL)
{
printf("-->%d/%d ",p->adjvex,p->info);
p=p->nextarc;
}
printf("
");
}
}
出力結果: