一、定義

圖的鄰接表是一種順序與鏈式存盤相結合的存盤方式，下面給出一個示例，以便大家能夠理解鄰接表這種存盤方式：
無向圖G1

用鄰接表來存盤G1

每一個頂點所在結點都是之后鏈表的頭結點，之后的鏈表結點存放從頭結點所存頂點能夠直接到達頂點的位置下標，如頂點A能夠直接到達D，B兩個頂點，D的頂點存放在3位置，B頂點存放在1位置，所以A之后的鏈表結點存放的值為3和1

二、結構

結構圖

代碼描述

//頂點默認元素個數
#define Default_Vertex_Size 10
#define T  char //頂點元素型別
//邊結構
typedef struct Edge
{
	int dest;  //存放頂點下標
	struct Edge *link;//連接下一個頂點
}Edge;
//頂點結構
typedef struct Vertex
{
	T data;//頂點資料
	Edge *adj;//指向邊結構指標
}Vertex;
//鄰接表
typedef struct GraphLnk
{
	int MaxVertices; //最大頂點個數
	int NumVertices; //實際頂點個數
	int NumEdges;  //邊的條數

	Vertex *NodeTable; //指向頂點結構表
}GraphLnk;

三、常用操作

下面給出存盤無向圖的鄰接表的常用操作（有向圖類似）

初始化

//初始化
void InitGraph(GraphLnk *g)
{
	g->MaxVertices = Default_Vertex_Size;//初始化最大頂點個數
	g->NumEdges = g->NumVertices = 0;//初始化實際頂點個數和邊條數
	//為頂點結構表開辟空間
	g->NodeTable = (Vertex*)malloc(sizeof(Vertex) * g->MaxVertices);
	assert(g->NodeTable != NULL);
	for(int i=0; i<g->MaxVertices; ++i)//頂點結構表的初始化
	{
		g->NodeTable[i].adj = NULL;
	}
}

獲取頂點位置

//獲取頂點位置
int  GetVertexPos(GraphLnk *g, T v)
{
	for(int i=0; i<g->NumVertices; ++i)
	{
		if(g->NodeTable[i].data == v)//判斷是否找到
			return i;
	}
	return -1;
}

列印圖

//列印圖
void ShowGraph(GraphLnk *g)
{
	Edge *p;
	for(int i=0; i<g->NumVertices; ++i)//對頂點進行遍歷
	{
		printf("%d %c:>",i,g->NodeTable[i].data);//輸出頂點
		p = g->NodeTable[i].adj;//指向邊結構
		while(p != NULL)//列印相連的頂點
		{
			printf("%d-->",p->dest);
			p = p->link;
		}
		printf("Nul.\n");
	}
	printf("\n");
}

插入頂點

//插入頂點
void InsertVertex(GraphLnk *g, T v)
{
	//判斷頂點表是否已滿
	if(g->NumVertices >= g->MaxVertices)
		return;
	g->NodeTable[g->NumVertices++].data = v;//插入
}

插入邊

//插入邊：在頂點vertex1和vertex2之間插入一條邊
void InsertEdge(GraphLnk *g, T vertex1, T vertex2)
{
	int v1 = GetVertexPos(g,vertex1);//獲取vertex1的位置
	int v2 = GetVertexPos(g,vertex2);//獲取vertex2的位置
	if(v1==-1 || v2==-1)
		return;

	Edge *s;
	//無向圖是雙向的插入要兩次
	//插入V1 --> V2的邊 頭插法插入
	s = (Edge *)malloc(sizeof(Edge));
	assert(s != NULL);
	s->dest = v2;
	s->link = g->NodeTable[v1].adj;
	g->NodeTable[v1].adj = s;

	//插入V2 --> V1的邊 頭插法插入
	s = (Edge *)malloc(sizeof(Edge));
	assert(s != NULL);
	s->dest = v1;
	s->link = g->NodeTable[v2].adj;
	g->NodeTable[v2].adj = s;

	g->NumEdges++;
}

洗掉邊

//洗掉一條邊：洗掉頂點vertex1和頂點vertex2之間的邊
void RemoveEdge(GraphLnk *g, T vertex1, T vertex2)
{
	int v1 = GetVertexPos(g,vertex1);//獲取v1所在位置
	int v2 = GetVertexPos(g,vertex2);//獲取頂點v2所在位置

	if(v1==-1 || v2==-1)
		return;

	Edge *q = NULL;
	Edge *p;
	//無向圖是雙向的，所以需要洗掉兩邊相對的邊
	//洗掉v1 -- > v2的邊
	p = g->NodeTable[v1].adj;
	while(p != NULL && p->dest != v2)
	{//從v1后面的鏈表中查找v2頂點，其中q指向v2頂點的前驅,p指向v2頂點
		q = p;
		p = p->link;
	}
	if(p == NULL)
		return;

	if(q == NULL)//判斷找到的結點是否是鏈表內的第一個結點
	{//是  頭刪
		g->NodeTable[v1].adj = p->link;//頭刪
	}
	else
	{//不是 直接洗掉
		q->link = p->link;
	}
	free(p); //釋放空間

	//洗掉v2 --> v1的邊
	q = NULL;
	p = g->NodeTable[v2].adj;
	while(p->dest != v1)
	{//從v2后面的鏈表中查找v1頂點，其中q指向v1頂點的前驅,p指向v1頂點
		q = p;
		p = p->link;
	}
	if(q==NULL)//判斷找到的結點是否是鏈表內的第一個結點
	{//是  頭刪
		g->NodeTable[v2].adj = p->link;
	}
	else
	{//不是 直接洗掉
		q->link = p->link;
	}
	free(p); //釋放空間
	g->NumEdges--; //邊數減一
}

