邻接表既适用于存储无向图,也适用于存储有向图。邻接表常用于稀疏图的存储。
邻接表存储图主要在于将图的各顶点建立一个链表,链表记录该顶点的邻接点的在数组的位置。
#define MAX_VERTEX_NUM 10 // 最大顶点数
#define INF 32767 // 不邻接
typedef char verType; // 顶点类型
typedef string infoType; // 弧上信息类型
typedef enum { UDG, DG, UDN, DN }Graph; // 无向图、有向图、无向网、有向网
// 弧
struct ArcNode {ArcNode() :adjIndex(INF), Next(NULL), info(NULL) {}int adjIndex; // 邻接节点下标ArcNode* Next; // 下一邻接节点 infoType* info;
};
// 顶点
typedef struct VerNode {VerNode() :first(NULL) {}VerNode(verType ver) :vertex(ver), first(NULL) {}verType vertex; // 数据域ArcNode* first; // 指向第一个邻接节点
}AdjList[MAX_VERTEX_NUM];
// 邻接表
struct ALGraph {AdjList adj; // 邻接表int ver_num; // 顶点数int arc_num; // 边数Graph Kind; // 图类型
};
获取顶点在数组位置:
// 获取顶点位置
int LocateVertex(ALGraph &graph, verType ver) {for (int i = 0; i < graph.ver_num; ++i) {if (ver == graph.adj[i].vertex) return i;}return -1;
}
创建图:
// 创建无向图
void CreatUDG(ALGraph &graph) {graph.Kind = UDG;cout << "输入顶点数、边数>>" << endl;cin >> graph.ver_num >> graph.arc_num;cout << "输入顶点信息>>" << endl;for (int i = 0; i < graph.ver_num; ++i) {cin >> graph.adj[i].vertex;graph.adj[i].first = NULL;}verType v1, v2;int index1, index2;for (int i = 0; i < graph.arc_num; ++i) {cout << "输入邻接的顶点>>" << endl;cin >> v1 >> v2;index1 = LocateVertex(graph, v1);index2 = LocateVertex(graph, v2);if (index1 < 0 || index2 < 0) {cout << "邻接顶点有误" << endl;--i;continue;}// 头插法插入邻接表ArcNode* arc1 = new ArcNode();ArcNode* arc2 = new ArcNode();arc1->adjIndex = index2;arc1->Next = graph.adj[index1].first;graph.adj[index1].first = arc1; // 头插arc2->adjIndex = index1;arc2->Next = graph.adj[index2].first;graph.adj[index2].first = arc2; // 头插cout << "弧上是否存储信息" << endl;cout << " 1.是 0、否" << endl;int Is_info;cin >> Is_info;if (Is_info) {cout << "输入弧上信息" << endl;infoType INFO;cin >> INFO;graph.adj[index1].first->info = new infoType(INFO);graph.adj[index2].first->info = new infoType(INFO);}}
}
// 创建有向图
void CreatDG(ALGraph &graph) {graph.Kind = DG;cout << "输入顶点数、边数>>" << endl;cin >> graph.ver_num >> graph.arc_num;cout << "输入顶点信息>>" << endl;for (int i = 0; i < graph.ver_num; ++i) {cin >> graph.adj[i].vertex;graph.adj[i].first = NULL;}verType v1, v2;int index1, index2;for (int i = 0; i < graph.arc_num; ++i) {cout << "输入邻接的顶点>>" << endl;cin >> v1 >> v2;index1 = LocateVertex(graph, v1);index2 = LocateVertex(graph, v2);if (index1 < 0 || index2 < 0) {cout << "邻接顶点有误" << endl;--i;continue;}cout << "弧上是否存储信息" << endl;cout << " 1.是 0、否" << endl;int Is_info;cin >> Is_info;ArcNode* arc = new ArcNode();arc->adjIndex = index2;arc->Next = graph.adj[index1].first;graph.adj[index1].first = arc; // 头插if (Is_info) {cout << "输入弧上信息" << endl;infoType INFO;cin >> INFO;graph.adj[index1].first->info = new infoType(INFO);}}
}
输出图的邻接表:
// 遍历
void Traverse(ALGraph &graph) {for (int i = 0; i < graph.ver_num; ++i) {ArcNode* T = graph.adj[i].first;int index;while (T) {index = T->adjIndex;cout << "顶点 " << graph.adj[i].vertex << " <----> "<< "顶点 " << graph.adj[index].vertex;if (T->info) {cout << " 弧上信息:" << *(T->info);}cout << endl;T = T->Next;}}
}