天天看点
返回

看数据结构写代码（35） 图的邻接矩阵表示法

杂谈：最近清明小长假，好好的放松了一下。节前 和 节后 都有点 松懈。不好，不好。贵在坚持。加油。

图的邻接矩阵表示法是用 两个数组 来表示 图的数据结构。一个是顶点数组，另一个是邻接矩阵数组。邻接矩阵 里存放着 顶点的关系。

用邻接矩阵表示图，在 看 顶点之间 是否有边，或者 求顶点的度等操作时比较简单。但空间浪费巨大，在插入，删除 顶点 和边 操作时 需要 移动大量数据，造成不便。所以在插入删除比较多，节点数比较多的时候 不宜 使用这种结构。

下面上代码：

源代码网盘地址：点击打开链接

// MGraph2.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <climits>
#include <cstring>

#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
enum E_State
{
	E_State_Error = 0,
	E_State_Ok = 1,
};
enum E_Graph_Kind
{
	DG = 0,//有向图
	DN,//有向网
	UDG,//无向图
	UDN,//无向网
};
//边（弧）单元
typedef struct ArcCell
{
	int adj;//表示顶点的关系类型，对于无权图，0，1表示是否相邻，对于有权图，表示权值类型
	char * info;//边,弧其余信息.
}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
//定义图
struct MGraph
{
	char  vexs[MAX_VERTEX_NUM];//顶点集
	AdjMatrix arcs;//图的邻接矩阵
	int vexNum,arcNum;
	E_Graph_Kind kind;
};

int graphLocation(MGraph graph,char  vex);
void createDG(MGraph * graph);
void createDN(MGraph * graph);
void createUDG(MGraph * graph);
void createUDN(MGraph * graph);

void graphCreate(MGraph * graph){
	E_Graph_Kind kind;
	printf("请输入要创建的图的类型（有向图：0，有向网：1，无向图：2，无向网：3）\n");
	scanf("%d",&kind);
	switch (kind){
	case DG:
		createDG(graph);
		break;
	case DN:
		createDN(graph);
		break;
	case UDG:
		createUDG(graph);
		break;
	case UDN:
		createUDN(graph);
		break;
	default:
		break;
	}
}
//返回顶点vex的第一个邻接点
char  firstAdjVex(MGraph graph,char vex){
	int location = graphLocation(graph,vex);
	int i = 0;
	for (; i < graph.vexNum; i++){
		if ((graph.kind == DG || graph.kind == UDG) && graph.arcs[location][i].adj == 1){
			return graph.vexs[i];
		}
		else if((graph.kind == DN || graph.kind == UDN) && graph.arcs[location][i].adj != INFINITY){
			return graph.vexs[i];
		}
	}
	return ' ';
}
//返回顶点vex1 相对于 vex2的下一个邻接点.
char  nextAdjVex(MGraph graph,char  vex1,char  vex2){
	int location1 = graphLocation(graph,vex1);
	int location2 = graphLocation(graph,vex2);
	int i = location2+1;
	for (; i < graph.vexNum; i++){
		if ((graph.kind == DG || graph.kind == UDG) && graph.arcs[location1][i].adj == 1){
			return graph.vexs[i];
		}
		else if((graph.kind == DN || graph.kind == UDN) && graph.arcs[location1][i].adj != INFINITY){
			return graph.vexs[i];
		}
	}
	return ' ';
}


