学步园

邻接矩阵法

    邻接矩阵又称数组表示,它采用两个数组表示图:一个数组表示顶点信息(一维数组)，另一个数组表示个顶点的关系，这个关系数组叫做邻接矩阵(在邻接矩阵中，若为无向图，矩阵的元素为1或0,1表示有关系，0反之；若为有向网络，则矩阵中的元素表示权,无权值则无无穷)

C语言描述:

#define MAX_VERTEX_NUM 20					//可容纳的最多的顶点个数
#define INFINTY 32768						//表示无穷大
typedef enum{DG,DN,UDG,UDN} GraphKing;		//图的种类(分别表示有向图,有向网络,无向图,无向网络)
typedef char VertexData;					//图顶点的数据类型,根据实际需要更改
typedef int AdjType;						//对于无权图,用1或0表示是否相邻;对于带权图则表示权值
typedef struct{								//struct  定义顶点信息
	AdjType adj;
	/*可编写其他信息*/
}ArcNode;
typedef struct {
	VertexData vertex[MAX_VERTEX_NUM];		//顶点数组
	ArcNode arcs[MAX_VERTEX_NUM]
				[MAX_VERTEX_NUM];			//邻接矩阵
	int vexnum,arcnum;						//顶点数目和边的数目
	GraphKing kinig;						//图的类型
}AdjMatrix;									//Adjacency Matrix Graph 邻接矩阵

下面给出测试代码:

#include<stdio.h>
#define MAX_VERTEX_NUM 20					//可容纳的最多的顶点个数
#define INFINITY 32768						//表示无穷大
typedef enum{DG,DN,UDG,UDN} GraphKing;		//图的种类(分别表示有向图,有向网络,无向图,无向网络)
typedef int VertexData;						//图顶点的数据类型,根据实际需要更改
typedef int AdjType;						//对于无权图,用1或0表示是否相邻;对于带权图则表示权值
typedef struct{								//struct  定义顶点信息
	AdjType adj;
	/*可编写其他信息*/
}ArcNode;
typedef struct {
	VertexData vertex[MAX_VERTEX_NUM];		//顶点数组
	ArcNode arcs[MAX_VERTEX_NUM]
				[MAX_VERTEX_NUM];			//邻接矩阵
	int vexnum,arcnum;						//顶点数目和边的数目
	GraphKing kinig;						//图的类型
}AdjMatrix;									//Adjacency Matrix Graph 邻接矩阵

//找出该顶点 V 在数组vertex[]中对应位置
int LocateVertex(AdjMatrix *G,VertexData v){
	int j,k;
	for(k=0;k<G->vexnum;k++){
		if(G->vertex[k] == v){
			j = k;
			break;
		}
	}
	return j;
}


void CreateDN(AdjMatrix *G)
{
	int i,j,k,weight;
	VertexData v1,v2;
	
	printf("输入顶点个数和边数:\n");
	scanf("%d%d",&G->vexnum,&G->arcnum);	//顶点和边的数目

	printf("输入%d个顶点\n",G->vexnum);
	for(i=0;i<G->vexnum;i++)
		scanf("%d",&G->vertex[i]);

	/*初始化,将矩阵的元素赋值为无穷*/
	for(i=0;i<G->vexnum;i++){
		for(j=0;j<G->vexnum;j++){
			G->arcs[i][j].adj = -1;//-1代表无穷
		}
	}
	printf("输入边的两个顶点,及该边的权值(逗号隔开)\n");
	for(k=0;k<G->arcnum;k++){
		scanf("%d%d%d",&v1,&v2,&weight);

		i = LocateVertex(G,v1);
		j = LocateVertex(G,v2);

		G->arcs[i][j].adj = weight;
	}
}
void PAdjMatrix(AdjMatrix *G)
{
	int i,j;
	for(i=0;i<G->vexnum;i++)
	{
		for(j=0;j<G->vexnum;j++){
			printf("%d\t",G->arcs[i][j].adj);
		}
		printf("\n");
	}
}
int main()
{
	AdjMatrix G;
	CreateDN(&G);
	PAdjMatrix(&G);
	return 0;
}