1. Toy模板网首页
  2. > Toy博客

图的邻接矩阵存储及遍历操作

10月前 作者：杼蛘 分类：Toy博客 阅读(40) 违法举报

这篇具有很好参考价值的文章主要介绍了图的邻接矩阵存储及遍历操作。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

第1关：图的邻接矩阵存储及求邻接点操作

任务描述

本关任务：要求从文件输入顶点和边数据，包括顶点信息、边、权值等，编写程序实现以下功能。
1）构造无向网G的邻接矩阵和顶点集，即图的存储结构为邻接矩阵。
2）输出无向网G的各顶点和邻接矩阵。
3）输出无向网G中顶点H的所有邻接顶点。

测试说明

平台会对你编写的代码进行测试：

测试输入：
3
lt.txt
武汉

输入说明：
第一行输入3，表示输入图的类型为无向网。
第二行输入文件名，该文件里保存了图的数据信息，内容如下：
6
9
武汉
上海
长沙
南京
成都
广州
武汉 长沙 9
武汉 成都 2
长沙 上海 2
长沙 南京 2
上海 南京 5
上海 广州 4
上海 成都 3
南京 广州 8
成都 广州 6

第1行为图的顶点的个数n；
第2行为图的边的条数m；
第3行至第n+2行是n个顶点的数据；
第n+3行至第n+m+2行是m条边的数据；
最后输入一个顶点的数据

预期输出：
无向网
6个顶点9条边。顶点依次是: 武汉 上海 长沙 南京 成都 广州
图的邻接矩阵:
∞ ∞ 9 ∞ 2 ∞
∞ ∞ 2 5 ∞ ∞
9 2 ∞ 2 ∞ ∞
∞ 5 2 ∞ ∞ ∞
2 ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞
长沙 成都

输出说明：
第一行输出图的类型。
第二行起输出图的顶点和边的数据信息。
最后一行输出输入顶点的所有邻接点。

代码如下

#include<stdio.h> 
#include<stdlib.h> 
#include<string.h>
#include<limits.h> 

typedef int VRType;    // 顶点关系类型 
typedef char VertexType[20]; // 顶点类型 
// 图的数组(邻接矩阵)存储表示 
#define INFINITY INT_MAX // 用整型最大值代替∞ 
#define MAX_VERTEX_NUM 20 // 最大顶点个数 
typedef enum{DG,DN,UDG,UDN}GraphKind; // {有向图,有向网,无向图,无向网} 

