把邻接矩阵转换成邻接表的算法

来源:百度知道 编辑:UC知道 时间:2024/06/19 20:48:08
数据结构中将邻接矩阵转换成邻接表的算法
具体算法
最好将主函数也写出来

#include <stdio.h>
#include <malloc.h>
#define INF 32767 //INF表示∞
typedef int InfoType;
typedef int Vertex;

//--------------邻接矩阵存储表示------------
#define MAXV 20 //最大顶点个数
#define INF 32767 //INF表示∞
//以下定义邻接矩阵类型
typedef struct{
int nunber; //顶点编号
InfoType info; //顶点其他信息
} VertexType; //顶点类型

typedef struct { //图的定义
int edges[MAXV][MAXV]; //邻接矩阵
int n,e; //顶点数,弧数
VertexType vexs[MAXV]; //存放顶点信息
} MGraph; //图的邻接矩阵类型

//-------------------邻接表存储表示----------
//以下定义邻接表类型
typedef struct ANode{ //弧的结点结构类型
int adjvex; //该弧的终点位置
InfoType info; //该弧的相关信息,这里用于存放权值
struct ANode *nextarc; //指向下一条弧的指针
} ArcNode;

typedef struct Vnode { //邻接表头结点的类型
Vertex data; //顶点信息
int count; //存放顶点入度,只在拓扑排序中用
ArcNode *firs