图-邻接矩阵表示

代码区

#include<stdio.h>
#include<stdlib.h>
#define N 20
//定义顶点数据类型
typedef int Vertex[N];
//定义边的数据类型
typedef int Edge[N][N];


//定义的图类型
typedef struct Graph
{
	Vertex vers;//int Vers[N]; //存储定点的信息
	Edge edges;//int edges[N][N];//存储边的信息
	int vernum,edgenum;//顶点数量,边数量 
}Graph;

int visit[N];//标志数组,是否已经被查找过,初始0,查找过变1 


//定义队列
typedef struct SeQueue
{
	int *elem;
	int front,rear;
}SeQueue;
//定义初始化队列
void InitSeQueue(SeQueue &Q)
{
	Q.elem = (int *)malloc(N * sizeof(int));
	Q.front = Q.rear = 0;
}
//入队
void EnterSeQueue(SeQueue &Q,int e)
{
	Q.elem[Q.rear] = e;
	Q.rear = (Q.rear + 1) % N;
}
//出队
void OutSeQueue(SeQueue &Q,int &e)
{
	e = Q.elem[Q.front];
	Q.front = (Q.front + 1) % N;
}

//判断队列是否为空 
int IsEmpty(SeQueue Q){
	if(Q.rear == Q.front)
		return 1;
	else
		return 0;
}


//求一个顶点在顶点集合中的位置
int LocateVerPos(Graph G,int v)
{
	int i = 0;
	while(G.vers[i] != v)
	{
		i ++;
	}
	return i;
	
}

//	初始化图
void CreateGraph(Graph &G)
{
	int v1,v2;//顶点 
	int i,j,pos1,pos2;
	printf("输入顶点数量,边数量:\n");
	scanf("%d%d",&G.vernum,&G.edgenum);//输入顶点数量,边数量
	printf("定义i个顶点名称: \n"); 
	for(i = 0;i < G.vernum; i ++)
		scanf("%d",&G.vers[i]);//定义i个顶点名称 
		
	//初始化图的边二维数组
	for(i = 0;i < G.vernum; i ++)
		for(j = 0;  j < G.vernum; j ++)
			G.edges[i][j] = 0;//初始化图的n*n矩阵//全部为0 
	printf("打印初始化无向矩阵图:\n");
	for(i = 0;i < G.vernum;i ++)
		printf("%d\t",G.vers[i]);//最上面一行顶点v1,v2,v3,v4.. 
	printf("\n");
	for(i = 0; i < G.vernum; i ++) 
	{
		for(j = 0; j < G.vernum; j ++)
			printf("%d\t",G.edges[i][j]);
		printf("%d",G.vers[i]);//最右边一行 
		printf("\n");
	}
	
	for(i = 1; i <= G.edgenum; i ++)//边的数量次数//有边0才会变1 
	{
		printf("输入相连的两个顶点:\n");
		scanf("%d%d",&v1,&v2);//输入v1,v2//G.vernum == v1 == v2//v1,v2共用一个G.vernum数量 
		pos1 = LocateVerPos(G,v1);//找出v1在顶点集合中的位置 
		pos2 = LocateVerPos(G,v2);//找出v2在顶点集合中的位置 
		G.edges[pos1][pos2] = 1;//矩阵中i行j列变为1 
		G.edges[pos2][pos1] = 1;//矩阵对称 
	}
	printf("输出所有顶点 \n");
	for(i = 0; i < G.vernum; i ++)//输出所有顶点 
		printf("%d\t",G.vers[i]);
	printf("\n");
	
	printf("打印无向图邻接矩阵\n");
	for(i = 0;i < G.vernum;i ++)
		printf("%d\t",G.vers[i]);//最上面一行顶点v1,v2,v3,v4.. 
	printf("\n");
	for(i = 0; i < G.vernum; i ++)//打印无向图邻接矩阵 
	{
		for(j = 0; j < G.vernum; j ++)
			printf("%d\t",G.edges[i][j]);
		printf("%d",G.vers[i]);//输出所有顶点//顶点在每一行后面位置 
		printf("\n");
	}
}


