1 数据结构

邻接表用到两个数据结构：

(1) 头结点表，用一维数组存储。包括顶点和指向第一个邻接点的指针。

(2) 每个顶点vi的所有邻接点构成一个线性表，用单链表存储。无向图称为顶点vi的边表，有向图称为顶点vi作为弧尾的出边表，存储的是顶点的序号，和指向下一个边的指针。

头结点：

struct Hnode{ //定义顶点类型
Node *first; //指向第一个邻接点
};

首先创建邻接表表头，初始化每个结点的第一个邻接点为NULL，如图3所示。

表结点：

struct Node{ //定义表结点
int v; //以v为弧头的顶点编号
int w; //边的权值
Node *next; //指向下一个邻接结点
}；

表结点如图4所示↑。

2 创建邻接表

刚开始的时候把顶点表初始化，指针指向null。然后邻接点的表结点插入进来，插入到first指向的结点之前。

(1) 输入第一条边的结点和权值w、v、w分别为1、3、10。

创建一条边，如图5所示。

对应的表结点，如图6所示↑。

将表结点链接到头结点表中，如图7所示。

(2) 输入第二条边的结点和权值w、v、w分别为1、2、12。

创建一条边，如图8所示↑。

对应的表结点，如图9所示↑。

将表结点链接到头结点表中，实际上是插入到1号顶点的邻接单链表的表头，即first指向的邻接点之前，如图10所示↑。

注意：由于后输入的插入到了单链表的前面，因此输入顺序不同，建立的单链表也不同。

3 输出邻接表

4 代码

运行输入：

请输入顶点数n和边数m:
6 9
请依次输入每条边的两个顶点u,v和边的权值w:
1 3 10
1 2 12
2 4 8
3 5 13
3 2 2
4 6 18
4 3 5
5 6 4
5 4 6

运行输出：

----------邻接表如下：----------
v1： [2 12] [3 10]
v2： [4 8]
v3： [2 2] [5 13]
v4： [3 5] [6 18]
v5： [4 6] [6 4]
v6：

附原代码：

//adjlist
#include <iostream>
using namespace std;
const int N=10000;
 struct Node {							//定义表结点
 int v;								//以v为弧头的顶点编号
 int w;								//边的权值
 Node *next;							//指向下一个邻接结点
};
 struct Hnode{							//定义顶点类型
 Node *first;							//指向第一个邻接点
};
Hnode g[N];
int n,m,i,u,v,w;
void insertedge(Hnode &p,int x,int y)	//插入一条边
{
 Node *q;
 q=new(Node);
 q->v=x;
 q->w=y;
 q->next=p.first;
 p.first=q;
}
void printg(int n)						//输出邻接表
{
 cout<<"----------邻接表如下：----------"<<endl;
 for(int i=1;i<=n;i++)
 {
 Node *t=g[i].first;
 cout<<"v"<<i<<"： ";
 while(t!=NULL)
 {
 cout<<"["<<t->v<<" "<<t->w<<"] ";
 t=t->next;
 }
 cout<<endl;
 }
}
int main()
{
 cout<<"请输入顶点数n和边数m:"<<endl;
 cin >>n>>m;
 for(i=1; i<=n; i++)
 g[i].first=NULL;
 cout<<"请依次输入每条边的两个顶点u,v和边的权值w:"<<endl;
 for(i=0;i<m;i++)
 {
 cin>>u>>v>>w;
 insertedge(g[u],v,w);
									//无向图时还要插入一条反向边
 }
 printg(n);						//输出邻接表
	system("pause");
 return 0;
}
－End－

邻接表存储结构（简单理解图的存储结构）

1 数据结构

2 创建邻接表

4 代码