图论

图论Grap

本章介绍图的基本操作，请仔细阅读

图的操作

结构体

#pragma once
#define MAXSIZE 16
#define INF 65535

typedef int ElemType;
typedef int VertexType;//顶点类型
typedef int EdgeType;//边的类型

typedef struct graph{
	VertexType Vex[MAXSIZE];//顶点集
	EdgeType Edge[MAXSIZE][MAXSIZE];//边集
	int vernum;//实际顶点数
	int edgenum;//实际边数
}Graph;

初始化

//初始化图
void initGraph(Graph &G)
{
	for(int i=0;i<MAXSIZE;i++)
	{
		G.vertices[i].data=0;
		G.vertices[i].first=NULL;
	}
	G.vexnum=0;
	G.arcnum=0;
}

添加顶点

void addVertex(Graph &G,VertexType v)
{
	if(G.vexnum>=MAXSIZE)
	{return;}
	G.vertices[G.vexnum++].data=v;
}

判断顶点是否存在

//如果顶点在图中存在返回其在顶点表中的下标，否则的话返回-1
int vex_is_exist(Graph G,VertexType v)
{
	for(int i=0;i<G.vexnum;i++)
	{
		if(G.vertices[i].data==v)
		{
			return i;
		}
	}
	return -1;
}

添加边

//添加边
void add_edge(Graph &G,VertexType v1,VertexType v2)
{
	//查找v1 v2在表中的下标
	int index1=vex_is_exist(G,v1);
	int index2=vex_is_exist(G,v2);
	if(index1==-1||index2==-1)	{return;	}

	/*
	//尾插法创建v1的边表结点
	ArcNode*pre=(ArcNode*)malloc(sizeof(ArcNode));
	pre->adjVex=v1;
	pre->next=NULL;
	if(G.vertices[index1].first==NULL){
		G.vertices[index1].first=pre;
	}else{
		ArcNode*tail=G.vertices[index1].first;
		while(tail->next!=NULL)
		{
			tail=tail->next;
		}
		tail->next=pre;
	}
	//创建v2的边表结点
	ArcNode*last=(ArcNode*)malloc(sizeof(ArcNode));
	last->adjVex=v2;
	last->next=NULL;
	if(G.vertices[index2].first==NULL){
		G.vertices[index2].first=last;
	}else{
		ArcNode*tail=G.vertices[index2].first;
		while(tail->next!=NULL)
		{
			tail=tail->next;
		}
		tail->next=last;
	}
	*/

	
	//创建V1边结点并插入
	ArcNode*pre=(ArcNode*)malloc(sizeof(ArcNode));
	pre->adjVex=v2;
	pre->next=G.vertices[index1].first;
	G.vertices[index1].first=pre->next;
	
	//创建V1边结点并插入
	ArcNode*last=(ArcNode*)malloc(sizeof(ArcNode));
	last->adjVex=v1;
	last->next=G.vertices[index2].first;
	G.vertices[index2].first=last;
	G.arcnum++;

}//当前的图为无向图,要V1->V2还要V2->V1

打印图

void print_graph(Graph G)
{
	printf("图的邻接表存储;\n");
	for(int i=0;i<G.vexnum;i++)
	{	
		printf("%d: ",G.vertices[i].data);
		ArcNode*pre=G.vertices[i].first;
		while(pre!=NULL)
		{
			printf("%d->",pre->adjVex);
			pre=pre->next;
		}
		printf("\n");
	}
}

创建邻接表

void create_graph(Graph &G)
{
	printf("当前图G所包含的顶点为:\n");
	VertexType v;
	scanf("%d",&v);
	while(v!=999)
	{
		addVertex(G,v);
		scanf("%d",&v);
	}

	printf("请输入要创建的G的边集（V1 V2）\n");
	VertexType v1,v2;
	scanf("%d%d",&v1,&v2);
	while(v1!=0||v2!=0)
	{
		add_edge(G,v1,v2);
		add_edge(G,v2,v1);
		scanf("%d%d",&v1,&v2);
	}
}

