数据结构-图的深度遍历和广度遍历-邻接矩阵-邻接表

structfun.h

//数据结构函数头文件

#include <stdio.h>
#include <iostream>
#include<string>

using std::cout;
using std::cin;
using std::string;

#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define INFINITY 65535//无穷大
typedef string ElemType;
typedef string VertexType;//图顶点数据类型
typedef int EdgeType;//图边的数据类型

//定义一个数组队列
typedef struct Queue
{
int date[MAXSIZE];
int num;
};

//数据结构-图-----------------------------------------------------------------------------

//1、邻接矩阵（Adjacency Martix）
	//设置一个顶点数组vertex[],设置一个边数组arc[][]
typedef struct
{
	//图顶点数组
	VertexType vertex[MAXSIZE];
	//图边数组
	EdgeType arc[MAXSIZE][MAXSIZE];	
	int vertexnum,arcnum;
}AdjMarGraph;

//2、邻接表（Adjacency List）
	//设置一个顶点数组vertex[],设置一个边的链表，顶点的next指向所对应的链表

typedef struct EdgeNode//边链表节点
{
	EdgeType arcVertex;
	int weight;//权值
	EdgeNode *next;
}EdgeNode;

typedef struct//顶点数组
{
	VertexType vertex;
	EdgeNode *firstEdge;
}VertexList[MAXSIZE];

typedef struct//图结构
{
	VertexList vlist;
	int numVertex,numArc;

}AdjListGraph;

//3、十字链表（Orthogonal->正交的 List）
	//设置一个顶点数组vertex[],设置一个边的链表，顶点的next指向所对应的链表

//链表节点 tailvex headvex headlink,taillink; 改成invex,outvex,outlink,inlink更好理解
                                                //入顶点，出顶点，出链接，入链接
typedef struct OrthogonalLinkNode
{
	EdgeType invex,outvex;
	OrthogonalLinkNode *outlink,*inlink;
	int weight;//边的权重
}OrthogonalLinkNode;

//数组顶点节点 vertex 顶点 edgein 入边 edgeout 出边
typedef struct
{
	VertexType vertex;
	OrthogonalLinkNode *edgein,*edgeout;
}OrthogonalEdgeNode[MAXSIZE];

//十字链表结构
typedef struct 
{
	OrthogonalEdgeNode vertexlist;
	int numvertex,numedge;
}OrthogonalListGraph;

//4、无向图 邻接多重表结构Adjacency Multiple Table（邻接多重表就是一个顶点的多条边用链表链接）
//ivex ilink jvex jlink (ivex jvex 边的两个顶点，ilink指向值与ivex相同的jvex的节点,jlink指向值与jvex相同的下一个节点。

typedef struct AMTEdgeNode//边链表节点
{
	VertexType iver,jver;
	bool visited;//是否被访问过
	int weight;//权值
	AMTEdgeNode *ilink,*jlink;
}AMTEdgeNode;

typedef struct//顶点数组
{
	VertexType vertex;
	AMTEdgeNode *firstEdge;
}AMTVertexList[MAXSIZE];

typedef struct//图结构
{
	AMTVertexList vlist;
	int numVertex,numArc;

}AdjacencyMultipleTableGraph;




//1、邻接矩阵
	//无向图的邻接矩阵
int CreateAdjMaxGraph(AdjMarGraph *amg);
int AdjMarDepthFirstSearch(AdjMarGraph *amg,int f);//邻接矩阵深度遍历 int f为开始的结点
int AdjMarBreadthFirstSearch(AdjMarGraph *amg);
int AMBFS(AdjMarGraph *amg);

//2、邻接表
int CreateAdjListGraph(AdjListGraph *alg);
int AdjListDepthFirstSearch(AdjListGraph *alg,int f);//邻接表深度遍历
int AdjListBreadthFirstSearch(AdjListGraph *alg);//邻接表广度遍历

//3、十字链表
int CreateOrthogonalListGraph(OrthogonalListGraph *olg);

//4、邻接多重表结构
int CreateAdjacencyMultipleTableGraph(AdjacencyMultipleTableGraph *amtg);

