邻矩深度.cpp

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

#include"lj.h"

void dfs(adjmax adj,int i,int n);
void dfstrav(adjmax adj,int n);
int nextadjvex(adjmax adj,int i,int k,int n);
int first(adjmax adj,int i,int n);

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;
	for(k=1;k<=e;k++)
	{
		getchar();
		printf("第%d条边=>起点:  ",k);
		b=getchar();
		getchar();
		for(i=1;i<=n&&adj.vexs[i].data!=b;i++)  
			;	
		if(i>n)
		{
			printf("输入的起点不存在!\n");
			exit(0);
		}
		printf("  \t 终点:  ");
		t=getchar();
		getchar();
		for(j=1;j<=n&&adj.vexs[j].data!=t;j++)  
			;
		if(j>n)
		{
			printf("输入的终点不存在!\n");
			exit(0);
		}
		printf(" \t 权值:  ");
		scanf("%d",&w);
		adj.edges[i][j]=adj.edges[j][i]=w;
	}
	printf("该图对应的邻接矩阵为:\n");
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			printf("%4d",adj.edges[i][j]);
		printf("\n");
	}
	printf("深度遍历图输出: \n");
	dfstrav(adj,n);
	printf("\n");
}

void dfstrav(adjmax adj,int n)
{
	int i;
	for(i=1;i<=n;i++)
		visited[i]=0;
	for(i=1;i<=n;i++)
		if(!visited[i])
			dfs(adj,1,n);
}

void dfs(adjmax adj,int i,int n)
{
	int k;
	visited[i]=1;
	printf("%3c",adj.vexs[i].data);
	for(k=first(adj,i,n);k>0;k=nextadjvex(adj,i,k,n))
		if(!visited[k])
			dfs(adj,k,n);
}

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 nextadjvex(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;
}