typedef struct
{
	VRType adj; // 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；对带权图，则为权值 
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 二维数组 

typedef struct      // 图的数组(邻接矩阵)存储 
{
	VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量 
	AdjMatrix arcs; // 邻接矩阵 
	int vexnum,arcnum; // 图的当前顶点数和弧数 
	GraphKind kind; // 图的种类标志 
}MGraph;  

void visit(VertexType i);

void CreateGraphF(MGraph &G);// 采用数组(邻接矩阵)表示法，由文件构造无向网G
void Display(MGraph G);    // 输出邻接矩阵存储表示的图G
int LocateVex(MGraph G,VertexType u);//若G中存在顶点u，则返回该顶点在图中位置；否则返回-1 
VertexType* GetVex(MGraph G,int v);    // v是G中某个顶点的序号，返回v的值
int FirstAdjVex(MGraph G,VertexType v);//v是图G中某个顶点，返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点，则返回-1 
int NextAdjVex(MGraph G,VertexType v,VertexType w);//v是G中某个顶点，w是v的邻接顶点，返回v的(相对于w的)下一个邻接顶点的序号，若w是v的最后一个邻接顶点，则返回-1 
void DestroyGraph(MGraph &G); // 销毁图G 




int main()
{
	MGraph g;
	VertexType v1,v2;
	CreateGraphF(g);      // 利用数据文件创建邻接矩阵表示的图	
	Display(g);           // 输出图  
	int i,j,k,n;
	//printf("请输入顶点的值: ");
	scanf("%s",v1);
	//printf("输出图G中顶点%s的所有邻接顶点: ",v1);
	k=FirstAdjVex(g,v1);
	while(k!=-1)
	{ 
		strcpy(v2, g.vexs[k] );
		visit(v2);
		k=NextAdjVex(g,v1,v2);
	}
	printf("\n");    
	return 0;
}

void visit(VertexType i)
{
	printf("%s ",i);
}


void CreateGraphF(MGraph &G)
{
	// 采用数组(邻接矩阵)表示法，由文件构造无向网G
	/********** Begin **********/
	int i,j,k,w;
	char filename[13];
	VertexType va,vb;
	FILE * graphlist;
	scanf("%d",&G.kind);
	scanf("%s",filename);
	graphlist=fopen(filename,"r");

	fscanf(graphlist,"%d",&G.vexnum);
	fscanf(graphlist,"%d",&G.arcnum);
	for(i=0;i<G.vexnum;i++)
		fscanf(graphlist,"%s",G.vexs[i]);
	for(i=0;i<G.vexnum;++i)
		for(j=0;j<G.vexnum;++j){
			if(G.kind%2)
				G.arcs[i][j].adj=INFINITY;
			else
				G.arcs[i][j].adj=0;
		}
	for(k=0;k<G.arcnum;++k){
		if(G.kind%2)
			fscanf(graphlist,"%s%s%d",va,vb,&w);
		else
			fscanf(graphlist,"%s%s",va,vb);
		i=LocateVex(G,va);
		j=LocateVex(G,vb);
		if(G.kind==0)
			G.arcs[i][j].adj=1;
		else if(G.kind==1)
			G.arcs[i][j].adj=w;
		else if(G.kind==2)
			G.arcs[i][j].adj=G.arcs[j][i].adj=1;
		else
			G.arcs[i][j].adj=G.arcs[j][i].adj=w;
	}
	fclose(graphlist);
	/********** End **********/
}


void Display(MGraph G)
{
	// 输出邻接矩阵存储表示的图G
	/********** Begin **********/
	int i,j;
	switch(G.kind){
		case DG:printf("有向图\n");break;
		case DN:printf("有向网\n");break;
		case UDG:printf("无向图\n");break;
		case UDN:printf("无向网\n");
	}
    printf("%d个顶点%d条边。顶点依次是: ",G.vexnum,G.arcnum);
	for(i=0;i<G.vexnum;++i)
		printf("%s ",G.vexs[i]);
	printf("\n图的邻接矩阵:\n");
	for(i=0;i<G.vexnum;i++){
		for(j=0;j<G.vexnum;j++)
			if(G.kind%2){
				if(G.arcs[i][j].adj==INFINITY)
					printf("%s\t","∞");
				else
					printf("%d\t",G.arcs[i][j].adj);
			}else
				printf("%d\t",G.arcs[i][j].adj);
		printf("\n");
	}
	/********** End **********/
}


int LocateVex(MGraph G,VertexType u)
{
	//初始条件：图G存在，u和G中顶点有相同特征
	// 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1 
	/********** Begin **********/
    int i;
	for(i=0;i<G.vexnum;++i)
		if(strcmp(u,G.vexs[i])==0) return i;
	return -1;  
	/********** Begin **********/
}

VertexType* GetVex(MGraph G,int v)
{ 
	// 初始条件：图G存在，v是G中某个顶点的序号。操作结果：返回v的值
	/********** Begin **********/
	if(v>=G.vexnum || v<0)
		exit(0);
	return &(G.vexs[v]); 
	/********** End **********/
}



int FirstAdjVex(MGraph G,VertexType v)
{
 	// 初始条件：图G存在，v是G中某个顶点 
	// 操作结果：返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点，则返回-1 
	/********** Begin **********/
	int i,j,k;
	if(G.kind%2)
		j=INFINITY;
	else
		j=0;
	k=LocateVex(G,v);
	for(i=0;i<G.vexnum;i++)
		if(G.arcs[k][i].adj!=j)
			return i;
	return -1;
	/********** End **********/
}

int NextAdjVex(MGraph G,VertexType v,VertexType w)
{
	// 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点 
	// 操作结果：返回v的(相对于w的)下一个邻接顶点的序号，若w是v的最后一个邻接顶点，则返回-1 
	/********** Begin **********/
	int i,j,k1,k2;
	if(G.kind%2)
		j=INFINITY;
	else
		j=0;
	k1=LocateVex(G,v);

	k2=LocateVex(G,w);

	for(i=k2+1;i<G.vexnum;i++)
		if(G.arcs[k1][i].adj!=j)
			return i;
	return -1;
	/********** End **********/
}


void DestroyGraph(MGraph &G)
{ // 初始条件：图G存在。操作结果：销毁图G 
	/********** Begin **********/
	int i,j,k=0;
	if(G.kind%2) 
		k=INFINITY; 
	G.vexnum=0; 
	G.arcnum=0; 
	/********** End **********/
}

第2关：图的深度优先遍历

任务描述

本关任务：以邻接矩阵存储图，要求编写程序实现图的深度优先遍历

测试说明

平台会对你编写的代码进行测试：

测试输入：
0
lt2.txt

输入说明：
第一行输入0，表示输入图的类型为有向图。
第二行输入文件名，该文件里保存了图的数据信息，内容如下：
图的邻接矩阵存储及遍历操作
第1行为图的顶点的个数n；
第2行为图的边的条数m；
第3行至第n+2行是n个顶点的数据；
第n+3行至第n+m+2行是m条边的数据；

预期输出：
有向图
7个顶点9条边。顶点依次是: 高等数学 程序设计基础 C语言 离散数学 数据结构 编译原理 操作系统
图的邻接矩阵:
0 0 1 1 0 0 0
0 0 1 0 1 0 0
0 0 0 0 1 0 0
0 0 0 0 1 1 0
0 0 0 0 0 1 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0
深度优先遍历序列：
高等数学 C语言 数据结构 编译原理 操作系统 离散数学 程序设计基础

输出说明：
第一行输出图的类型。
第二行起输出图的顶点和边的数据信息。
最后一行为从“高等数学”出发进行深度优先遍历的序列。

代码如下

#include<stdio.h> 
#include<stdlib.h> 
#include<string.h>
#include<limits.h> 

#include"MGraph.h"

void DFS(MGraph G,int v);// 从第v个顶点出发递归地深度优先遍历图G 
void DFSTraverse(MGraph G);// 图G存在，从第1个顶点起，深度优先遍历图G，并对每个顶点调用函数visit一次且仅一次 

int visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量) 