structfun.cpp

#include<iostream>
#include<stdio.h>
#include<string>
#include<sstream>
#include"structfun.h"


using std::cout;
using std::cin;
using std::string;
using std::endl;
using std::ostringstream;


//图结构函数-----------------------------------------------
//1、邻接矩阵
	//图的邻接矩阵
int CreateAdjMaxGraph(AdjMarGraph *amg)
{
	int i=0;
	amg->vertexnum=0;
	amg->arcnum=0;

	while(1)//输入顶点;
	{
		printf("请输入顶点，结束用#号：");
	/*	scanf("%s",&amg->vertex[i]);*///string不能采用scanf,采用scanf必须先给字符串
		//预先分配空间，然后采用amg->vertex[i][0]scanf采用的是字符数组的形式存储字符串。
		//amg->vertex[i].resize(100);
		//scanf("%s",&amg->vertex[i][0]);
		cin>>amg->vertex[i];

		if(amg->vertex[i]=="#")
			break;
		amg->vertexnum++;
		i++;
		
	}
	for(i=0;i<amg->vertexnum;i++)//初始化边值为0
		for(int j=0;j<amg->vertexnum;j++)
		{
			if(i==j)
				amg->arc[i][j]=0;
			else
			amg->arc[i][j]=INFINITY;
		}
	//创建邻接矩阵图的边
	while(1)
	{
		int v1,v2,value;
		printf("请输入图的边的顶点下标（v1,v2,value）结束输入（0,0,0）：");
		scanf("%d,%d,%d",&v1,&v2,&value);
		amg->arc[v1][v2]=value;
		amg->arc[v2][v1]=value;//无向图增加对等矩阵另外一边的值
		if(!v1&!v2&!value)
			break;
		amg->arcnum++;	
	}
	
	//输出图的邻接矩阵
	printf("图的邻接矩阵:\n");
	for(i=0;i<amg->vertexnum;i++)
	{
		printf("%s: ",amg->vertex[i].c_str());
		for(int j=0;j<amg->vertexnum;j++)
			{
				printf("%d  ",amg->arc[i][j]);
				if(j==amg->vertexnum-1)
					printf("\n");
			}
	}
return OK;
}
//->1图邻接矩阵的深度遍历
bool visited[MAXSIZE];
int AdjMarDepthFirstRecursion(AdjMarGraph *amg,int i)//递归(Recursion)
{
	if(!visited[i])
		printf("%s ",amg->vertex[i].c_str());
	else return OK;
	visited[i]=true;
	for(int j=0;j<amg->vertexnum;j++)
		if(amg->arc[i][j]==1)//判断是否有路径
	{
		printf("(%d,%d)",i,j);
		AdjMarDepthFirstRecursion(amg,j);
	}
	return OK;
}
int AdjMarDepthFirstSearch(AdjMarGraph *amg,int f)//邻接矩阵深度遍历
{
	for(int i=0;i<amg->vertexnum;i++)
		visited[i]=false;
	printf("邻接矩阵深度遍历:\n");
	AdjMarDepthFirstRecursion(amg,f);//针对连通图，如果不是连通图就再使用循环

	//for(int i=0;i<amg->vertexnum;i++)
	//	AdjMarDepthFirstRecursion(amg,i);

	return OK;
}

