邻接矩阵转邻接表

作者：追风剑情发布于：2014-8-17 10:56 分类：Algorithms

程序语言 C++

开发工具 Visual Studio2010

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
 
#define MAXVEX 5	//图中最大顶点数
 
/////////////////////////////////////////////////////////////////////
//
// 定义邻接表数据结构
//
/////////////////////////////////////////////////////////////////////
 
//定义顶点类型为10个字符的字符数组
typedef char VertexType[10];
 
typedef struct edgenode
{
	int adjvex; //邻接点序号
	int value;  //边的权值
	struct edgenode *next; //下一条边的顶点
} ArcNode; //每个顶点建立的单键表中结点的类型
 
typedef struct vexnode
{
	VertexType data; //顶点信息
	ArcNode *firstarc; //指向第一条边结点
} VHeadNode; //单链表的头结点类型
 
typedef struct
{
	int n,e; //n为实际顶点数，e为实际边数
	VHeadNode adjlist[MAXVEX]; //单链表头结点数组
} AdjList; //图的邻接表类型
 
/////////////////////////////////////////////////////////////////////
//
// 定义邻接矩阵数据结构
//
/////////////////////////////////////////////////////////////////////
 
typedef struct vertex
{
	int adjvex;		/*顶点编号*/
	VertexType data;/*顶点信息*/
} VType; /*顶点类型*/
 
typedef struct graph
{
	int n,e; /*n为实际顶点数，e为实际边数*/
	VType vexs[MAXVEX]; /*顶点集合*/
	int edges[MAXVEX][MAXVEX]; /*边的集合*/
} AdjMatix; /*图的邻接矩阵类型*/
 
//将邻接矩阵g转换成邻接表G*
void MatToList(AdjMatix g, AdjList *&G)
{
	int i,j;
	ArcNode *p;
	G = (AdjList *)malloc(sizeof(AdjList));
	for(i=0; i<g.n; i++) //给邻接表中所有头结点的指针域置初值
	{
		G->adjlist[i].firstarc = NULL;
		strcpy(G->adjlist[i].data, g.vexs[i].data);
	}
	//检查邻接矩阵中每个元素
	for(i=0; i<g.n; i++)
	{
		for(j=g.n - 1; j>=0; j--)
		{
			if(g.edges[i][j] != 0){
				//创建一个结点p
				p = (ArcNode *)malloc(sizeof(ArcNode));
				p->value = g.edges[i][j];
				p->adjvex = j;
				//将p插入到链表之首
				p->next = G->adjlist[i].firstarc;
				G->adjlist[i].firstarc = p;
			}
		}
	}
	G->n = g.n;
	G->e = g.e;
}
 
void DispAdjList(AdjList *G)
{
	int i;
	ArcNode *p;
	printf("图的邻接表表示如下：\n");
	for(i=0; i<G->n; i++)
	{
		printf("[%d, %3s]=>", i, G->adjlist[i].data);
		p = G->adjlist[i].firstarc;
		while(p != NULL)
		{
			printf("(%d, %d)->", p->adjvex, p->value);
			p = p->next;
		}
		printf("NULL\n");
	}
}
 
void main()
{
	int i,j;
	AdjMatix g;
	AdjList *G;
	int a[5][5] = {{0,1,0,1,0},{1,0,1,0,0},{0,1,0,1,1},
					{1,0,1,0,1},{0,0,1,1,0}};
	char *vname[MAXVEX] = {"a", "b", "c", "d", "e"};
	g.n = 5;
	g.e = 12;//建立无向图，每1条无向边算2条有向边
	for(i=0; i<g.n; i++)
		strcpy(g.vexs[i].data, vname[i]);
	for(i=0; i<g.n; i++)
		for(j=0; j<g.n; j++)
			g.edges[i][j] = a[i][j];
 
	MatToList(g, G);
	DispAdjList(G);
 
	system("pause");
}