邻接表

特点：

          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 ; else q = 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); }

邻接表结果：

逆向邻接表

        逆向邻接表的用处：为了方便了解入度和出度的信息，会将邻接表和逆向邻接表结合起来。这称为十字链表

【未完待续】