//->2图邻接矩阵的深度遍历
Queue list;//定义一个全局数列
int AdjMarBreadthFirstRecursion(AdjMarGraph *amg,int i)//图邻接矩阵广度优先递归
{
	/*int list[MAXSIZE],intlist=0;*///不能直接用数组，要用队列数据结构
	
	if(!visited[i])
	printf("%s ",amg->vertex[i].c_str());
	else return OK;

	visited[i]=true;
	for(int j=0;j<amg->vertexnum;j++)
		if(amg->arc[i][j]==1)
			{
				list.date[list.num]=j;
				list.num++;
			}
		for(int j=0;j<=list.num;j++)
			AdjMarBreadthFirstRecursion(amg,list.date[j]);
	return OK;		
}//递归方法
int AdjMarBreadthFirstSearch(AdjMarGraph *amg)
{

	for(int i=0;i<amg->vertexnum;i++)
		visited[i]=false;

	list.num=0;//队列合计初始化

	printf("广度优先遍历结果：\n");
	AdjMarBreadthFirstRecursion(amg,2);
	return OK;
}
//广度优先遍历（不用递归）
int AMBFS(AdjMarGraph *amg)
{
	int i=0;
	for(i=0;i<amg->vertexnum;i++)//初始化访问标识数组
		visited[i]=false;

	list.num=0;//队列合计初始化

	printf("广度优先遍历结果：\n");
	list.date[0]=0;//遍历开始节点，（从0节点开始）
	list.num++;
	visited[0]=true;//初始化开始节点访问为true
	while(1)
	{
		/*if(i==amg->vertexnum)//不能用这个判断，因为有可能还没遍历结束 i就==amg->vertexnum
			break;*/
		if(list.num==0)//要用数列是否为空判断
			break;

		for(int j=0;j<amg->vertexnum;j++)
			if(amg->arc[list.date[0]][j]==1&&!visited[j])//查找列表开头定点所连接的定点，追加到列表后面
				{
					list.date[list.num]=j;
					list.num++;
					visited[j]=true;
				}

			//if(visited[list.date[0]]==false)
			//{
				printf("%s ",amg->vertex[list.date[0]].c_str());
				/*visited[list.date[0]]=true;*///在添加进队列的时候标记比较好
	/*		}*/

			for(int j=0;j<list.num;j++)
				list.date[j]=list.date[j+1];
			list.num--;
	}
	return OK;

}


//2、邻接表
int CreateAdjListGraph(AdjListGraph *alg)
{
	int i=0;
	alg->numVertex=0;
	alg->numArc=0;
	while(1)//创建顶点
	{
		printf("请输入邻接表的顶点结束用#：");
		cin>>alg->vlist[i].vertex;
		if(alg->vlist[i].vertex=="#")
			break;
		alg->vlist[i].firstEdge=NULL;
		i++;
		alg->numVertex++;

	}
		while(1)//创建边链表
	{
		int v1=0,v2=0,w=0;
		EdgeNode *edgenode;
		printf("请输入邻接表的顶点对应的边（v1,v2,w）以(0,0,0)结束：");
		scanf("%d,%d,%d",&v1,&v2,&w);

		if(!v1&&!v2&&!w)//(0,0,0)结束
			break;

		edgenode = new EdgeNode();//创建边节点
		edgenode->arcVertex=v2;
		edgenode->weight=w;
		edgenode->next=NULL;

		if(alg->vlist[v1].firstEdge==NULL)//插入边节点
			alg->vlist[v1].firstEdge=edgenode;
		else
		{
			EdgeNode *temp;
			temp=alg->vlist[v1].firstEdge;

			while(temp->next!=NULL)
				temp=temp->next;
			temp->next=edgenode;
		}

		//无向图要添加反方向的边，跟上面的代码一样，只是v1换成v2 v2换成v1
		edgenode = new EdgeNode();//创建边节点
		edgenode->arcVertex=v1;
		edgenode->weight=w;
		edgenode->next=NULL;

		if(alg->vlist[v2].firstEdge==NULL)//插入边节点
			alg->vlist[v2].firstEdge=edgenode;
		else
		{
			EdgeNode *temp;
			temp=alg->vlist[v2].firstEdge;

			while(temp->next!=NULL)
				temp=temp->next;
			temp->next=edgenode;
		}

		alg->numArc++;
	}
		return OK;
}
//->1图邻接表的深度遍历
int AdjListDepthFirstRecursion(AdjListGraph *alg,int i)
{
	if(visited[i])
		return OK;
	printf("%s ",alg->vlist[i].vertex.c_str());//打印顶点
	visited[i]=true;
	AdjListGraph *temp;
	//int j=0;
	temp=alg;
	while(temp->vlist[i].firstEdge)
	{
		AdjListDepthFirstRecursion(alg,temp->vlist[i].firstEdge->arcVertex);
		printf("(%d,%d)",i,temp->vlist[i].firstEdge->arcVertex);
		temp->vlist[i].firstEdge=temp->vlist[i].firstEdge->next;
	}
	return OK;
}
int AdjListDepthFirstSearch(AdjListGraph *alg,int f)
{
	for(int i=0;i<alg->numVertex;i++)
		visited[i]=false;
	printf("邻接表深度遍历:\n");
	AdjListDepthFirstRecursion(alg,f);
	return OK;
}
//->2图邻接表的广度遍历
int AdjListBreadthFirstSearch(AdjListGraph *alg)
{
	//1、初始化访问标识数组
	int i=0;
	for(i;i<alg->numVertex;i++)
		visited[i]=false;
	//2、初始化列表
	list.date[0]=0;
	list.num++;
	visited[0]=true;
	i=0;

	//3、遍历图
	while(1)
	{
		//退出循环条件
		if(list.num==0)
			break;

		//遍历该顶点所连接的定点，并放进队列。
		EdgeNode *temp;
		
		temp=alg->vlist[list.date[0]].firstEdge;
		
		while(temp)
		{
			if(!visited[temp->arcVertex])
			{
			list.date[list.num]=temp->arcVertex;
			list.num++;
			visited[temp->arcVertex]=true;
			}
			temp=temp->next;
		}

		//打印未访问过的节点
			//visited[i]=true;
			printf("%s ",alg->vlist[list.date[0]].vertex.c_str());
			for(int l=0;l<list.num;l++)
				list.date[l]=list.date[l+1];
			list.num--;
			i=list.date[0];
		
	}
return OK;
}



