数据结构_图—邻接表(C语言)

(一)邻接表图文解析

邻接表的结构比较复杂，包括顶点的存储结构和边的存储结构；
顶点结点包括数据域和指针域，边结点包括数据域、指针域和边结点所指向的顶点位置；
其中顶点结点由<mark>一维数组</mark>储存，每个顶点结点又以链栈的结构连接着边结点；

图的形式与邻接表的形式：

(二)邻接表代码解析

2.1 邻接表的存储结构

typedef struct	EdgeNode	//边结点
{
	int adjvex;				//邻接点
	OtherInfo info;			//数据域，边的权值
	struct EdgeNode *next;	//指针域，指向下一条边 
}EdgeNode;

typedef struct				//顶点结点
{
	VerTexType data;		//数据域，顶点结点的数据
	EdgeNode *firstedge;	//指针域，指向对应的边
}VextexNode,AdjList[MAXVEX];

typedef struct			
{
	AdjList adjList;		//存放顶点结点的数组
	int numNodes,numEdges;	//顶点数和边数
}ALGraph;

2.2 邻接表的创建

void  CreateALGraph(ALGraph &G)
{
	int i,j,k;
	OtherInfo w;
	printf("请输入顶点数和边数:");
	scanf("%d %d",&G.numNodes,&G.numEdges);

	for(i=0;i<G.numNodes;i++)//顶点结点
	{
		fflush(stdin);
		printf("请输入第%d个顶点数据:",i+1);
		scanf("%c",&G.adjList[i].data);//输入顶点结点数据
		G.adjList[i].firstedge=NULL;//初始化边结点的指针为空
	}
	
	for(k=0;k<G.numEdges;k++)//边结点
	{
		printf("请输入边(vi,vj)上的顶点序号及权值:");
		scanf("%d %d %d",&i,&j,&w);
		EdgeNode *p1,*p2;//创建两个新的边结点

		p1=(EdgeNode *)malloc(sizeof(EdgeNode));//为边结点分配空间
		p1->adjvex=j;				//新边结点所指向顶点的数组位置
		p1->next=G.adjList[i-1].firstedge;	//新边结点p1插入顶点结点后
		G.adjList[i-1].firstedge=p1;		//新边结点p1插入顶点结点后
		p1->info=w;//边结点的权值
		
		//因为为无向图，所以同时需要在相应顶点上接入相同权值的边结点
		p2=(EdgeNode *)malloc(sizeof(EdgeNode));
		p2->adjvex=i;
		p2->next=G.adjList[j-1].firstedge;
		G.adjList[j-1].firstedge=p2;
		p2->info=w;
	}
}

2.3 邻接表的遍历

void TravelALGraph(ALGraph G)
{
	int i;
	EdgeNode *p;
	for(i=0;i<G.numNodes;i++)
	{
		p=G.adjList[i].firstedge;
		while(p)
		{
			printf("第%d个顶点(边的权值:%d)-->第%d个顶点\n",i+1,p->info,p->adjvex);
			p=p->next;		
		}
		if(!p)
			printf("\n");
	}
}

2.4 邻接表的查找

void LocateALGraph(ALGraph G)
{
	int i,j;
	EdgeNode *p;
	printf("请输入顶点序号:");
	scanf("%d",&i);
	printf("该顶点信息为:%c\n",G.adjList[i-1].data);

	printf("请输入需要查找的边的两个顶点:");
	scanf("%d %d",&i,&j);
	p=G.adjList[i-1].firstedge;//从位置为i-1的顶点出发
	while(p)//遍历该顶点的所有边
	{
		if(p->adjvex==j)//查找到连接着顶点位置为j的边
		{
			printf("该边的权值为:%d\n",p->info);
			break;
		}
		else
			p=p->next;
	}
}

(三)源代码及测试

3.1 源代码

#include<stdio.h>
#include<malloc.h>

#define MAXVEX 100 

typedef int OtherInfo;	
typedef char VerTexType;	

typedef struct	EdgeNode	
{
	int adjvex;			
	OtherInfo info;			
	struct EdgeNode *next;	
}EdgeNode;

typedef struct			
{
	VerTexType data;		
	EdgeNode *firstedge;	
}VextexNode,AdjList[MAXVEX];

typedef struct			
{
	AdjList adjList;		
	int numNodes,numEdges;
}ALGraph;

void  CreateALGraph(ALGraph &G)
{
	int i,j,k;

	OtherInfo w;

	printf("请输入顶点数和边数:");
	scanf("%d %d",&G.numNodes,&G.numEdges);

	for(i=0;i<G.numNodes;i++)
	{
		fflush(stdin);
		printf("请输入第%d个顶点数据:",i+1);
		scanf("%c",&G.adjList[i].data);
		G.adjList[i].firstedge=NULL;
	}
	
	for(k=0;k<G.numEdges;k++)
	{
		printf("请输入边(vi,vj)上的顶点序号及权值:");
		scanf("%d %d %d",&i,&j,&w);
		EdgeNode *p1,*p2;

		p1=(EdgeNode *)malloc(sizeof(EdgeNode));
		p1->adjvex=j;				
		p1->next=G.adjList[i-1].firstedge;
		G.adjList[i-1].firstedge=p1;
		p1->info=w;

		p2=(EdgeNode *)malloc(sizeof(EdgeNode));
		p2->adjvex=i;
		p2->next=G.adjList[j-1].firstedge;
		G.adjList[j-1].firstedge=p2;
		p2->info=w;
	}
}
void TravelALGraph(ALGraph G)
{
	int i;
	EdgeNode *p;
	for(i=0;i<G.numNodes;i++)
	{
		p=G.adjList[i].firstedge;
		while(p)
		{
			printf("第%d个顶点(边的权值:%d)-->第%d个顶点\n",i+1,p->info,p->adjvex);
			p=p->next;		
		}
		if(!p)
			printf("\n");
	}
}
void LocateALGraph(ALGraph G)
{
	int i,j;
	EdgeNode *p;
	printf("请输入顶点序号:");
	scanf("%d",&i);
	printf("该顶点信息为:%c\n",G.adjList[i-1].data);

	printf("请输入需要查找的边的两个顶点:");
	scanf("%d %d",&i,&j);
	p=G.adjList[i-1].firstedge;//从位置为i-1的顶点出发
	while(p)//遍历该顶点的所有边
	{
		if(p->adjvex==j)//查找到连接着顶点位置为j的边
		{
			printf("该边的权值为:%d\n",p->info);
			break;
		}
		else
			p=p->next;
	}
}
int main()
{
	ALGraph G;	
	CreateALGraph(G);
	TravelALGraph(G);
	LocateALGraph(G);
	return 0;
}