数据结构14天重点学习

提示：这里可以添加系列文章的所有文章的目录，目录需要自己手动添加
例如：第一章 Python 机器学习入门之pandas的使用
`
—``

提示：写完文章后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

图是数据结构中数据关系最复杂的一种结构

提示：以下是本篇文章正文内容，下面案例可供参考

一、图的储存结构

1图的两种储存结构

图的储存结构主要有两种，一种是邻接表表示法，另一种是邻接矩阵表示法。
邻接矩阵
优点
容易获得每个顶点的度，特别是对于有向图，获得顶点i的出度,只需遍历第i行，即arc[i][]的值，入度也只需遍历第i列，即arc[][i]。
缺点：
对于边数相对顶点较少的图，浪费了极大的储存空间。
邻接表
优点
便于增加和删除顶点
便于统计边的数目，按顶点表顺序扫描所有边表可得到边的数目，时间复杂度为O(n)
空间利于效率高避免了储存空间的浪费
缺点
对于有向图，出度和入度是不兼得的，要两样都获得就只能分别建立、遍历对应的邻接表和逆邻接表空间利用率和效率也不高。

2储存结构代码表示及建立

1）邻接矩阵
通过一个一维数组表示顶点，通过一个二维数组表示顶点间的关系

`邻接矩阵

代码如下

#define VertexNum 20
#define MaxWeight 99
typedef char Vertextype;
typedef int EdgeType;
typedef struct{
	Vertextype vex[VertexNum];//储存顶点信息
	EdgeType edges[VertexNum][VertexNum];//储存边的信息
	int n,e;
	}MGraph;
void CreateMGraph(MGraph *G)
{
	int i,j,k;//定义i,j用于之后遍历输入使用，k用于输入权值信息 
		EdgeType w;// 
		printf("读入顶点数和边数：\n");
	scanf("%d %d",&G->n,&G->e);
//	getchar();
	fflush(stdin);//防止键盘输入影响后面 
	printf("读入顶点信息，建立顶点表：");
	for(i=0;i<G->n;i++){
		printf("第%d个顶点",i+1);
		scanf("%c",&G->vexs[i]);
		getchar();}
	printf("输入边表信息，建立边表\n"); 
	for(i=0;i<G->n;i++){
		for(j=0;j<G->n;j++){
			G->edges[i][j]=MaxWeight;}}//初始化各边的权值 
	for(k=0;k<G->e;k++)//赋权值 
	{
		printf("输入矩阵信息，i,j,w:");
		scanf("%d %d %d",&i,&j,&w);//输入边的权值 
//			getchar();
		G->edges[i][j]=w;
		G->edges[j][i]=w;//有向图删除
	}
}

2）邻接链表
邻接链表
主要分为三个部分
结点结构
有两个域：数据域和指针域
顶点结构：丁殿宇和头指针
链接表：顶点数、边数和链接表

代码如下

#include<stdio.h>
#include<malloc.h>
#define VertexNum 20
typedef char VertexType;
typedef struct node //后面要用
{//边链表 
	int adjvex;//邻接点域 
	struct node *next;//指针域 
}EdgeNode;
typedef struct vnode//顶点表节点 
{
	VertexType vertex;//顶点域 
	EdgeNode *firstedge;//边表头指针 
}VertexNode;
typedef VertexNode AdjList[VertexNum];
typedef struct
{//邻接表定义
	AdjList adjlist;//链接表 
	int n,e;//图中当前顶点数和边数 
}ALGraph;
int CreateALGraph(ALGraph *G)
{//建立无向图的邻接表，调用成功返回返回1，否则返回0
	int i,j,k;
	EdgeNode *s;
	printf("请输入顶点数和边数：");
	scanf("%d %d",&G->n,&G->e);
	getchar();
	//fflush(stdin);//另一种防止出错的方法
	for(i=0;i<G->n;i++)
	{//建立顶点表 
		printf("输入顶点：");
		G->adjlist[i].vertex=getchar();
		fflush(stdin);
		G->adjlist[i].firstedge=NULL; 
	}
	for(k=0;k<G->e;k++)
	{//建立边表
		printf("输入边vi,vj顶点对序号："); 
		scanf("%d %d",&i,&j);
		//读入边（vi,vj)顶点对序号 
		s=(EdgeNode*)malloc(sizeof(EdgeNode));
		if(s==NULL)
		{
			puts("空间申请失败");return 0; 
		 } 
		s->adjvex=j;
		s->next=G->adjlist[i].firstedge;
		G->adjlist[i].firstedge=s;//将新节点*s插入顶点vi的边表头部
		s=(EdgeNode*)malloc(sizeof(EdgeNode));
		if(s==NULL)
		{
			puts("空间申请失败");return 0;
		 }
		s->adjvex=i;
		s->next=G->adjlist[j].firstedge;
		G->adjlist[j].firstedge=s;//将新节点*s插入到顶点vj的边表头部 
	}
	return 1; 
}

