图的邻接矩阵，邻接表的C语言实现(408真题)

图的邻接矩阵

数据结构定义

#define MAXV 50;//顶点数目的最大值 
typedef struct{
	int vex[MAX];			//顶点表 
	int edge[MAXV][MAXV];	//邻接矩阵 
	int edgeNum,vexNum; 	//图中实际的边数和顶点数 
}MGraph;

初始化

void Matrix_Init(MGraph *Mgraph) {
	int v1, v2;//存储有边的两个顶点的序号,注意：顶点序号是从1开始
	printf("请输入顶点数和边数：");
	scanf("%d%d", &Mgraph->vexNum, &Mgraph->edgeNum);
	printf("请输入每个顶点的值(一次性输入)：");
	for (int i = 0; i < Mgraph->vexNum; i++)
	{
		scanf("%d", &Mgraph->vex[i]);
	}
	for (int i = 0; i < Mgraph->edgeNum; i++)
	{
		for (int j = 0; j < Mgraph->edgeNum; j++)
		{	//任意两个顶点之间的边初始化为0，表示现在还没有一条边
			Mgraph->edge[i][j] = 0;
		}
	}
	for (int i = 0; i < Mgraph->edgeNum; i++)
	{
		printf("请输入有边相连的两个顶点的序号(输入一对就回车)：");
		scanf("%d%d", &v1, &v2);
		Mgraph->edge[v1 - 1][v2 - 1] = 1;
		Mgraph->edge[v2 - 1][v1 - 1] = 1;//因为是无向图，所以该邻接矩阵是对称的
	}
}

2021年408算法题

//EL路径：图中存在一条路径经过所有边，且每条边都只经过了一次
//算法思想：遍历邻接矩阵，统计**度为奇数的顶点个数**，若有0个或2个这样的顶点，返回1，否则返回0
int IsExistEL(MGraph G){
	int count = 0; //度为奇数的顶点个数 
	for(int i = 0; i<G.numVertices; i++){
		degree = 0;
		for(int j = 0; j<G.numEdges; j++){
			degree+= G.Edge[i][j]; //累加顶点的度 
		}
		if(degree%2==1){
			count++; //统计度为奇数的顶点个数  
		}
	}
	if(count == 0 || count == 2){
		return 1;
	}else{
		return 0;
	} 
}

2023年408算法题

//算法思想：分别按行按列遍历邻接矩阵，得到顶点的出度和入度，若出度大于入度则输出
int printVertices(MGraph G){
	int count = 0; //K顶点个数 
	for(int i = 0; i<G.numVertices; i++){
		int indegree = 0;
		int outdegree = 0;
		for(int j = 0; j<G.numEdges; j++){
			//统计出度
			outdegree+=G.Edge[i][j];
		}
		fot(int j = 0; j<G.numEdges; j++){
			//统计入度 
			indegree+=G.Edge[j]i]; 
		}
		
		if(outdegree>indegree){
			printf("%c",G.VerticesList[i]); 
			count++;
		}
	}
	return count;
}

邻接表

数据结构定义

#define MAXV 50;//顶点数目的最大值
//邻接表法
typedef struct ArcNode {
	int adjvex;				 	//弧所指向的顶点的位置
	//int weight;				//若边有权值 
	struct ArcNode* nextArc; 	//指向下一条弧的指针
}ArcNode;
typedef struct{
	int vex;					//顶点的值 
	ArcNode* firstArc;			//该顶点指向第一条边的指针 
}VertexNode;
typedef struct{
	VertexNode adjlist[MAXV];	//顶点表 
	int vexNum, arcNum;			//图中实际的顶点数和边数 
}ALGraph;

初始化

void AdjList_Init(ALGraph &ALgraph) {
	int v1, v2;//存储有边的两个顶点的序号,注意：顶点序号是从1开始，c语言数组下标从0开始
	ArcNode *pNew1,*pNew2;//用来创建边结点,因为是无向图，所以创建两个
	printf("请输入顶点数和边数：");
	scanf("%d%d", &ALgraph.vexNum, &ALgraph.arcNum);
	printf("请输入每个顶点的值：");
	for (int i = 0; i < ALgraph.vexNum; i++)
	{
		scanf("%d", &ALgraph.adjlist[i].vex);//输入顶点的值
		ALgraph.adjlist[i].firstArc = NULL;//表示所有顶点之间还没有边相连
	}
	for (int i = 0; i < ALgraph.arcNum; i++)
	{
		printf("请输入有边的两个顶点：");
		scanf("%d%d", &v1, &v2);
		pNew1 = (ArcNode*)malloc(sizeof(ArcNode));//创建一个边结点
		pNew1->adjvex = v2 - 1; //边所指向的顶点的位置(c语言数组下标从0开始)
		pNew1->nextArc = ALgraph.adjlist[v1 - 1].firstArc; //头插法
		ALgraph.adjlist[v1 - 1].firstArc = pNew1;

		//因为是无向图，所以v2顶点的边表也要进行插入
		pNew2 = (ArcNode*)malloc(sizeof(ArcNode));
		pNew2->adjvex = v1 - 1; //边所指向的顶点的位置(从0开始的)
		pNew2->nextArc = ALgraph.adjlist[v2 - 1].firstArc;
		ALgraph.adjlist[v2 - 1].firstArc = pNew1;
	}
}