数据结构之图的邻接表示意法

数据结构之图的邻接表表示法

邻接表表示法：

就是使用基本链表来链接每个顶点的邻近顶点，每个顶点的结构，如下图所示：

对于如下的无向图：

其对应的邻接表表示法如下图所示：

代码实现如下：

/*
File Name	：	ALGraph.h
Copyright	:

Date time	:	2012.8.7
Author		:
Description	:
*/
struct node
{
	int vertex;
	struct node* next;
};

typedef struct node* graph;
struct node head[6];

/*
File Name	：	ALGraph.c
Copyright	:

Date time	:	2012.8.7
Author		:
Description	:	
*/
#include <stdio.h>
#include <stdlib.h>
#include "ALGraph.h"

//创建图

void create_graph(int* node, int num)
{
	graph newnode;
	graph ptr;
	int from;
	int to;
	int i;

	for(i = 0; i < num; i++)
	{
		from = node[i * 2];		//边的起点
		to = node[i * 2 + 1];	//边的终点


		// 创建新顶点内存
		newnode = (graph)malloc(sizeof(struct node));
		newnode->vertex = to;
		newnode->next = NULL;
		ptr = &(head[from]);
		while(ptr->next != NULL)
			ptr = ptr->next;

		ptr->next = newnode;
	}
}

int main()
{
	graph ptr;
	int node[12][2] = { {1,2},{2,1},
						{1,3},{3,1},
						{2,3},{3,2},
						{2,4},{4,2},
						{3,5},{5,3},
						{4,5},{5,4}};
	int i;
	for(i = 1; i <= 5; i++)
	{
		head[i].vertex = i;
		head[i].next = NULL;
	}

	create_graph(node, 12);
	
	printf("图的邻接表内容：\n");

	for(i = 1; i <= 5; i++)
	{
		printf("顶点%d => ", head[i].vertex);
		ptr = head[i].next;

		while(ptr != NULL)
		{
			printf(" %d", ptr->vertex);
			ptr = ptr->next;
		}
		printf("\n");
	}

	system("pause");
	return 0;
}

输出如下：

内容来至《数据结构C语言版》