二、深度优先遍历和广度优先遍历

1.深度优先遍历

1）遍历方法
类似于树的先序遍历，特点就是尽可能的向纵深方向遍历进行搜索

代码如下（示例）：

//邻接矩阵的深度优先遍历 
void DFSM(MGRaph *G,int i)//其次执行
{//以vi为深度出发点进行搜索，设置矩阵是0,1矩阵
	int j;
	printf("%4c",G->vexs[i]);//访问i顶点
	visited[i]=1;//把被访问的顶点做好标记
	for(j=0;j<G->n;j++)
		if((G->edges[i][j]==1)&&(!visited[j]))//深度查找未被访问的元素
			DFSM(G,j);//进入访问
 }
void DFSTraverse(MGraph *G)//优先执行
{
	int i;
	for(i=0;i<G->n;i++)
		visited[i]=0;//初始化
	for(i=0;i<G->n;i++)
		if(!visited[i])//判断是否访问过
			DFSM(G,i);//进入i点的访问
}
//邻接表的深度优先遍历
void DFS(ALGraph *G,int i)//
{
	EdgeNode *p;//定义邻接点指针 
	printf("%4c",G->adjlist[i].vertex);//遍历 
	visited[i]=1;//访问后的进行标记
	p=G->adjlist[i].firstedge;//进入邻接表深入查找
	while(p)
	{//依次搜索vi的邻接点vj，这里j=p->adjvex
		if(!visited[p->adjvex])
			DFS(G,p->adjvex);
		p=p->next;
	}
}
void DFSTraverse(ALGraph *G)//邻接表深度优先第一步
{//深度优先遍历以邻接表表示G
	int i;
	for (i=0;i<G->n;i++)
		visited[i]=0;//进行初始化
	for(i=0;i<G->n;i++)//查找未被访问的顶点
	 	if(!visited[i])//判断
	 		DFS(G,i);//找到后进行访问
}

2.广度优先遍历

广度优先遍历类似于树的按层次遍历。采用的搜索方法的特点是尽可能先对横向搜索

代码如下（示例）：

//广度优先遍历邻接矩阵
int visited[vertexnum];
void BFSM(MGraph *G,int k)
{//以vk为源点对用邻接矩阵表示的图·进行广度优先搜索·
	int i,j;
	Cirqueue Q;//需要定义，在前面的链表的章节
	InitQueue(&Q);//初始化链表函数需要定义，在链表那一节
	printf(%4c",G->vexs[k]);
	visited[k]=1;
	EnQueue(&Q,k);//链表那一节
	while(!QueueEmpty(&Q))
	{
		DeQueue(&Q,&i);
		for(j=0;j<G->n;j++)
			if(G->edges[i][j]==1&&！visited[j])
			{//vj未访问
				printf("%4c",G->vexs[i])
				 visited[i]=1;
				 Dequeue(&Q,&i);
			}
	}
}
void BFSTraverse(MGraph *G)//如果·从第一个元素开始则调用此函数
{
	int i;
	for(i=0;i<G->n;i++)
		visited[i]=0;
	for(i=0;i<G->n;i++)
		if(!visited[i])
			BFSM(G,i);
}	
//广度遍历邻接表
void BFS(ALGraph *G,int k)
{
	int i;
	CirQueue Q;
	EdgeNode *p;
	InitQueue(&Q);
	printf("%4c",G->adjlist[k].vertex);
	visited[k]=1;
	EnQueue(&Q,k);
	while(!QueueEmpty(&Q))
	{//队非空则执行
		DeQueue(&Q,&i);
		p=G->adjlist[i].firstedge;
		while(p)
		{//依次搜索vi邻接点vj(令p->adjvex=j)
			if(!visited[p->adjvex])
			{//若vj未访问过
				printf("%4c",G->adjlist[p->adjvex].vertex); 
				visited[p->adjvex]=1;
				EnQueue(&Q,p->adjvex);
			 } 
			 p=p->next;//查找下一个 
			
		 } 
		
	}
}

总结

以上就是今天要讲的内容，本文仅仅简单介绍了图的最重要的两种储存结构和遍历方法，还有其他两种储存结构十字链表和邻接多重链表下次再给大家介绍