int main()
{
   MGraph g;
	VertexType v1,v2;
	CreateGraphF(g); /* 利用数据文件创建无向图*/
	Display(g); /* 输出无向图*/  
	printf("深度优先遍历序列：\n"); 
	DFSTraverse(g);
	return 0;
}



void DFS(MGraph G,int v)
{
	// 从第v个顶点出发递归地深度优先遍历图G 
	/********** Begin **********/
	int w;
	visited[v]=1;
	visit(G.vexs[v]);
	for(w=FirstAdjVex(G,G.vexs[v]);w>=0;w=NextAdjVex(G,G.vexs[v],G.vexs[w]))
		if(!visited[w])
			DFS(G,w);
	/********** End **********/
}

void DFSTraverse(MGraph G)
{   //图G存在，从第1个顶点起，深度优先遍历图G，并对每个顶点调用函数visit一次且仅一次 
	/********** Begin **********/
	int v;
	for(v=0;v<G.vexnum;v++)
		visited[v]=0;
	for(v=0;v<G.vexnum;v++)
		if(!visited[v])
			DFS(G,v);
	printf("\n");
	/********** End **********/
}

第3关：图的广度优先遍历

任务描述

本关任务：以邻接矩阵存储图，要求编写程序实现图的广度优先遍历。

测试说明

平台会对你编写的代码进行测试：

测试输入：
0
lt2.txt

输入说明：
第一行输入0，表示输入图的类型为有向图。
第二行输入文件名，该文件里保存了图的数据信息，内容如下：
图的邻接矩阵存储及遍历操作
第1行为图的顶点的个数n；
第2行为图的边的条数m；
第3行至第n+2行是n个顶点的数据；
第n+3行至第n+m+2行是m条边的数据；

预期输出：
有向图
7个顶点9条边。顶点依次是: 高等数学 程序设计基础 C语言 离散数学 数据结构 编译原理 操作系统
图的邻接矩阵:
0 0 1 1 0 0 0
0 0 1 0 1 0 0
0 0 0 0 1 0 0
0 0 0 0 1 1 0
0 0 0 0 0 1 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0
广度优先遍历序列：
高等数学 C语言 离散数学 数据结构 编译原理 操作系统 程序设计基础

输出说明：
第一行输出图的类型。
第二行起输出图的顶点和边的数据信息。
最后一行为从“高等数学”出发进行广度优先遍历的序列。

代码如下

#include<stdio.h> 
#include<stdlib.h> 
#include<string.h>
#include<limits.h> 

#include"MGraph.h"
#include"sqqueue.h" 


void BFSTraverse(MGraph G);// 图G存在，从第1个顶点起，按广度优先非递归遍历图G,并对每个顶点调用函数visit一次且仅一次 

int visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量) 

int main()
{
    MGraph g;
	VertexType v1,v2;
	CreateGraphF(g);    // 利用数据文件创建图
	Display(g);         // 输出图  
	printf("广度优先遍历序列：\n"); 
	BFSTraverse(g);
	return 0;
}



void BFSTraverse(MGraph G)
{ 	// 图G存在，从第1个顶点起，按广度优先非递归遍历图G,并对每个顶点调用函数visit一次且仅一次 
	/********** Begin **********/
	int v,u,w;
	SqQueue Q;
	for(v=0;v<G.vexnum;v++)
		visited[v]=0;
	InitQueue(Q);
	for(v=0;v<G.vexnum;v++)
		if(!visited[v]){
			visited[v]=1;
			visit(G.vexs[v]);
			EnQueue(Q,v);
			while(!QueueEmpty(Q)){
				DeQueue(Q,u);
				for(w=FirstAdjVex(G,G.vexs[u]);w>=0;w=NextAdjVex(G,G.vexs[u],G.vexs[w]))
					if(!visited[w]){
						visited[w]=1;
						visit(G.vexs[w]);
						EnQueue(Q,w);
					}
			}
		}
		printf("\n");
	/********** End **********/
}

辅助文件

lt.txt

6
9
武汉
上海
长沙
南京
成都
广州
武汉 长沙 9
武汉 成都 2
长沙 上海 2
长沙 南京 2
上海 南京 5
上海 广州 4
上海 成都 3
南京 广州 8
成都 广州 6

lt2.txt

7
9
高等数学
程序设计基础
C语言
离散数学
数据结构
编译原理
操作系统 
高等数学 C语言 
高等数学 离散数学 
程序设计基础 数据结构
程序设计基础 C语言
C语言 数据结构
离散数学 数据结构 
离散数学 编译原理
数据结构 编译原理 
数据结构 操作系统

MGraph.h

 #ifndef   __MGraph_H__
#define   __MGraph_H__
typedef int VRType;    // 顶点关系类型 
typedef char VertexType[20]; // 顶点类型 
// 图的数组(邻接矩阵)存储表示 
#define INFINITY 4270000 // 用整型最大值代替∞ 
#define MAX_VERTEX_NUM 20 // 最大顶点个数 
typedef enum{DG,DN,UDG,UDN}GraphKind; // {有向图,有向网,无向图,无向网} 

