图1——用邻接矩阵表示法创建有向图
图
可分两部分:一个是创建顶点信息,可用一个一维数组存储;另一个是创建弧的信息,包括弧的相关顶点和权值,可存储到二维数组里,其中,二维数组的下标分别表示两个顶点的弧尾和弧头编号,权值存放在对应的数组中。
创建一个网:
请输入有向网N的顶点数和弧数:6 9
请输入6个顶点的值:
a b c d e f
请分别输入9条弧的弧尾 弧头 权值(以空格分隔):
a b 6
a e 5
a f 9
f c 7
b c 8
b f 6
c d 5
d a 12
e d 3
code:
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>
#include <iomanip>
#include <iostream>
using namespace std;
typedef char VertexType[4];
typedef char InfoPtr;
typedef int VRType;
#define INFINITY 65535
#define MAXSIZE 100
typedef enum{DG,DN,UG,UN}GraphKind;//图的类型,有向图、有向网、无向图、无向网
typedef struct
{
VRType adj;//无权图,1表示相邻,0表示不相邻;对于带权图,存储权值
InfoPtr *info; //弧或边的相关信息
}ArcNode,AdjMatrix[MAXSIZE][MAXSIZE];
typedef struct
{
VertexType vex[MAXSIZE];//用于存储顶点
AdjMatrix arc;
int vexnum, arcnum;//顶点数和边(弧)的数
GraphKind kind;//图的类型
}MGraph;
void CreateGraph(MGraph *N);
int LocateVertex(MGraph N,VertexType v);
void DestoryGraph(MGraph *N);
void DisplayGraph(MGraph N);
void main()
{
MGraph N;
cout << "创建一个网:" << endl;
CreateGraph(&N);
cout << "输出网的顶点和弧:" << endl;
DisplayGraph(N);
DestoryGraph(&N);
system("pause");
}
void CreateGraph(MGraph *N)
{
int i, j, k, w;
VertexType v1, v2;
cout << "请输入有向网N的顶点数和弧数:";
cin >> (*N).vexnum >> (*N).arcnum;
cout << "请输入" << N->vexnum << "个顶点的值:" << endl;
for (i = 0; i < N->vexnum;i++)
{
cin >> N->vex[i];
}
for (i = 0; i < N->vexnum;i++)
{
for (j = 0; j < N->vexnum; j++)
{
N->arc[i][j].adj = INFINITY;
N->arc[i][j].info = NULL;
}
}
cout << "请分别输入" << N->arcnum << "条弧的弧尾 弧头 权值(以空格分隔):" << endl;
for (k = 0; k < N->arcnum;k++)
{
cin >> v1 >> v2 >> w;
i = LocateVertex(*N, v1);
j = LocateVertex(*N, v2);
N->arc[i][j].adj = w;
}
N->kind = DN;
}
int LocateVertex(MGraph N, VertexType v)
{
int i;
for (i = 0; i < N.vexnum;++i)
{
if (strcmp(N.vex[i],v)==0)
{
return i;
}
}
return -1;
}
void DestoryGraph(MGraph *N)
{
int i, j;
for (i = 0; i < N->vexnum;i++)
{
for (j = 0; j < N->vexnum;j++)
{
if (N->arc[i][j].adj!=INFINITY)
{
if (N->arc[i][j].info!=NULL)
{
free(N->arc[i][j].info);
N->arc[i][j].info = NULL;
}
}
}
}
N->vexnum = 0;
N->arcnum = 0;
}
void DisplayGraph(MGraph N)
{
int i, j;
cout << "有向网具有" << N.vexnum << "个顶点" << N.arcnum << "条弧,顶点依次是:";
for (i = 0; i < N.vexnum;++i)
{
cout << N.vex[i] << " ";
}
cout << endl << "有向网N的" << endl;
cout << "顶点:";
for (i = 0; i < N.vexnum;i++)
{
cout << setw(7) << N.vex[i];
}
cout << endl;
for (i = 0; i < N.vexnum;i++)
{
cout << setw(6) << N.vex[i];
for (j = 0; j < N.vexnum;j++)
{
cout << setw(7) << N.arc[i][j].adj;
}
cout << endl;
}
}
结果: