当前位置 博文首页 > Inmaturity_7的博客：408计算机考研--数据结构--图的学习（C语言

最大化 缩小

    Inmaturity_7的博客：408计算机考研--数据结构--图的学习（C语言

    作者：[db:作者] 时间：2021-07-16 21:45

    图的学习

    一、图的存储及BFS、DFS算法

    1.1、邻接矩阵法

    特点：

    1. 无向图的邻接矩阵一定是一个对称矩阵（并且唯一）。因此，在实际存储邻接矩阵时只需存储上（或下）三角矩阵的元素。
    2. 对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是顶点i的度TD(vi)。
    3. 对于有向图，邻接矩阵的第i行非零元素（或非∞元素）的个数正好是顶点i的出度OD(vi)；第i列非零元素（或非∞元素）正好是顶点i的入度ID(vi)。
    4. 用邻接矩阵存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。
    5. 稠密图适合使用邻接矩阵的存储表示
    6. 设图G的邻接矩阵为A,An的元素An[i][j]等于由顶点i到顶点j的长度为n的路径的数目。
    7. 邻接矩阵实现BFS和DFS算法的空间复杂度均为O(|V|)，时间复杂度均为O(|V|2)
    #include<stdio.h>
#include<string.h>
#include<stdlib.h> 
#define MaxVertexNum 100 //顶点数目的最大值
#define Max 0x7FFFFFFF	//int最大数 




typedef char VertexType; //顶点的数据类型
typedef int EdgeType;    //带权图中边上权值的数据类型
typedef struct{
	VertexType Vex[MaxVertexNum]; //顶点表
	EdgeType Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵，边表
	int vexnum,arcnum;//图的当前顶点数和弧数 
}MGragh; 
//链表 
typedef struct LinkNode{
	int val;//数据域
	struct LinkNode *next;//指针域 
}LinkNode,*LinkedList;
//链式存储队列 
typedef struct LinkedQueue{
	LinkedList front,rear;
}LinkedQueue;

//初始化队列 
void Init_LinkedQueue(LinkedQueue &q){
	q.front=q.rear=(LinkedList)malloc(sizeof(LinkNode));//建立队头和队尾
	q.front->next=NULL; 
}
//判队空
bool is_Empty(LinkedQueue &q){
	if(q.front==q.rear){
		return true; 
	} 
	return false;
} 
//入队
void EnQueue(LinkedQueue &q,int x){
	LinkedList newNode=(LinkedList)malloc(sizeof(LinkNode));//新结点
	newNode->val=x;
	newNode->next=NULL;
	//插入新结点 
	q.rear->next=newNode;
	q.rear=newNode;
	return;
} 
//出队
bool DeQueue(LinkedQueue &q,int &x){
	if(is_Empty(q)){
		return false;
	}
	//获取被删结点 
	LinkedList p=q.front->next;
	x=p->val;
	//删除结点 
	q.front->next=p->next;
	if(q.rear==p){
		q.rear=q.front; 
	}
	free(p);
	return true;
}