洗掉頂點

//洗掉頂點
void RemoveVertex(GraphLnk *g, T vertex)
{
	int v = GetVertexPos(g,vertex);//獲取頂點vertex的位置
	if(v == -1)
		return;

	//洗掉頂點所相連的邊
	Edge *p = g->NodeTable[v].adj;//獲取與頂點vertex相連的鏈表

	int k;
	Edge *t = NULL;//t是s的前驅
	Edge *s;
	while(p!=NULL)
	{
		k = p->dest;//獲取與v相連的頂點k
		s = g->NodeTable[k].adj;//獲取與k連接的鏈表
		while(s!=NULL && s->dest!=v)//從該鏈表中查找與v連接的結點
		{
			t = s;
			s = s->link;
		}
		if(s!=NULL)//判斷是否找到
		{//找到
			if(t==NULL)//判斷是否是第一個結點
			{//是  頭刪
				g->NodeTable[k].adj = s->link;
			}
			else
			{//否 直接洗掉
				t->link = s->link;
			}
			free(s);//釋放空間
		}
		//釋放與v連接鏈表中的k結點
		g->NodeTable[v].adj = p->link;
		free(p);
		p = g->NodeTable[v].adj;
	}
	
	g->NumVertices--;//頂點數減一
	//拿最后一個頂點的值覆寫要洗掉的頂點
	g->NodeTable[v].data = g->NodeTable[g->NumVertices].data;
	g->NodeTable[v].adj = g->NodeTable[g->NumVertices].adj;

	//調整鏈表內結點的指向：將原來標明到最后一個頂點的結點，標明到最后一個結點更改后的位置
	s = g->NodeTable[v].adj;//指向原來與最后一個頂點連接的鏈表
	while(s != NULL)//對鏈表進行搜索，看哪些頂點與原來最后一個頂點相連
	{
		k = s->dest;//獲取相連的頂點位置
		p = g->NodeTable[k].adj;//找到與相鄰頂點連接的鏈表
		while(p != NULL)//對該鏈表進行搜索
		{
			if(p->dest == g->NumVertices)//判斷是否找到指向最后一個頂點的結點
			{//找到
				p->dest = v;//更換指向，指向最后一個頂點更新后的位置
				break;
			}
			p = p->link;//沒找到，則繼續查找下一個
		}
		s = s->link;//進入下一個結點，準備下一個頂點鏈表結點的替換
	}
}

獲取第一個鄰接頂點

//獲取第一個鄰接頂點
int  GetFirstNeighbor(GraphLnk *g, T vertex)
{
	int v = GetVertexPos(g,vertex);//獲取頂點vertex的位置
	if(v == -1)
		return -1;
	//從vertex所連接鏈表的第一個結點處取得第一個鄰接頂點
	Edge *p = g->NodeTable[v].adj;
	if(p != NULL)
		return p->dest;
	return -1;
}

獲取鄰接頂點的下一個頂點

//獲取鄰接頂點的下一個頂點：獲取頂點vertex1的鄰接頂點，該鄰接頂點在vertex1的鄰接頂點vertex2的下一個
int  GetNextNeighbor(GraphLnk *g,  T vertex1, T vertex2)
{
	int v1 = GetVertexPos(g,vertex1);//獲取vertex1的位置
	int v2 = GetVertexPos(g,vertex2);//獲取vertex2的位置
	if(v1==-1 || v2==-1)
		return -1;

	Edge *p = g->NodeTable[v1].adj;//獲取與頂點vertex1相連的鏈表
	while(p != NULL && p->dest != v2)//從鏈表中查找到指向vertex2頂點的結點位置
		p = p->link;
	if(p!=NULL && p->link!=NULL)//判斷是否找到
		return p->link->dest;//找到，那么它的下一個結點就是所求的鄰接頂點
	return -1;
}

銷毀圖

//銷毀圖
void DestroyGraph(GraphLnk *g)
{
	Edge *p;
	//釋放每一個頂點指向的鏈表空間
	for(int i=0; i<g->NumVertices; ++i)
	{
		p = g->NodeTable[i].adj;
		while(p != NULL)
		{
			g->NodeTable[i].adj = p->link;
			free(p);
			p = g->NodeTable[i].adj;
		}
	}
	//釋放存放頂點的空間
	free(g->NodeTable);
	g->NodeTable = NULL;
	g->MaxVertices = g->NumEdges = g->NumVertices = 0;
}

結語

對圖的鄰接表的介紹就到這里啦，希望這篇文章能給予你一些幫助，感謝各位人才的：點贊、收藏和評論，我們下次見，

附錄

測驗代碼：圖之鄰接表詳解（C語言版）