typedef struct
{
	VRType adj; // 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；对带权图，则为权值 
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 二维数组 

typedef struct      // 图的数组(邻接矩阵)存储 
{
	VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量 
	AdjMatrix arcs; // 邻接矩阵 
	int vexnum,arcnum; // 图的当前顶点数和弧数 
	GraphKind kind; // 图的种类标志 
}MGraph;  

/*邻接矩阵的8个基本操作函数声明*/
int LocateVex(MGraph G,VertexType u);//若图G中存在顶点u，则返回该顶点在图中位置；否则返回-1 
VertexType* GetVex(MGraph G,int v);// 根据图G中某个顶点的序号v，返回该顶点的值
void visit(VertexType i);// 访问输出顶点的值
int FirstAdjVex(MGraph G,VertexType v);// v是图G中某个顶点，返回v的第一个邻接顶点的序号。若顶点v在G中没有邻接顶点，则返回-1 
int NextAdjVex(MGraph G,VertexType v,VertexType w);//v是图G中某个顶点，w是v的邻接顶点，返回v的(相对于w的)下一个邻接顶点的序号，若w是v的最后一个邻接顶点，则返回-1 
void CreateGraphF(MGraph &G);//采用数组(邻接矩阵)表示法，由文件构造无向网G
void DestroyGraph(MGraph &G);//销毁图G 
void Display(MGraph G);//输出邻接矩阵存储表示的图G
#endif

MGraph.cpp

 #include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"MGraph.h"
/*邻接矩阵的8个基本操作函数定义*/
int LocateVex(MGraph G,VertexType u)
{
	//初始条件：图G存在，u和G中顶点有相同特征
	// 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1 
	int i;
	for(i=0;i<G.vexnum;++i)
		if(strcmp(u,G.vexs[i]) == 0)	
			return i;   // VertexType是char [16]类型
	return -1;	
}

VertexType* GetVex(MGraph G,int v)
{ 
	// 初始条件：图G存在，v是G中某个顶点的序号。操作结果：返回v的值
	if( v>=G.vexnum || v<0 )
		exit(0);
	return &(G.vexs[v]);
}

void visit(VertexType i)
{
	printf("%s ",i);
}

int FirstAdjVex(MGraph G,VertexType v)
{
	 // 初始条件：图G存在，v是G中某个顶点 
	// 操作结果：返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点，则返回-1 
	int i,j=0,k;
	k=LocateVex(G,v); // k为顶点v在图G中的序号 
	if(G.kind%2) // 网 
		j=INFINITY;
	for(i=0;i<G.vexnum;i++)
		if(G.arcs[k][i].adj!=j)
			return i;
	return -1;
}

int NextAdjVex(MGraph G,VertexType v,VertexType w)
{
	// 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点 
	// 操作结果：返回v的(相对于w的)下一个邻接顶点的序号，若w是v的最后一个邻接顶点，则返回-1 
	int i,j=0,k1,k2;
	k1=LocateVex(G,v); // k1为顶点v在图G中的序号 
	k2=LocateVex(G,w); // k2为顶点w在图G中的序号 
	if(G.kind%2) // 网 
		j=INFINITY;
	for(i=k2+1;i<G.vexnum;i++)
		if(G.arcs[k1][i].adj!=j)
			return i;
	return -1;
}

void CreateGraphF(MGraph &G)
{
	// 采用数组(邻接矩阵)表示法，由文件构造无向网G
	int i,j,k,w;
	char filename[13];
	VertexType va,vb;
	FILE *graphlist;
	//printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");
	scanf("%d",&G.kind);
	//printf("请输入数据文件名：");
	scanf("%s",filename);   
	graphlist=fopen(filename,"r");       // 以graphlist指针 打开数据文件
	fscanf(graphlist,"%d",&G.vexnum);
	fscanf(graphlist,"%d",&G.arcnum);
	for(i=0;i<G.vexnum;++i)              // 构造顶点向量
		fscanf(graphlist,"%s",G.vexs[i]);
	for(i=0;i<G.vexnum;++i)              // 初始化邻接矩阵
		for(j=0;j<G.vexnum;++j)
		{
			if(G.kind%2)                 // 网
				G.arcs[i][j].adj=INFINITY;       
			else                         // 图
				G.arcs[i][j].adj=0; 
		}
		for(k=0;k<G.arcnum;++k)
		{
			if(G.kind%2)                 // 网
				fscanf(graphlist,"%s%s%d",va,vb,&w);
			else                         // 图
				fscanf(graphlist,"%s%s",va,vb);

			i=LocateVex(G,va);
			j=LocateVex(G,vb);
			if(G.kind == 0)              // 有向图
				G.arcs[i][j].adj =1;
			else if(G.kind == 1)
				G.arcs[i][j].adj=w;      // 有向网
			else   if(G.kind == 2)       // 无向图
				G.arcs[i][j].adj =  G.arcs[j][i].adj=1;
			else
				G.arcs[i][j].adj =  G.arcs[j][i].adj = w;
		}
	fclose(graphlist);              // 关闭数据文件
}

void DestroyGraph(MGraph &G)
{ 
	// 初始条件：图G存在。操作结果：销毁图G 	
	int i,j,k=0;
	if(G.kind%2) // 网 
		k=INFINITY; // k为两顶点之间无边或弧时邻接矩阵元素的值 
	G.vexnum=0; // 顶点数为0 
	G.arcnum=0; // 边数为0 
}

void Display(MGraph G)
{ 
	// 输出邻接矩阵存储表示的图G	
	int i,j;
	switch(G.kind)
	{
	case DG: printf("有向图\n");	      break;
	case DN: printf("有向网\n");          break;
	case UDG:printf("无向图\n");         break;
	case UDN:printf("无向网\n");
	}
	printf("%d个顶点%d条边。顶点依次是: ",G.vexnum,G.arcnum);
	for(i=0;i<G.vexnum;++i)         // 输出G.vexs 
		printf("%s ",G.vexs[i]);
	printf("\n图的邻接矩阵:\n");     // 输出G.arcs.adj 

	for(i=0;i<G.vexnum;i++)
	{
		for(j=0;j<G.vexnum;j++)
			if(G.kind%2)  
			{
				if(G.arcs[i][j].adj==INFINITY)
					printf("%s\t","∞");
				else
					printf("%d\t",G.arcs[i][j].adj);
			}
			else
				printf("%d\t",G.arcs[i][j].adj);
		printf("\n");
	} 
}

sqqueue.h

#ifndef   __SQQUEUE_H__
#define   __SQQUEUE_H__
#include"symbol.h"
#define MAX_QSIZE 20 // 最大队列长度+1

typedef int VRType;    // 顶点关系类型
typedef  VRType  QElemType;

 
struct SqQueue
{
   QElemType *base; // 初始化的动态分配存储空间
   int front; // 头指针，若队列不空，指向队列头元素
   int rear; // 尾指针，若队列不空，指向队列尾元素的下一个位置
};
void InitQueue(SqQueue &Q);      // 构造一个空循环队列Q 
void DestroyQueue(SqQueue &Q);   // 销毁循环队列Q，Q不再存在
void ClearQueue(SqQueue &Q);   // 将Q清为空循环队列
int QueueEmpty(SqQueue Q);     // 若循环队列Q为空队列，则返回TRUE；否则返回FALSE
int QueueLength(SqQueue Q);      // 返回Q的元素个数，即循环队列的长度
int GetHead(SqQueue Q,QElemType &e); // 若循环队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR
int EnQueue(SqQueue &Q,QElemType e);   // 插入元素e为循环队列Q的新的队尾元素
int DeQueue(SqQueue &Q,QElemType &e);  // 若循环队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR
void QueueTraverse(SqQueue Q,void(*vi)(QElemType)); // 从队头到队尾依次对队列Q中每个元素调用函数vi()
#endif

sqqueue.cpp

#include<stdio.h>
#include<stdlib.h>

#include"sqqueue.h" 
typedef  int  QElemType;
void InitQueue(SqQueue &Q)
 { 
   Q.base=(QElemType *)malloc(MAX_QSIZE*sizeof(QElemType));
   if(!Q.base) // 存储分配失败
     exit(OVERFLOW);
   Q.front=Q.rear=0;
 }
// 销毁循环队列Q，Q不再存在
 void DestroyQueue(SqQueue &Q)
 { 
   if(Q.base)
     free(Q.base);
   Q.base=NULL;
   Q.front=Q.rear=0;
 }
// 将Q清为空循环队列
 void ClearQueue(SqQueue &Q)
 { 
   Q.front=Q.rear=0;
 }
// 若循环队列Q为空队列，则返回TRUE；否则返回FALSE
 int QueueEmpty(SqQueue Q)
 { 
   if(Q.front==Q.rear) // 队列空的标志
     return TRUE;
   else
     return FALSE;
 }
// 返回Q的元素个数，即循环队列的长度
 int QueueLength(SqQueue Q)
 { 
   return(Q.rear-Q.front+MAX_QSIZE)%MAX_QSIZE;
 }
// 若循环队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR
 int GetHead(SqQueue Q,QElemType &e)
 { 
   if(Q.front==Q.rear) // 队列空
     return ERROR;
   e=Q.base[Q.front];
   return OK;
 }
// 插入元素e为循环队列Q的新的队尾元素
 int EnQueue(SqQueue &Q,QElemType e)
 { 
   if((Q.rear+1)%MAX_QSIZE==Q.front) // 队列满
     return ERROR;
   Q.base[Q.rear]=e;
   Q.rear=(Q.rear+1)%MAX_QSIZE;
   return OK;
 }
// 若循环队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR
 int DeQueue(SqQueue &Q,QElemType &e)
 { 
   if(Q.front==Q.rear) // 队列空
     return ERROR;
   e=Q.base[Q.front];
   Q.front=(Q.front+1)%MAX_QSIZE;
   return OK;
 }
// 从队头到队尾依次对队列Q中每个元素调用函数vi()
 void QueueTraverse(SqQueue Q,void(*vi)(QElemType))
 { 
   int i;
   i=Q.front;
   while(i!=Q.rear)
   {
     vi(Q.base[i]);
     i=(i+1)%MAX_QSIZE;
   }
   printf("\n");
 }

symbol.h文章来源地址https://www.toymoban.com/news/detail-456070.html

#ifndef   __SYMBOL_H__
#define   __SYMBOL_H__

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1

#endif

到了这里，关于图的邻接矩阵存储及遍历操作的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 对无向图进行邻接矩阵的转化，并且利用DFS（深度优先）和BFS（广度优先）算法进行遍历输出， 在邻接矩阵存储结构上，完成最小生成树的操作。

    对无向图进行邻接矩阵的转化，并且利用DFS（深度优先）和BFS（广度优先）算法进行遍历输出， 在邻接矩阵存储结构上，完成最小生成树的操作。

    目录 一 实验目的 二 实验内容及要求 实验内容： 实验要求： 三 实验过程及运行结果 一 算法设计思路 二 源程序代码 三、截图 四 调试情况、设计技巧及体会 1．掌握图的相关概念。 2．掌握用邻接矩阵和邻接表的方法描述图的存储结构。 3．掌握图的深度优先搜索和广度优

    2024年02月04日
    浏览(57)
  • 【数据结构】图的创建（邻接矩阵，邻接表）以及深度广度遍历（BFS,DFS）

    【数据结构】图的创建（邻接矩阵，邻接表）以及深度广度遍历（BFS,DFS）

    图是由顶点集合及顶点间的关系组成的一种数据结构：G = (V， E)，其中： 顶点集合V = {x|x属于某个数据对象集}是有穷非空集合； E = {(x,y)|x,y属于V}或者E = {x, y|x,y属于V Path(x, y)}是顶点间关系的有穷集合，也叫 做边的集合。 完全图：在有n个顶点的无向图中，若有n * (n-1)/2条边，

    2024年02月04日
    浏览(45)
  • 图的存储 —— 邻接矩阵

    图的存储 —— 邻接矩阵

    图的结构比较复杂，任何两个节点之间都可能有关系。 图的存储分为顺序存储和链式存储。 顺序存储包括邻接矩阵和边集数组， 链式存储包括邻接表、链式前向星、十字链表和邻接多重表。 图的存储 —— 邻接矩阵 邻接矩阵通常采用一个一维数组存储图中节点的信息，采用

    2024年02月06日
    浏览(42)
  • 数据结构——图的基本定义以及图的存储结构，邻接矩阵，邻接表

    数据结构——图的基本定义以及图的存储结构，邻接矩阵，邻接表

    目录 图的定义和术语 图的存储结构 顺序存储结构—邻接矩阵 链式存储结构 邻接表 邻接多重表 十字链表 图的遍历 图的连通性问题 有向无环图及其应用 最短路径 图的定义：图是一种非线性的复杂的数据结构，图中的数据元素的关系是多对多的关系 ，在图中我们常常把数

    2024年02月04日
    浏览(58)
  • 图的数据结构，系统学习图的基本概念、定义和建立，学会邻接矩阵、邻接表以及实现六度空间案例，遍历图的方式——广度、深度访问

    图的数据结构，系统学习图的基本概念、定义和建立，学会邻接矩阵、邻接表以及实现六度空间案例，遍历图的方式——广度、深度访问

    图 ：G = (V,E) Graph = (Vertex, Edge) V：顶点（数据元素）的有穷非空集合； E：边的有穷集合。 有向图 ：每条边都是有方向的     无向图 ：每条边都是无方向的   完全图 ：任意两点之间都有一条边相连    无向完全图：n个顶点，n(n-1)/2条边 无向完全图：n个顶点，n(n-1)条边 稀疏

    2023年04月22日
    浏览(49)
  • 图的存储--邻接矩阵/边集数组/邻接表/链式邻接表/链式前向星

    图的存储--邻接矩阵/边集数组/邻接表/链式邻接表/链式前向星

    使用二维数组w[u][v]存储点u到点v的边的权值。 一般应用在点数不多的稠密图 时间复杂度：O(n 2 ) 空间复杂度：O(n 2 ) 边集数组e[i]存储第i条边的「起点、终点、边权」。在kruskal算法中，将边按边权排序，直接存边。 时间复杂度：O(nm) 空间复杂度：O(m) 出边数组e[u][i]存储u的所

    2024年02月02日
    浏览(39)
  • 24考研数据结构-图的存储结构邻接矩阵

    24考研数据结构-图的存储结构邻接矩阵

    【1】顶点的结点结构 ——————— | data | firstarc | ——————— data数据域：储存顶点vi firstarc链域：指向链表中第一个结点 【2】弧的结点结构 —————————— | adjvex | info | nextarc | —————————— adjvex邻接点域：与顶点vi邻接的点在图中的位置 info数据域

    2024年02月14日
    浏览(57)
  • 图详解第一篇：图的基本概念及其存储结构（邻接矩阵和邻接表）

    图详解第一篇：图的基本概念及其存储结构（邻接矩阵和邻接表）

    这篇文章开始，我们来学习一种高阶数据结构——图 图是由顶点集合及顶点间的关系（边）组成的一种数据结构：G = (V， E)。 其中： 顶点集合V = {x|x属于某个数据对象集}是有穷非空集合； E = {(x,y)|x,y属于V}或者E = {x, y|x,y属于V Path(x, y)}是顶点间关系的有穷集合，也叫做边的集

    2024年02月08日
    浏览(42)
  • C++数据结构之图的存储结构——邻接矩阵和邻接表实现无向图

    C++数据结构之图的存储结构——邻接矩阵和邻接表实现无向图

    关键点： 1.构建二维数组 2.对应边的位置赋值为1 由于比较简单就直接上代码： 个人对邻接表实现无向图的理解如下，仅供参考：         由于无向图的组成是由多个顶点和多条无向边组成的，因此我们可以把它拆分成两个结构，分别是顶点和无向边，又由于我们是使用

    2024年02月05日
    浏览(55)
  • 图的基本操作（邻接矩阵）

    图的基本操作（邻接矩阵）

    图是比较常用的一种数据结构，我针对期末考试对其进行了大概整理，形成了本文。 整体上是基于文件进行图的建立，有两种文件内容格式，READMODE ==1时，是读入顶点个数，顶点信息以及邻接矩阵，READMODE ==2时，是读入顶点个数，顶点信息，边的个数，边的信息，样例如下：

    2024年02月04日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包