邻接表图解：看上图（左）
8 9 有向图：这是左图的连接方式看右图就是建表后，表的样子就是 1 开头的 后面写 2 3
1 3 2 2 开头的后写4 5 一次类推
1 2 1 无向图： 就是1 后 2 3 ， 2 后 1 4 5 因为无向吗所以 1 2 也可以看做 2 1
2 4 3
2 5 1
3 6 2
3 7 6
4 8 6
5 8 3
6 7 2
#include<cstdio> #include<cstring> #define maxn 100+10 #define maxm 20000+10 struct Edge { int from,to,val,next; };//from 起点，to终点，val权值，next就是指向下一个边 Edge edge[maxm]; // 边数的数组要比都节点数大 int head[maxn],edgenum;// head数组和edgenum就是记录与一个头结点相连的结点的个数 int n,m; void addEdge(int u,int v,int w) //w 是权值 { Edge E={u,v,w,head[u]}; // 输入的数据存入结构体 edge[edgenum]=E; // edge[] 数据存每组数据 head[u]=edgenum++ // 这里就是记录一个头结点所连的尾结点个数 } void init() { edgenum=0; memset(head,-1,sizeof(head)); } void getMap() { int a,b,c; while(m--) { scanf("%d%d%d",&a,&b,&c); addEdge(a,b,c); addEdge(b,a,c); } } void get_map() // 这里写一个输出链表的函数 方便理解链表的结构和怎样调用链表中的数据 { for(int u=1;u<=n;u++) // 控制每个头结点 { printf("%d: ",u);// 输出头结点 for(int i=head[u];i!=-1;i=edge[i].next)// 控制每条链 printf("%d ",edge[i].to);// 这里输出 （输出什么看题而定） printf("\n"); } }// 记住上边这个函数就可以随意调用链表中的任何一项数据 int main() { while(scanf("%d%d",&n,&m),n||m) { init(); getMap(); printf("\n"); get_map(); } return 0; }
这就是建表和输出表 （这里用的是结构体数组存储 ，不太喜欢用指针存）
测试结果：
8 9
1 3 2
1 2 1
2 4 3
2 5 1
3 6 2
3 7 6
4 8 6
5 8 3
6 7 2
1: 2 3
2: 5 4 1
3: 7 6 1
4: 8 2
5: 8 2
6: 7 3
7: 6 3
8: 5 4
再回看上右图怎么惊人的相似！哈哈这就是邻接表
但是怎么用呢其实也很简单，就是在求最短路径等与图论相关的题用的比较多
这里给一个求最短路的题 hdu-2544-最短路径