//列出图中所有与x相邻的顶点
void find_all_neighbors(Graph G,VertexType x,VertexType data[])
{	//data用于存放与x相邻的所有顶点的信息
	int index=vex_is_exist(G,x);
	if(index==-1){return;}//顶点不存在，直接退出
	
	int count=0;
	ArcNode*pre=G.vertices[index].first;
	while(pre)
	{
		data[count++]=pre->adjVex;
		pre=pre->next;
	}
}

求图中顶点的第一个邻接点

VertexType first_neighbor(Graph G,VertexType x)
{
	int index=vex_is_exist(G,x);
	if(index==-1){return -1;}//判断顶点存不存在

	ArcNode*pre=G.vertices[index].first;
	if(pre==NULL){return -1;}else{return pre->adjVex;}
}

求相邻的结点

//假设图G中顶点y是x的一个邻接点，返回除y外的顶点x的
//下一个邻接点的顶点，若y是x的最后一个顶点则返回-1
VertexType next_neighbor(Graph G,VertexType x,VertexType y)
{
	int index=vex_is_exist(G,x);
	if(index==-1){return -1;}//判断顶点存不存在
	
	ArcNode*pre=G.vertices[index].first;
	while(pre&&pre->adjVex!=y)
	{
		pre=pre->next;
	}
	if(pre&&pre->next)	{return pre->next->adjVex;}
	
	return -1;
}

找顶点的入度

int in_degree(Graph G,VertexType x)
{
	int count=0;
	for(int i=0;i<G.vexnum;i++)
	{
		ArcNode*pre=G.vertices[i].first;
		while(pre)
		{
			if(pre->adjVex==x){count++;}
			pre=pre->next;
		}
	}
	return count;
}

广度优先搜索

void BFS(Graph G,VertexType start)
{
	Queue Q;
	initQueue(Q);
	bool visted[MAXSIZE]={false};//记录顶点是否被访问，初始为false，访问过则改为true
	enQueue(Q,start);
	visted[vex_is_exist(G,start)]=true;//入队之后，更新vist表，跟新结点访问情况
	while(!isEmpty(Q))
	{
		VertexType pre=deQueue(Q);
		printf("%d ",pre);
		VertexType near[MAXSIZE];
		find_all_neighbors(G,pre,near);//找出队顶点相邻的顶点，并存放在near数组中，near中元素的个数为该顶点的出度
		for(int i=0;i<de_degree(G,pre);i++)
		{
			if(visted[vex_is_exist(G,near[i])]==false)//没有访问过就让它入队
			{	
				enQueue(Q,near[i]);
				visted[vex_is_exist(G,near[i])]=true;
			}
		}	
	}
}

深度优先搜索

递归

bool vist[MAXSIZE]={false};
void DFS(Graph G,VertexType v)
{
	vist[vex_is_exist(G,v)]=true;
	printf("%d ",v);
	VertexType near[MAXSIZE];
	find_all_neighbors(G,v,near);
	for(int i=0;i<de_degree(G,v);i++)
	{
		if(vist[vex_is_exist(G,near[i])]==false)
		{
			DFS(G,near[i]);
		}
	}
}

非递归

void DFS1(Graph G,VertexType v)
{
	Stack S;
	initStack(S);
	bool visted[MAXSIZE]={false};//判断图中元素是否被访问过
	push(S,v);
	printf("%d",v);
	visted[vex_is_exist(G,v)]=true;
	while(!isEmpty(S))
	{
		VertexType pre=pop(S);
		VertexType near[MAXSIZE];
		find_all_neighbors(G,pre,near);
		for(int i=0;i<de_degree(G,pre);i++)
		{
			if(!visted[vex_is_exist(G,pre)])
			{
				push(S,pre);
				push(S,near[i]);
				printf("%d",near[i]);
				visted[vex_is_exist(G,near[i])]=true;
				break;
			}
		}
	}
}