邻表深度.cpp

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

#include"lb.h"

void travgraph(adjlist g,int n);
void dfs(adjlist adj,int v);

void main()
{
	adjlist g;
	int e,i,s,d,n;
	struct edgenode *p,*q;
	printf("输入结点数(n)和边数(e):  ");
	scanf("%d%d",&n,&e);
	for(i=1;i<=n;i++)
	{
		getchar();
		printf("第%d个结点信息:",i);
		scanf("%c",&g[i].data);
		g[i].link=NULL;
	}
	for(i=1;i<=e;i++)
	{
		printf("第%d条边的起点序号,终点序号:",i);
		scanf("%d%d",&s,&d);
		p=(struct edgenode*)malloc(sizeof(struct edgenode));
		q=(struct edgenode*)malloc(sizeof(struct edgenode));
		p->adjvex=d;
		p->info=g[d].data;
		q->adjvex=s;
		q->info=g[s].data;
		p->next=g[s].link;			//p插入顶点s是邻接表中
		g[s].link=p;
		q->next=g[d].link;			//q插入顶点d的邻接表中
		g[d].link=q;
	}
	travgraph(g,n);
	dfs(g,n);
	printf("\n");
}

//遍历邻接表表示的一个图
void travgraph(adjlist g,int n)
{
	int i;
	struct edgenode *p;
	printf("建立的邻接表如下:\n");
	for(i=1;i<=n;i++)
	{
		printf("[%d,%c]=>",i,g[i].data);
		p=g[i].link;
		while(p!=NULL)
		{
			printf("(%d,%c)-->",p->adjvex,p->info);
			p=p->next;
		}
		printf("\n");
	}
}

void dfs(adjlist g,int n)
{
	int i;
	struct edgenode *p;
	for(i=1;i<=n;i++)
		visited[i]=0;
	visited[1]=1;
	printf("%c",g->data);					//取v的边的表头指针
	p=g[1].link;
	while(p!=NULL)
	{
		if(visited[p->adjvex]==0);	//从v的未访问过的邻接点出发进行深度遍历
			dfs(g,n);
		p=p->next;					//找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 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;
}
*/