//找出图G的x顶点的第一个邻接点
//若有则返回顶点号。若没有返回-1 
int FirstNeighbor(MGragh G,int x){
	if(x<0||x>=G.vexnum){//判断图是否存在以及查找顶点是否在表其中，不在的话直接返回-1 
		return -1;
	}
	for(int i=0;i<G.vexnum;i++){
		if(G.Edge[x][i]==1){
			return i;//查找到第一个邻接点 
		}
	}
	return -1;
}
//找出图G的x顶点的y的下一个邻接点
//若有则返回顶点号。若没有返回-1 
int NextNeighbor(MGragh G,int x,int y){
	if(x<0||x>=G.vexnum||y<0||y>=G.vexnum){//判断图是否存在以及查找顶点是否在表其中，不在的话直接返回-1 
		return -1;
	}
	for(int i=y+1;i<G.vexnum;i++){
		if(G.Edge[x][i]==1){
			return i;//查找y的下一个邻接点 
		}
	}
	return -1;
}
//深度优先遍历算法
void DFS(MGragh G,int v,bool* visited){
	visited[v]=1;//将当前顶点标记为已访问
	printf("%c->",G.Vex[v]);//打印该结点 
	for(int w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
		if(!visited[w]){
			DFS(G,w,visited);
		}
	} 
}
//对图进行深度优先遍历 
void DFSTraverse(MGragh G,bool* visited){
	for(int v=0;v<G.vexnum;v++){//从第一个结点开始遍历整个顶点表
		if(!visited[v]){
			DFS(G,v,visited);
		}
	}
	printf("\n");
}
//广度优先遍历算法
void BFS(MGragh G,int v,bool* visited){
	LinkedQueue q;
	Init_LinkedQueue(q);//初始化队列
	EnQueue(q,v);//初始顶点入队列 
	visited[v]=1;
	printf("%c->",G.Vex[v]);//打印该结点 
	while(!is_Empty(q)){
		DeQueue(q,v);//出队列
		for(int w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
			if(!visited[w]){
				EnQueue(q,w);
				visited[w]=1;
				printf("%c->",G.Vex[w]);//打印该结点 
			}
		} 
	}
} 
void BFSTraverse(MGragh G,bool* visited){
	for(int v=0;v<G.vexnum;v++){//从第一个结点开始遍历整个顶点表
		if(!visited[v]){
			BFS(G,v,visited);
		}
	}
	printf("\n");
}
int main(){
    //测试图
	MGragh mGragh={"ABCDEFGH",
		{{0,1,0,0,1,0,0,0},
		{1,0,0,0,0,1,0,0},
		{0,0,0,1,0,1,1,0},
		{0,0,1,0,0,0,1,1},
		{1,0,0,0,0,0,0,0},
		{0,1,1,0,0,0,1,0},
		{0,0,1,1,0,1,0,1},
		{0,0,0,1,0,0,1,0}},
		8,
		10};
	bool visited[mGragh.vexnum];//定义访问顶点记录数组
	memset(visited,0,sizeof(visited));
	//DFS深度遍历算法 
	 DFSTraverse(mGragh,visited);
	 
	 
	 memset(visited,0,sizeof(visited));
	 //BFS广度遍历算法
	 BFSTraverse(mGragh,visited); 
	 //A->B->F->C->D->G->H->E->
	 //A->B->E->F->C->G->D->H->
}
    1.2、邻接表法

    特点：

    1. 若G为无向图，则所需的存储空间为O(|V|+2|E|)；若G为有向图，则所需的存储空间为O(|V|+|E|)。前者倍数2是由于无向图中，每条边在邻接表中出现了两次。
    2. 对于稀疏图，采用邻接表表示将极大地节省存储空间。
    3. 在邻接表中，给定一顶点，能很容易地找出它所有邻边，因为只需要读取它的邻接表。在邻接表中，相同的操作则需要扫描一行，花费的时间为O(n)。但是，若要确定给定的两个顶点之间是否存在边，则在邻接矩阵中可以立刻查到，而在邻接表中则需要在相应结点对应的边表中查找另一结点，效率极低。
    4. 在有向图的邻接表表示中，求一个给定顶点的度只需计算其邻接表中的结点个数；但求其顶点的入度则需要遍历全部的邻接表。因此，也有人采用逆邻接表的存储方式来加快求解给定顶点的入度。当然，这实际上与邻接表的存储方式是类似的。
    5. 图的邻接表表示并不唯一，因为在每个顶点对应的单链表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。
    #include<stdio.h>
#include<stdlib.h> 
#include<string.h> 
#define MaxVertexNum 100 //顶点数目的最大值
typedef char VertexType;//顶点类型 

typedef struct ArcNode{//边表结点 
	int adjvex;//该弧所指向的顶点的为止
	struct ArcNode *next;//指向下一条弧的指针 
	//InfoType info; //网的边权值 
}ArcNode; 
typedef  struct VNode{//顶点表结点
	VertexType data;//顶点信息
	ArcNode *first;//指向第一条依附该顶点的弧的指针	
}VNode,AdjList[MaxVertexNum];
typedef struct{
	AdjList vertices;//邻接表
	int vexnum,arcnum;//图的顶点数和弧数 
}ALGraph;//ALGraph是以邻接表存储的图类型 


//链表 
typedef struct LinkNode{
	int val;//数据域
	struct LinkNode *next;//指针域 
}LinkNode,*LinkedList;
//链式存储队列 
typedef struct LinkedQueue{
	LinkedList front,rear;
}LinkedQueue;

//初始化队列 
void Init_LinkedQueue(LinkedQueue &q){
	q.front=q.rear=(LinkedList)malloc(sizeof(LinkNode));//建立队头和队尾
	q.front->next=NULL; 
}
//判队空
bool is_Empty(LinkedQueue &q){
	if(q.front==q.rear){
		return true; 
	} 
	return false;
} 
//入队
void EnQueue(LinkedQueue &q,int x){
	LinkedList newNode=(LinkedList)malloc(sizeof(LinkNode));//新结点
	newNode->val=x;
	newNode->next=NULL;
	//插入新结点 
	q.rear->next=newNode;
	q.rear=newNode;
	return;
} 
//出队
bool DeQueue(LinkedQueue &q,int &x){
	if(is_Empty(q)){
		return false;
	}
	//获取被删结点 
	LinkedList p=q.front->next;
	x=p->val;
	//删除结点 
	q.front->next=p->next;
	if(q.rear==p){
		q.rear=q.front; 
	}
	free(p);
	return true;
}

