図の一連のアルゴリズム(続き)
2835 ワード
#include<iostream>
using namespace std;
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
typedef enum {DG, DN, UDG, UDN} GraphKind;
//
typedef struct ArcCell
{
int key; // ， 1 0 ， ，
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //
typedef struct {
int vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum; //
GraphKind kind;
}MGraph;
//
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode
{
int key;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices;
int vexnum,arcnum;
GraphKind kind;
} ALGraph;
void CreateUD(MGraph &G) //
{
int i,j;
cout<<"Input vexnum:"<<endl;
cin>>G.vexnum;
cout<<"Input arcnum:"<<endl;
cin>>G.arcnum;
for( i=0; i<G.vexnum; ++i)
{
for( j=0; j<G.vexnum; ++j)
{
G.arcs[i][j].key = 0;
}
}
int v1,v2;
for( int k=0; k<G.arcnum; ++k)
{
cout<<"Input two index:"<<endl;
cin>>v1>>v2;
G.arcs[v1][v2].key=1;
G.arcs[v2][v1].key = G.arcs[v1][v2].key; //
}
cout<<"Graph:"<<endl;
for( i=0; i<G.vexnum; ++i)
{
for( j=0; j<G.vexnum; ++j)
{
cout<<G.arcs[i][j].key<<" ";
}
cout<<endl;
}
}
void CreateDG(ALGraph &G) //
{
int i;
cout<<"Input vexnum:"<<endl;
cin>>G.vexnum;
cout<<"Input arcnum:"<<endl;
cin>>G.arcnum;
for( i=0; i<G.vexnum; i++)
{
G.vertices[i].key=i;
G.vertices[i].firstarc=NULL;
}
int v1,v2;
for( int k=0; k<G.arcnum; ++k)
{
cout<<"Input two index:"<<endl;
cin>>v1>>v2;
if( v1==v2 )
{
--k;
cout<<"two index are same, renew input:"<<endl;
continue;
}
ArcNode *node = (ArcNode *)malloc(sizeof(ArcNode));
node->adjvex=v2;
node->nextarc=NULL;
if(G.vertices[v1].firstarc==NULL)
{
G.vertices[v1].firstarc=node;
}
else
{
ArcNode *next=G.vertices[v1].firstarc;
while(next->nextarc)
{
next=next->nextarc;
}
next->nextarc=node;
}
}
for( int j=0; j<G.vexnum; j++)
{
cout<<G.vertices[j].key<<" :";
ArcNode *next=G.vertices[j].firstarc;
while( next!=NULL)
{
cout<<next->adjvex<<" ";
next=next->nextarc;
}
cout<<endl;
}
}