邻矩广度.cpp

数据结构中关于图的操作,含多种操作方法例子

#include"lj.h"

int first(adjmax adj,int i,int n);
void bfs(adjmax adj,int n);
int next(adjmax adj,int i,int k,int n);

void bfs(adjmax adj,int n)
{
	int front=0,rear=1,i,v,queue[MAXVEX],p;
	char ch;
	for(i=1;i<=n;i++)
		visited[i]=0;
	visited[1]=1;
	v=adj.vexs[1].num;
	ch=adj.vexs[v].data;
	printf("%3c",ch);
	queue[rear]=v;							//初始顶点入队列
	while(front!=rear)
	{
		front=(front+1)%MAXVEX;
		v=queue[front];						//按访问次序依次出队列
		p=first(adj,v,n);						//找v的邻接点
		while(p>0)
		{
			if(visited[p]==0)
			{
				visited[p]=1;
				printf("%3c",adj.vexs[p].data);		//访问该结点并使之入队列
				rear=(rear+1)%MAXVEX;
				queue[rear]=adj.vexs[p].num;
			}
			p=next(adj,v,p,n);						//找v的下一个接点
		}
	}
}

int first(adjmax adj,int i,int n)
{
	int j;
	for(j=1;j<=n;j++)
		if(adj.edges[i][j]!=0)
			return j;
	 return -1;
}

int next(adjmax adj,int i,int k,int n)
{
	int j;
	for(j=k+1;j<=n;j++)
		if(adj.edges[i][j]!=0)
			return j;
		return -1;
}


void main()
{
	int i,j,k,w,n,e;
	char b,t;
	adjmax adj;
	printf("输入顶点数(n)和边数(e):  ");
	scanf("%d%d",&n,&e);
	for(i=1;i<=n;i++)
	{
		getchar();
		printf("  第%d个顶点的信息:  ",i);
		scanf("%c",&adj.vexs[i].data);
		adj.vexs[i].num=i;
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			adj.edges[i][j]=0;
		getchar();
	for(k=1;k<=e;k++)
	{
		
		printf("第%d条边:  ",k);
		scanf("%c%c",&b,&t);
		getchar();
		for(i=1;i<=n&&adj.vexs[i].data!=b;i++)  
			;	
		if(i>n)
		{
			printf("输入的起点不存在!\n");
			exit(0);
		}
		for(j=1;j<=n&&adj.vexs[j].data!=t;j++)  
			;
		if(j>n)
		{
			printf("输入的终点不存在!\n");
			exit(0);
		}
		adj.edges[i][j]=adj.edges[j][i]=1;
	}
	printf("该图对应的邻接矩阵为:\n");
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			printf("%4d",adj.edges[i][j]);
		printf("\n");
	}
	printf("广度遍历图输出: \n");
	bfs(adj,n);
	printf("\n");
}