//查找顶点的位置
int graphLocation(MGraph graph,char  vex){
	for (int i = 0; i < graph.vexNum; i++){
		if (graph.vexs[i] == vex){
			return i;
		}
	}
	return -1;
}
//创建图 子函数
//有向图
void createDG(MGraph * graph){
	graph->kind = DG;
	printf("请输入顶点数，边(弧)数\n");
	scanf("%d%d%*c",&graph->vexNum,&graph->arcNum);
	//初始化邻接矩阵
	for (int i = 0; i < MAX_VERTEX_NUM; i++){
		for (int j = 0; j < MAX_VERTEX_NUM; j++){
			graph->arcs[i][j].adj = 0;
			graph->arcs[i][j].info = NULL;
		}
	}
	//构造顶点集
	printf("请输入顶点集\n");
	for (int i = 0; i < graph->vexNum; i++){
		scanf("%c",&graph->vexs[i]);
	}
	//构造顶点关系
	fflush(stdin);
	printf("请输入顶点的关系\n");
	for (int i = 0; i < graph->arcNum; i++){
		char vex1,vex2;
		scanf("%c%c%*c",&vex1,&vex2);
		int location1 = graphLocation(*graph,vex1);
		int location2 = graphLocation(*graph,vex2);
		graph->arcs[location1][location2].adj = 1;
	}
}
//有向网
void createDN(MGraph * graph){
	graph->kind = DN;
	printf("请输入顶点数，边(弧)数\n");
	scanf("%d%d%*c",&graph->vexNum,&graph->arcNum);
	//初始化邻接矩阵
	for (int i = 0; i < MAX_VERTEX_NUM; i++){
		for (int j = 0; j < MAX_VERTEX_NUM; j++){
			graph->arcs[i][j].adj = INFINITY;
			graph->arcs[i][j].info = NULL;
		}
	}
	//构造顶点集
	printf("请输入顶点集\n");
	for (int i = 0; i < graph->vexNum; i++){
		scanf("%c",&graph->vexs[i]);
	}
	//构造顶点关系
	fflush(stdin);
	printf("请输入顶点的关系\n");
	for (int i = 0; i < graph->arcNum; i++){
		char vex1,vex2;
		int weight;
		scanf("%c%c%d%*c",&vex1,&vex2,&weight);
		int location1 = graphLocation(*graph,vex1);
		int location2 = graphLocation(*graph,vex2);
		graph->arcs[location1][location2].adj = weight;
	}
}
//无向图
void createUDG(MGraph * graph){
	graph->kind = UDG;
	printf("请输入顶点数，边(弧)数\n");
	scanf("%d%d%*c",&graph->vexNum,&graph->arcNum);
	//初始化邻接矩阵
	for (int i = 0; i < MAX_VERTEX_NUM; i++){
		for (int j = 0; j < MAX_VERTEX_NUM; j++){
			graph->arcs[i][j].adj = 0;
			graph->arcs[i][j].info = NULL;
		}
	}
	//构造顶点集
	printf("请输入顶点集\n");
	for (int i = 0; i < graph->vexNum; i++){
		scanf("%c",&graph->vexs[i]);
	}
	fflush(stdin);
	//构造顶点关系
	printf("请输入顶点的关系\n");
	for (int i = 0; i < graph->arcNum; i++){
		char vex1,vex2;
		scanf("%c%c%*c",&vex1,&vex2);
		int location1 = graphLocation(*graph,vex1);
		int location2 = graphLocation(*graph,vex2);
		graph->arcs[location1][location2].adj = graph->arcs[location2][location1].adj = 1;
	}
}
//无向网
void createUDN(MGraph * graph){
	graph->kind = UDN;
	printf("请输入顶点数，边(弧)数\n");
	scanf("%d%d%*c",&graph->vexNum,&graph->arcNum);
	//初始化邻接矩阵
	for (int i = 0; i < MAX_VERTEX_NUM; i++){
		for (int j = 0; j < MAX_VERTEX_NUM; j++){
			graph->arcs[i][j].adj = INFINITY;
			graph->arcs[i][j].info = NULL;
		}
	}
	//构造顶点集
	printf("请输入顶点集\n");
	for (int i = 0; i < graph->vexNum; i++){
		scanf("%c",&graph->vexs[i]);
	}
	//构造顶点关系
	fflush(stdin);
	printf("请输入顶点的关系\n");
	for (int i = 0; i < graph->arcNum; i++){
		char vex1,vex2;
		int weight;
		scanf("%c%c%d%*c",&vex1,&vex2,&weight);
		int location1 = graphLocation(*graph,vex1);
		int location2 = graphLocation(*graph,vex2);
		graph->arcs[location1][location2].adj =graph->arcs[location2][location1].adj = weight;
	}
}

//查看顶点数据之间是否相邻
bool graphIsAdj(MGraph graph,char vex1,char vex2){
	E_Graph_Kind kind = graph.kind;
	int weight = (kind == DG || kind == UDG) ? 0 : INFINITY;
	int location1 = graphLocation(graph,vex1);
	int location2 = graphLocation(graph,vex2);
	return graph.arcs[location1][location2].adj != weight ? true : false;
}

int graphDegree(MGraph graph,char vex){
	int location = graphLocation(graph,vex);
	E_Graph_Kind kind = graph.kind;
	int weight = (kind == DG || kind == UDG) ? 0 : INFINITY;
	int degree = 0;
	for (int i = 0; i < graph.vexNum; i++){//计算行
		if (graph.arcs[location][i].adj != weight){
			degree++;
		}
	}
	for (int i = 0; i < graph.vexNum; i++){//计算列
		if (graph.arcs[i][location].adj != weight){
			degree++;
		}
	}
	if (kind == UDG || kind == UDN){
		degree /= 2;
	}
	return degree;
}

