多重邻接表

针对无向图#include stdio.h #include stdlib.h #include string.h #define inf 10001 // 定义无穷大本程序未实际使用 // 无向图的边节点结构邻接多重表表示 typedef struct ENode { //int w; // 如果需要权值可以打开 int x_i; // 边的一个端点顶点下标 int y_i; // 边的另一个端点顶点下标 struct ENode* xnext;// 指向依附于 x_i 顶点的下一条边 struct ENode* ynext;// 指向依附于 y_i 顶点的下一条边 } ENode; // 图的顶点结构 struct Graph { char data; // 顶点存储的字符信息 ENode* first; // 指向该顶点的第一条边 } g[105]; // 最多支持 105 个顶点 int n, m; // n: 顶点数, m: 边数 // 根据字符查找对应顶点的下标1-based int find(char x) { int i; for(i 1; i n; i) { if(g[i].data x) { break; } } return i; } int main(){ // 输入顶点数和边数 scanf(%d %d, n, m); getchar(); // 吸收换行符 // 输入每个顶点的字符并初始化边链表为空 for(int i 1; i n; i) { scanf(%c, g[i].data); g[i].first NULL; } char u, v; int ui, vi; // 读入 m 条边构建邻接多重表 for(int i 1; i m; i) { getchar(); // 吸收换行符或空格 scanf(%c %c, u, v); // 输入一条边的两个顶点字符 ui find(u); // 找到 u 对应的下标 vi find(v); // 找到 v 对应的下标 ENode* e (ENode*)malloc(sizeof(ENode)); // 创建边节点 // 将边节点 e 插入到顶点 u 的边链表中 e-x_i ui; // 记录边的第一个端点 e-xnext g[ui].first; // 新节点指向原来的第一条边 g[ui].first e; // 头插法更新顶点 u 的第一条边 // 将同一个边节点 e 插入到顶点 v 的边链表中 e-y_i vi; // 记录边的第二个端点 e-ynext g[vi].first; // 新节点指向原来的第一条边 g[vi].first e; // 头插法更新顶点 v 的第一条边 } getchar(); // 吸收换行符 scanf(%c, u); // 输入要查询度数的顶点字符 ui find(u); // 找到该顶点的下标 int d 0; // 度数计数器 ENode* p g[ui].first; // 从该顶点的第一条边开始遍历 // 遍历依附于该顶点的所有边统计度数 while(p ! NULL) { d; // 根据当前边节点中与 ui 相同的端点来决定沿着哪个指针继续 if(p-x_i ui) p p-xnext; // 如果 x_i 是 ui沿 xnext 走 else { p p-ynext; // 否则沿 ynext 走 } } // 输出该顶点的度数 printf(%d\n, d); return 0; } /* 示例输入 4 5 ABCD B A B D D A A C C D A 说明4个顶点5条边顶点依次为A B C D边为(B,A) (B,D) (D,A) (A,C) (C,D) 最后查询顶点 A 的度数。 */