算法设计：邻接矩阵转换邻接表
时间： 1ms 内存：128M
描述：
算法设计：实现邻接矩阵到邻接表的转换。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
提示：
参考答案（内存最优[0]）：
#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");
}
}
void MatToList(MGraph g,ALGraph *&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->adjvex=j;
p->nextarc=G->adjlist[i].firstarc;
G->adjlist[i].firstarc=p;
}
G->n=g.n;G->e=g.e;
}
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;
}
参考答案（时间最优[0]）：
#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 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) //邻接矩阵的当前元素不为0
{
p=(ArcNode *)malloc(sizeof(ArcNode)); //创建一个节点*p
p->adjvex=j;
p->nextarc=G->adjlist[i].firstarc; //将*p链到链表后
G->adjlist[i].firstarc=p;
}
G->n=g.n;
G->e=g.e;
}
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++)
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++)
{
cin>>i>>j;
g.edges[i][j]=1;
}
DispMat(g);
MatToList(g,G);
printf("图G的邻接表:\n");
DispAdj(G); //输出邻接表
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。