//查找图中基于顶点v的第一个邻接顶点的位置
int LocateFirstVer(Graph G,int v1)//v1时顶点名称 
{
	int i = 1/*初始第一行*/,j;//i为顶点v在邻接矩阵中的行位置//第i行 
	while(G.vers[i-1]){//G.vers默认从第0行开始 
		if(v1 != G.vers[i-1])
			i++;
		else
			break;
	}
	printf("顶点%d所在行数为%d(从0行开始计数)\n",v1,i-1);
	for(j = 0; j < G.vernum; j ++){//顶点数量 
		if(G.edges[i-1][j] == 1){//与顶点v相连的顶点在矩阵图中下标为1 
			return j;//j是要找的顶点的位置 
		}
		else
			continue; 
	}
	return -1;
}


//查找图中基于顶点v挨着adjpos的下一个邻接顶点的位置
int LocateNextVer(Graph G,int v2,int adjpos)
{
	int i = 1;/*初始第一行*///i为顶点v在邻接矩阵中的行位置//第i行 
	while(G.vers[i-1]){//G.vers默认从第0行开始 
		if(v2 != G.vers[i-1])
			i++;
		else
			break;
	}
	printf("顶点%d所在行数为%d(从0行开始计数)\n",v2,i-1);
	int j;//查找与顶点v相连的顶点位置//即矩阵中v行j列的位置 
	for(j = adjpos; j < G.vernum; j ++)//j从adjpos位置后开始查找 
		if(G.edges[i-1][j] == 1)//因为一行中可能有多个1,即多个顶点与v相连, 
			return j;
		return -1;
}


//递归回起始顶点的另一条边 
void DFS(Graph G,int v)//从第0行开始遍历//v == 0开始 
{
	int adjpos;//开始查找的位置 
	printf("第%d个顶点\n",v);//第一个顶点 
	visit[v] = 1;//代表第一个顶点已查找过 
	printf("行数变成了v行所在的"); 
	v = G.vers[v];//把v从行数变成行所在的顶点 
	printf("顶点名称%d\n",v);
	for(adjpos = LocateFirstVer(G,v);adjpos >= 0;adjpos = LocateNextVer(G,v,adjpos))
		if(visit[adjpos] == 0)//未查找过 也可!visit[adjpos] 
			DFS(G,adjpos);//adjpos作为v递归
	//有问题 
}

//深度优先搜索遍历图
void DFSTraverse(Graph G)
{
	int i;
	for(i = 0; i < G.vernum; i ++)//顶点数量 
		visit[i] = 0;//标志初始化为0 
	for(i = 0;i < G.vernum; i ++)
		if(visit[i] == 0)//未查找过 也可!visit[i] 
			DFS(G,i);
}


// 广度优先搜索遍历图
void BFSTraverse(Graph G)//按层数逐渐加深遍历//类似二叉树的顺序遍历 
{
	SeQueue Q;//栈Q 
	int i,v;
	InitSeQueue(Q);//初始化队列 
	for(i = 0; i < G.vernum; i ++)
		visit[i] = 0;//初始化visit数组//全部赋值为0 
	for(i = 0; i < G.vernum; i ++)
	{
		if(visit[i] == 0 )//未查找过 
		{
			printf("第%d个顶点:\t",i+1);//打印第i行顶点的名称 
			visit[i] = 1;
			EnterSeQueue(Q,G.vers[i]);//入栈 
			
		}
	}
	printf("\n"); 
	while(!IsEmpty(Q))//当队列不空 
	{
		OutSeQueue(Q,i);//出栈
		printf("顶点名称:%d\t",i);
	}

}
int main()
{
	Graph G;//定义图类型的变量
	SeQueue Q; 
	int v1,v2,adjpos;
	
	CreateGraph(G);//创建邻接矩阵 
	
	printf("查找图中基于顶点v的第一个邻接顶点的位置,请输入你要查找的顶点:\t");
	scanf("%d",&v1); 
	printf("\n第一个邻接顶点位置:%d\n",LocateFirstVer(G,v1));
	
	printf("===============================================\n"); 
	printf("查找图中基于顶点v的从第adjpos个邻接顶点开始查找的位置,请输入你要查找的位置及顶点:\t");
	scanf("%d%d",&adjpos,&v2);
	printf("\n从第%d个开始的邻接顶点位置:%d\n",adjpos,LocateNextVer(G,v2,adjpos));
	
	printf("===============================================\n"); 
	
	//DFSTraverse(G);
	BFSTraverse(G);

}

测试区