//当有以下操作时，不适合 用邻接矩阵的方式来处理。
void insertVex(MGraph * graph,char  vex){
	graph->vexs[graph->vexNum++] = vex;
}
//需要移动很多元素.
void deleteVex(MGraph * graph,char  vex){
	int location = graphLocation(*graph,vex);
	//删除顶点集
	for (int i = location+1; i < graph->vexNum; i++){
		graph->vexs[i-1] = graph->vexs[i];
	}
	//计算删除的边（弧）数
	graph->arcNum -= graphDegree(*graph,vex);
	//删除边（弧）
	//vex下面的上移
	for (int i = location+1; i < graph->vexNum; i++){
		for (int j = 0; j < graph->vexNum; j++){
			graph->arcs[i-1][j] = graph->arcs[i][j];
		}
	}
	//vex右边的左移
	for (int i = location + 1; i < graph->vexNum; i++){
		for (int j = 0; j < graph->vexNum; j++){
			graph->arcs[j][i-1] = graph->arcs[j][i];
		}
	}
	//清理垃圾数据(第vexNum行 和 第vexNum列）
	int maxVexNum = graph->vexNum;
	E_Graph_Kind kind = graph->kind;
	int weight = (kind == DG || kind == UDG) ? 0 : INFINITY;
	for (int i = 0; i < maxVexNum; i++){
		graph->arcs[maxVexNum-1][i].adj = weight;
		graph->arcs[i][maxVexNum-1].adj = weight;
	}
	graph->vexNum--;
}
//插入边（弧）
void insertArc(MGraph * graph,char  vex1,char  vex2,int weight){
	int location1 = graphLocation(*graph,vex1);
	int location2 = graphLocation(*graph,vex2);
	E_Graph_Kind kind = graph->kind;
	if (kind == DG || kind == UDG){
		graph->arcs[location1][location2].adj = 1;
	}
	else{
		graph->arcs[location1][location2].adj = weight;
	}
	if (kind == UDG || kind == UDN)
	{
		graph->arcs[location2][location1].adj = graph->arcs[location1][location2].adj;
	}
}
//删除边（弧）
void deleteArc(MGraph * graph,char  vex1,char  vex2){
	int location1 = graphLocation(*graph,vex1);
	int location2 = graphLocation(*graph,vex2);
	E_Graph_Kind kind = graph->kind;
	if (kind == DG || kind == UDG){
		graph->arcs[location1][location2].adj = 0;
	}
	else{
		graph->arcs[location1][location2].adj = INFINITY;
	}
	if (kind == UDG || kind == UDN)
	{
		graph->arcs[location2][location1].adj = graph->arcs[location1][location2].adj;
	}
}

void printAdjMatrix(MGraph graph){
	for (int i = 0; i < graph.vexNum; i++){
		for (int j = 0; j < graph.vexNum; j++){
			printf("%d\t",graph.arcs[i][j]);
		}
		printf("\n");
	}
}




int _tmain(int argc, _TCHAR* argv[])
{
	MGraph graph;
	graphCreate(&graph);
	printAdjMatrix(graph);
	printf("图 有 %d个顶点,%d个边（弧）\n",graph.vexNum,graph.arcNum);
	char * isAdj = graphIsAdj(graph,'a','d')? "相邻":"不相邻";
	int degree = graphDegree(graph,'c');
	printf("a 和 d %s,c的度数是：%d\n",isAdj,degree);
	char vexFirst = firstAdjVex(graph,'c');
	char vexNext = nextAdjVex(graph,'c','a');
	printf("c的第一个邻接点是%c\nc的相对于a的下一个邻接点是%c\n",vexFirst,vexNext);
	insertVex(&graph,'e');
	printf("插入节点e之后：\n");
	printAdjMatrix(graph);
	printf("插入边(e,d)之后:\n");
	insertArc(&graph,'e','d',1);
	printAdjMatrix(graph);
	printf("删除顶点c之后：\n");
	deleteVex(&graph,'c');
	printAdjMatrix(graph);
	deleteArc(&graph,'a','b');
	printf("删除弧(a,b)之后：\n");
	printAdjMatrix(graph);
	return 0;
}

运行截图：

看数据结构写代码（35） 图的邻接矩阵表示法
数据结构 图的数组表示法 图的邻接矩阵表示法
上一篇: SVN提交之后补写或改写log信息的方法及错误问题解决
下一篇: 浅谈二分答案

继续阅读