//找出图G的x顶点的第一个邻接点
//若有则返回顶点号。若没有返回-1 
int FirstNeighbor(ALGraph G,int x){
	if(x<0||x>=G.vexnum){//判断图是否存在以及查找顶点是否在表其中，不在的话直接返回-1 
		return -1;
	}
	ArcNode* arc=G.vertices[x].first;//获取该弧
	
	return arc==NULL?-1:arc->adjvex;
}
//找出图G的x顶点的y的下一个邻接点
//若有则返回顶点号。若没有返回-1 
int NextNeighbor(ALGraph G,int x,int y){
	if(x<0||x>=G.vexnum||y<0||y>=G.vexnum){//判断图是否存在以及查找顶点是否在表其中，不在的话直接返回-1 
		return -1;
	}
	ArcNode* arc=G.vertices[x].first;//获取该弧
	while(arc!=NULL&&arc->adjvex!=y){
		arc=arc->next;
	}
	if(arc==NULL){
		return -1;
	}else{
		return arc->next==NULL?-1:arc->next->adjvex;
	}
}
//深度优先遍历算法
void DFS(ALGraph G,int v,bool* visited){
	visited[v]=1;//将当前顶点标记为已访问
	printf("%c->",G.vertices[v].data);//打印该结点 
	for(int w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
		if(!visited[w]){
			DFS(G,w,visited);
		}
	} 
}
//对图进行深度优先遍历 
void DFSTraverse(ALGraph G,bool* visited){
	for(int v=0;v<G.vexnum;v++){//从第一个结点开始遍历整个顶点表
		if(!visited[v]){
			DFS(G,v,visited);
		}
	}
	printf("\n");
}
//广度优先遍历算法
void BFS(ALGraph G,int v,bool* visited){
	LinkedQueue q;
	Init_LinkedQueue(q);//初始化队列
	EnQueue(q,v);//初始顶点入队列 
	visited[v]=1;
	printf("%c->",G.vertices[v].data);//打印该结点 
	while(!is_Empty(q)){
		DeQueue(q,v);//出队列
		for(int w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
			if(!visited[w]){
				EnQueue(q,w);
				visited[w]=1;
				printf("%c->",G.vertices[w].data);//打印该结点 
			}
		} 
	}
} 
void BFSTraverse(ALGraph G,bool* visited){
	for(int v=0;v<G.vexnum;v++){//从第一个结点开始遍历整个顶点表
		if(!visited[v]){
			BFS(G,v,visited);
		}
	}
	printf("\n");
}
int main(){
	//初始化邻接表图 
	ALGraph g;
	g.vexnum=8;
	g.arcnum=10;
	g.vertices[0].data='A';//结点A 
	ArcNode* a1=(ArcNode*)malloc(sizeof(ArcNode));
	g.vertices[0].first=(ArcNode*)malloc(sizeof(ArcNode));
	g.vertices[0].first->adjvex=1;
	a1->adjvex=4;
	a1->next=NULL;
	g.vertices[0].first->next=a1;
	
	g.vertices[1].data='B';//结点B 
	ArcNode* b1=(ArcNode*)malloc(sizeof(ArcNode));
	g.vertices[1].first=(ArcNode*)malloc(sizeof(ArcNode));
	g.vertices[1].first->adjvex=0;
	b1->adjvex=5;
	b1->next=NULL;
	g.vertices[1].first->next=b1;
	
	g.vertices[2].data='C';//结点C 
	ArcNode* c1=(ArcNode*)malloc(sizeof(ArcNode));
	ArcNode* c2=(ArcNode*)malloc(sizeof(ArcNode));
	g.vertices[2].first=(ArcNode*)malloc(sizeof(ArcNode));
	g.vertices[2].first->adjvex=3;
	c1->adjvex=5;
	c2->adjvex=6;
	c1->next=c2;
	c2->next=NULL;
	g.vertices[2].first->next=c1;
	
	g.vertices[3].data='D';//结点D 
	ArcNode* d1=(ArcNode*)malloc(sizeof(ArcNode));
	ArcNode* d2=(ArcNode*)malloc(sizeof(ArcNode));
	g.vertices[3].first=(ArcNode*)malloc(sizeof(ArcNode));
	g.vertices[3].first->adjvex=2;
	d1->adjvex=6;
	d2->adjvex=7;
	d1->next=d2;
	d2->next=NULL;
	g.vertices[3].first->next=d1;
	
	g.vertices[4].data='E';//结点E
	g.vertices[4].first=(ArcNode*)malloc(sizeof(ArcNode));
	g.vertices[4].first->adjvex=0;
	g.vertices[4].first->next=NULL;
	
	g.vertices[5].data='F';//结点F
	ArcNode* f1=(ArcNode*)malloc(sizeof(ArcNode));
	ArcNode* f2=(ArcNode*)malloc(sizeof(ArcNode));
	g.vertices[5].first=(ArcNode*)malloc(sizeof(ArcNode));
	g.vertices[5].first->adjvex=1;
	f1->adjvex=2;
	f2->adjvex=6;
	f1->next=f2;
	f2->next=NULL;
	g.vertices[5].first->next=f1;
	 
	g.vertices[6].data='G';//结点G 
	ArcNode* g1=(ArcNode*)malloc(sizeof(ArcNode));
	ArcNode* g2=(ArcNode*)malloc(sizeof(ArcNode));
	ArcNode* g3=(ArcNode*)malloc(sizeof(ArcNode));
	g.vertices[6].first=(ArcNode*)malloc(sizeof(ArcNode));
	g.vertices[6].first->adjvex=2;
	g1->adjvex=3;
	g2->adjvex=5;
	g3->adjvex=7;
	g1->next=g2;
	g2->next=g3;
	g3->next=NULL;
	g.vertices[6].first->next=g1;
	
	g.vertices[7].data='H';//结点H 
	ArcNode* h1=(ArcNode*)malloc(sizeof(ArcNode));
	g.vertices[7].first=(ArcNode*)malloc(sizeof(ArcNode));
	g.vertices[7].first->adjvex=3;
	h1->adjvex=6;
	h1->next=NULL;
	g.vertices[7].first->next=h1;
	
	bool visited[g.vexnum];//定义访问顶点记录数组
	memset(visited,0,sizeof(visited));
	//DFS深度遍历算法 
	 DFSTraverse(g,visited);
	 
	 
	 memset(visited,0,sizeof(visited));
	 //BFS广度遍历算法
	 BFSTraverse(g,visited); 
	//A->B->F->C->D->G->H->E->
	//A->B->E->F->C->G->D->H->
}
    1.3、十字链表法

    ? 十字链表是有向图的一种存储结构。

    ? 弧节点：tailvex(记录弧尾在图中的位置)、headvex(记录弧头在图中的位置)、hlink(指向弧头相同下一条弧)、tlink(指向弧尾相同的下一条弧)、info(指向该弧的相关信息)

    ? 顶点结点：data(存储顶点相关的数据信息)、firstin(指向该顶点为弧头的第一个弧结点)、firstout(指向该顶点为弧尾的第一个弧结点)

    #include<stdio.h>
