题目描述
算法设计：实现邻接矩阵到邻接表的转换。void MatToList(MGraph g,ALGraph *&G) 将邻接矩阵g转换成邻接表G。主函数及其他各个函数已给出。
#include <stdio.h>
#include <malloc.h>
#include <iostream>
using namespace std;
#define INF -1
typedef int InfoType;
#define MAXV 100 //最大顶点个数
//以下定义邻接矩阵类型
typedef struct
{
int no; //顶点编号
} VertexType; //顶点类型
typedef struct //图的定义
{
int edges[MAXV][MAXV]; //邻接矩阵
int n,e; //顶点数，边数
VertexType vexs[MAXV]; //存放顶点信息
} MGraph; //图的邻接矩阵类型
//以下定义邻接表类型
typedef struct ANode //边的节点结构类型
{
int adjvex; //该边的终点位置
struct ANode *nextarc; //指向下一条边的指针
} ArcNode;
typedef int Vertex;
typedef struct Vnode //邻接表头节点的类型
{
Vertex data; //顶点信息
ArcNode *firstarc; //指向第一条边
} VNode;
typedef VNode AdjList[MAXV]; //AdjList是邻接表类型
typedef struct
{
AdjList adjlist; //邻接表
int n,e; //图中顶点数n和边数e
} ALGraph; //图的邻接表类型
void DispMat(MGraph g) //输出邻接矩阵g
{
int i,j;
for (i=0; i<g.n; i++)
{
for (j=0; j<g.n; j++)
printf("%3d",g.edges[i][j]);
printf("\n");
}
}
void DispAdj(ALGraph *G) //输出邻接表G
{
int i;
ArcNode *p;
for (i=0; i<G->n; i++)
{
p=G->adjlist[i].firstarc;
printf("%d: ",i);
while (p!=NULL)
{
printf("%3d",p->adjvex);
p=p->nextarc;
}
printf("\n");
}
}
int main()
{
ALGraph *G;
MGraph g;
int i,j,k;
cin>>g.n>>g.e; //输入图的定点个数与边的个数
for (i=0; i<g.n; i++) //初识化图的邻接矩阵，对角线为1，其余为-1
for (j=0; j<g.n; j++)
{
if(i==j)
g.edges[i][j]=0;
else
g.edges[i][j]=-1;
}
for(k=0; k<g.e; k++) //输入图的各个边，有边，将其置为1，无边不变
{
cin>>i>>j;
g.edges[i][j]=1;
}
DispMat(g);
MatToList(g,G);
printf("图G的邻接表:\n");
DispAdj(G); //输出邻接表
return 0;
}
注意：只提交void MatToList(MGraph g,ALGraph *&G)部分。
输入
输入图的顶点个数n
输入图的边的个数e
输入e行，每行为一个边的顶点对<i,j>
输出
输出图的邻接矩阵
输出图的邻接表，由n行组成，每行以各个顶点的“序号：”开始，然后是该顶点的所有邻接点。
样例输入
5
6
0 1
0 2
0 3
1 0
1 4
4 2
样例输出
0 1 1 1 -1
1 0 -1 -1 1
-1 -1 0 -1 -1
-1 -1 -1 0 -1
-1 -1 1 -1 0
图G的邻接表:
0: 1 2 3
1: 0 4
2:
3:
4: 2
参考代码
暂无
解析
暂无
