邻接表
特点：
1、想要知道某个顶点的度，就去查找这个顶点的边表中结点的个数
2、若想判断顶点 Vi 到 Vj是否存在边，只需测试顶点 Vi 的边表中adjvex是否存在 Vj 的下标。
3、若求顶点的所有邻接点，其实就是对此顶点的边表进行遍历，得到adjvex域对应的顶点就是邻接点。
#include <iostream>
#include <stdlib.h>
#define maxvex 4
using namespace std;//边表结点
typedef struct edgenode
{int adjvex; //下标int weight; //权值，可有可没有 struct edgenode *next;
}EdgeNode;
//顶点结点
typedef struct node
{int data;EdgeNode *first; //边表头指针
}VertexNode,AdjList[maxvex];
//二次封装
typedef struct
{AdjList adjlist;int numetex, numedge;
}GraAdjList;//创建邻接表
void CreateAlGraph(GraAdjList &g)
{int m, n;EdgeNode *e=NULL;EdgeNode *q = NULL;cout << "请输入顶点数和边数:" << endl;cin >> g.numetex >> g.numedge;cout << "请输入顶点的信息：" << endl;//获取顶点的信息for (int i = 0;i < g.numetex;i++){cin >> g.adjlist[i].data;g.adjlist[i].first = NULL;}//建立边表，链表采用头插法for (int k=0;k<g.numedge;k++){cout << "请输入边（Vi,Vj）的顶点下标：" << endl;cin >> m >> n;//链表结点e = (EdgeNode *)malloc(sizeof(EdgeNode));e->adjvex = n;e->next = NULL;//头插法建链if (g.adjlist[m].first == NULL)q=g.adjlist[m].first = e ;elseq = q->next = e;}}
void print(const GraAdjList &g)
{EdgeNode *p;for (int k = 0;k < g.numetex;k++){cout << "顶点" << k << ": ";for (p = g.adjlist[k].first; p;p = p->next)cout << p->adjvex << " ";if (p == NULL)cout << endl;}
}
int main()
{GraAdjList gralist;CreateAlGraph(gralist);print(gralist);
}
邻接表结果：
逆向邻接表
总结：
邻接表中的链表是以当前顶点作为起点，存储的是终点顶点的下标。
逆邻接表中的链表是以当前顶点作为终点，存储的是各个起点的下标。
所以：
邻接表 很容易知道 出度 的信息； 逆邻接表 很容易知道 入度 的信息。
逆向邻接表的用处：为了方便了解入度和出度的信息，会将邻接表和逆向邻接表结合起来。这称为十字链表
带权的网图
【未完待续】
