图的表示法以及实现

一、图的表示

1.邻接矩阵

邻接指的是将所有元素用表相邻的连接起来，而矩阵是指用一个二维数组存储边的关系

2.邻接表

正常邻接表每个节点上记录出度链表的首地址，为了方便查找入度出现了逆邻接表，每个节点记录入度链表的首地址

3.十字链表

每个节点既要记录出度首地址，也要记录入度首地址

4.邻接多重表

当存储无向表时，会重复记录边的关系，邻接多重表就是为了解决这种情况出现的

5.边集数组

二，代码实现

1.邻接矩阵实现图

a.头文件

//
// Created by 27893 on 2025/7/20.
//

#ifndef MATRIXGRAPH_H
#define MATRIXGRAPH_H

#define MaxNodeNum 20//矩阵最大容量

#define INF 1E5

//顶点结构
typedef struct {
	int no;
	const char*show;
}MatrixVertex;
//边的结构
typedef int MatrixEdge;

//邻接矩阵表示图结构
typedef struct {
	MatrixVertex vex[MaxNodeNum];
	MatrixEdge edges[MaxNodeNum][MaxNodeNum];
	int nodeNum;
	int edgeNum;
	int directed;
}MGraph;

void initMGragh(MGraph*graph,const char*names[],int num,int directed,int edgeValue);

void addMGraph(MGraph*graph,int x,int y,int w);
#endif //MATRIXGRAPH_H

b.将接口实现 

//
// Created by 27893 on 2025/7/20.
//

#include "MatrixGraph.h"
#include <stdio.h>
#include <string.h>;
static int isEdge(int weight) {
	if (weight>0&&weight<INF) {
		return 1;
	}
	return 0;
}

void initMGragh(MGraph *graph, const char*names[], int num, int directed, int edgeValue) {
	graph->nodeNum=num;
	graph->directed=directed;
	graph->edgeNum=0;
	memset(graph->vex,0,sizeof(graph->vex));
	memset(graph->edges,0,sizeof(graph->edges));
	for (int i=0;i<num;++i) {
		graph->vex[i].no=i;
		graph->vex[i].show=names[i];
		for (int j=0;j<num;j++) {
			graph->edges[i][j]=edgeValue;
		}
	}
}

void addMGraph(MGraph*graph,int x,int y,int w) {
	//判断传入的x，y是否合法
	if (x<0||x>graph->nodeNum) {
		return;
	}
	if (y<0||y>graph->nodeNum) {
		return;
	}
	if (!isEdge(graph->edges[x][y])) {
		graph->edges[x][y]=w;
		if (graph->directed==0) {
			graph->edges[y][x]=w;
		}
		graph->edgeNum++;
	}
}