//3、十字链表(就是邻接表与逆邻接表合并)好处是方便同时具有图的出边和入边
int CreateOrthogonalListGraph(OrthogonalListGraph *olg)
{
	int i=0;
	olg->numvertex=0;
	olg->numedge=0;

	while(1)//输入顶点
	{
		printf("请输入图的顶点（以#结束）：");
		cin>>olg->vertexlist[i].vertex;
		if(olg->vertexlist[i].vertex=="#")
			break;
		olg->numvertex++;
		olg->vertexlist[i].edgein=NULL;
		olg->vertexlist[i].edgeout=NULL;
		i++;
	}

	while(1)//输入图的边
	{
		OrthogonalLinkNode *edge;
		edge=new OrthogonalLinkNode();
		edge->inlink=NULL;
		edge->outlink=NULL;
		int v1=0,v2=0,w=0;
		printf("请输入图的有向边（v1,v2,w）(0,0,0)结束：");
		scanf("%d,%d,%d",&v1,&v2,&w);
		if(!v1&&!v2&&!w)
			break;

		edge->outvex=v2;
		edge->invex=v1;//这一步是逆矩阵合并的步骤--edge->invex都等于链表的头顶点

		if(olg->vertexlist[v1].edgeout==NULL)
		{
			olg->vertexlist[v1].edgeout=edge;

		}else
		{
			OrthogonalLinkNode *temp;
			temp=new OrthogonalLinkNode(); 
			temp=olg->vertexlist[v1].edgeout;
			while(temp->outlink)
				temp=temp->outlink;
			temp->outlink=edge;
		}

		//最后处理图的入边与邻接表相比多了这个步骤，这个步骤是把逆邻接表串联起来，开头位置是edgein
		if(olg->vertexlist[v2].edgein==NULL)
		olg->vertexlist[v2].edgein=edge;
		else
		{
			OrthogonalLinkNode *temp;
			temp=new OrthogonalLinkNode(); 
			temp=olg->vertexlist[v2].edgein;
			while(temp->inlink)
				temp=temp->inlink;
			temp->inlink=edge;
		}

	}
	return OK;
}