#define MaxVertexNum 100 //图中顶点数目的最大值

typedef struct ArcNode{//弧结点 
	int tailvex;//弧尾
	int headvex;//弧头
	ArcNode hlink*;//指向弧头相同的下一条弧 
	ArcNode tlink*;//指向弧尾相同的下一条弧
	int info;//弧的相关信息 
}ArcNode;

typedef struct VertexNode{//顶点
	int data;// 存储顶点相关的数据信息
	ArcNode firstin*;//指向该顶点为弧头的第一个弧结点
	ArcNode firstout*;//指向该顶点为弧尾的第一个弧结点
}VertexNode,CrossList[MaxVertexNum];

typedef struct{
	CrossList crossList;//十字链表 
	int vexnum,arcnum;//图的顶点数和弧数 
}ALGraph;//ALGraph是以十字链表存储的图类型
    1.4、邻接多重表法

    邻接多重表是无向图的另一种存储结构。

    ? 弧节点：mark（标志域，可以标记该条边是否被搜索过）；ivex（记录弧尾在图中的位置）、ilink（指向下一条依附于顶点ivex的边）、jvex（记录弧头在图中的位置）、jlink（指向下一条依附于点jvex的边）、info（为指向和边的各种信息的指针域）

    ? 顶点结点：data(存储顶点相关的数据信息)、firstedge（指示第一条依附于该顶点的边）。

    #include<stdio.h>
#define MaxVertexNum 100 //图中顶点数目的最大值

typedef struct ArcNode{//弧结点 
	bool mark;//弧尾
	int ivex;//弧头
	ArcNode ilink*;//指向弧头相同的下一条弧
	int jvex;//弧尾 
	ArcNode jlink*;//指向弧尾相同的下一条弧
	int info;//弧的相关信息 
}ArcNode;

typedef struct VertexNode{//顶点
	int data;// 存储顶点相关的数据信息
	ArcNode firstedge*;//指向该顶点为弧头的第一个弧结点
}VertexNode,MultiList[MaxVertexNum];

typedef struct{
	MultiList multiList;//邻接多重表 
	int vexnum,arcnum;//图的顶点数和弧数 
}ALGraph;//ALGraph是以邻接多重表存储的图类型
    cs
    上一篇：Inmaturity_7的博客：算法练习帖--74--在排序数组中查找数字 I（
    下一篇：没有了