ajacency_list.cpp

C++的电子教程

//程序实例8_2
//图的邻接表表示
#include<stdio.h>
#include<stdlib.h>
#define Max 50

typedef struct e_node               //定义边结点的数据类型
{	int adjvex;
	int weight;
	struct e_node *next;
}E_node;

typedef struct v_node              //定义顶点结点的数据类型
{	int vertex;
	E_node *link;
}V_node;

V_node head[Max];                  //定义顶点结点的数组

//邻接表的建立
void adjlist(V_node head[],int n,int m,int t)  //t的0、1值分别表示无向、有向图,n=顶点数，m=边数
{	int i,w=1,v=1,weight;
	E_node *p;
	for(i=1;i<=n;i++)       //顶点结点初始化
	{	head[i].link=NULL;	//////////////////////////////////
		head[i].vertex=i;   //顶点信息设为顶点编号
	}
	i=1;                    //输入边计数
	while((v>0) && (w>0)&&i<=m)   //以起点（或终点）为0，结束边的输入
	{	printf("Input Edge %d's start point : ",i);
		scanf("%d",&v);
		printf("==> end point : ");
		scanf("%d",&w);
		if (t==1)
		{
			printf("Input the Weight Value : ");
			scanf("%d",&weight);
		}
		if((v>n) || (w>n))
		{	printf("Error! Input again.");
			continue;
		}
		if((v>0) && (w>0))
		{	p=(E_node *)malloc(sizeof(E_node));  //新结点存放w
			p->adjvex=w;    //终点为w的边结点链到第v个链表
			p->next=head[v].link;
			head[v].link=p;
			if(t==0)        //无向图
			{	p=(E_node *)malloc(sizeof(E_node));  //新结点存放v
				p->adjvex=v;  //终点为v的边结点链到第w个链表
				p->next=head[w].link;
				head[w].link=p;
			}
		    if(t==1)        //有向图
				p->weight=weight;   //赋权值
		}

		printf("Edge %d : (v%d,v%d)\n",i,v,w);  //输出第i条边
		i++	;
	}
}

//输出邻接表
void Print(V_node head[],int n,int t)
{	int i;
	E_node *p;
	for(i=1;i<=n;i++)
	{	printf("\nhead[%d]:",i);
		if(head[i].link)
		{	p=head[i].link;
			while(p)
			{	printf("->[%d]",p->adjvex);
			    if (t==1)      //有向图
					printf("[%d]",p->weight);  //输出权值
				p=p->next;
			}
			printf("\n");
		}
	}
}

//主函数
void main()
{
	int n,m,t;
	while(1)
	{	
		printf("\n 0: 无向图");
		printf("\n 1: 有向图");
		printf("\n 2: Exit");
		printf("\nPlease choose=>");
		scanf("%d",&t);
		switch(t)
		{	case 0:
			case 1:
				printf("\n 请输入图的顶点数n、边数m：");
				scanf("%d %d",&n,&m);
				printf("\n邻接表的建立：");
				adjlist(head,n,m,t);
				printf("\n输出邻接表: ");
				Print(head,n,t);
				break;
			default:
				return;
		}
	}
}