//4、邻接多重表结构
int CreateAdjacencyMultipleTableGraph(AdjacencyMultipleTableGraph *amtg)
{
	int i=0;
	amtg->numVertex=0;
	amtg->numArc=0;

	while(1)//创建顶点
	{
		printf("请输入邻接表的顶点结束用#：");
		cin>>amtg->vlist[i].vertex;
		if(amtg->vlist[i].vertex=="#")
			break;
		amtg->vlist[i].firstEdge=NULL;
		i++;
		amtg->numVertex++;
	}

	while(1)//创建边
	{
		string v1,v2;
		int vc1,vc2;//顶点的下标
		int w;
		AMTEdgeNode *node,*temp;
		node=new AMTEdgeNode();
		printf("请输入的边(v1 v2 w)用(# # 0)结束：");
		cin>>v1>>v2>>w;
		/*scanf("%s,%s,%d",v1.c_str(),v2.c_str(),&w);*/
		if(v1=="#"&&v2=="#"&&!w)//(0,0,0)结束
		break;

		//查找顶点下标
		for(int i=0;i<amtg->numVertex;i++)
		{
		if(amtg->vlist[i].vertex==v1)
			{
				vc1=i;
				break;
			}
		}

		for(i=0;i<amtg->numVertex;i++)
		{
		if(amtg->vlist[i].vertex==v2)
			{
				vc2=i;
				break;
			}
		}

		node->iver=v1;
		node->jver=v2;
		node->visited=false;//是否访问过
		node->weight=w;
		node->ilink=NULL;
		node->jlink=NULL;

		if(!amtg->vlist[vc1].firstEdge)//列表的firstEdge为空则指向节点
			amtg->vlist[vc1].firstEdge=node;
		if(!amtg->vlist[vc2].firstEdge)//列表的firstEdge为空则指向节点
			amtg->vlist[vc2].firstEdge=node;

		if(amtg->vlist[vc1].firstEdge!=node)
		{
			temp=new AMTEdgeNode();//处理v1的ilink和jlink
			temp=amtg->vlist[vc1].firstEdge;
			while(temp)
			{
				if(temp->iver==v1)
				{
					if(!temp->ilink)//沿着链表找到ilink的最后为空，此时指针可以指向node
					{
						temp->ilink=node;
						break;
					}
					temp=temp->ilink;//否则继续下一个ilink节点
				}
				else 
				{
					if(!temp->jlink&&temp->jver==v1)
					{
						temp->jlink=node;
						break;
					}
					temp=temp->jlink;
				}
			}
		}

		if(amtg->vlist[vc2].firstEdge!=node)
		{
			temp=new AMTEdgeNode();//处理v2的ilink和jlink
			temp=amtg->vlist[vc2].firstEdge;
			while(temp)
			{
				if(temp->iver==v2)
				{
					if(!temp->ilink)
					{
						temp->ilink=node;
						break;
					}
					temp=temp->ilink;
				}
				else 
				{
					if(!temp->jlink&&temp->jver==v2)
					{
						temp->jlink=node;
						break;
					}
					temp=temp->jlink;
				}
			}
		}		
		amtg->numArc++;
	}
	return OK;
}

main.cpp

#include<iostream>
#include<stdio.h>
#include <stdlib.h>
#include<string>
#include"structfun.h"

using std::string;
using std::printf;
using std::scanf;
using std::endl;
using std::to_string;

void main()
{
//图的邻接矩阵
AdjMarGraph amg;
CreateAdjMaxGraph(&amg);//创建图的邻接矩阵
//AdjMarDepthFirstSearch(&amg,0);//图的邻接矩阵深度优先遍历
// AdjMarBreadthFirstSearch(&amg);//广度优先遍历（递归）
 AMBFS(&amg);//（非递归）

//图的邻接表
//AdjListGraph alg;
//CreateAdjListGraph(&alg);
////AdjListDepthFirstSearch(&alg,0);
//AdjListBreadthFirstSearch(&alg);

//图的十字链表
//OrthogonalListGraph olg;
//CreateOrthogonalListGraph(&olg);

//图的邻接多重表
//AdjacencyMultipleTableGraph amtg;
//CreateAdjacencyMultipleTableGraph(&amtg);

system("pause");
}