求割点（邻接表无向图）C~
本文共 4271 字，大约阅读时间需要 14 分钟。
上一篇 ：
邻接表 ： O(N+M)
邻接矩阵 : O(N^2)
核心代码 ：
void dfs(int cur, int father, Graph g, Info* info) { info->index++; info->num[cur] = info->index; info->low[cur] = info->index; info->child = 0;//记录每个顶点孩子数量 ENode *node; node = g.vex[cur].first_edge; while(node != NULL){ //访问 每个 临接点 if(info->num[node->ivex] == 0){//当前顶点未访问 info->child++;//当前顶点孩子数加1 dfs(node->ivex, cur, g, info);// info->low[cur] = min(info->low[cur], info->low[node->ivex]); if(info->root != cur && info->low[node->ivex] >= info->num[cur] ) { info->flag[cur] = 1; info->cnt++; } if(info->root == cur && info->child == 2) { info->flag[cur] = 1; info->cnt++; } } else if(node->ivex != father){ info->low[cur] = min(info->low[cur], info->num[node->ivex]); } node = node->next_edge; } return ; } 完整实现 ：
#include#include #include #define MAXVEX 100 typedef char VertexType; typedef int WeightType; typedef struct ENode { int ivex;//顶点 索引 WeightType weight; struct ENode* next_edge; }ENode; typedef struct Info{// 记录 int index; int root; int child; int num[MAXVEX];//当前顶点的时间戳 int low[MAXVEX];//能访问到的最早顶点的时间戳 int flag[MAXVEX]; int cnt;}Info; typedef struct VNode { VertexType data; // 顶点 信息 ENode* first_edge; }VNode; typedef struct Graph { VNode vex[MAXVEX]; int vex_num, edge_num; }Graph; int index;char read_char() { char ch; do { ch = getchar(); } while (!isalpha(ch)); return ch; } int get_pos(Graph g, char ch) { int i; for (i = 0; i < g.vex_num; i++) { if (ch == g.vex[i].data) return i; } return -1; } void link_last(ENode* list, ENode *last) { ENode* p; p = list; while (p->next_edge != NULL) { p = p->next_edge; } p->next_edge = last; } void create_graph(Graph *g) { int i, w; printf("请输入顶点数和边数:\n"); scanf("%d%d", &g->vex_num, &g->edge_num); printf("请输入顶点信息:\n"); for (i = 0; i < g->vex_num; i++) { g->vex[i].first_edge = NULL; g->vex[i].data = read_char(); } printf("请输入边 :\n"); for (i = 0; i < g->edge_num; i++) { int p1, p2; char c1, c2; c1 = read_char(); c2 = read_char(); // scanf("%d", &w); p1 = get_pos(*g, c1); p2 = get_pos(*g, c2); ENode* node1, *node2; node1 = (ENode*)malloc(sizeof(ENode)); if (node1 == NULL) { printf("error"); return; } node1->next_edge = NULL; node1->ivex = p2; if (g->vex[p1].first_edge == NULL) g->vex[p1].first_edge = node1; else link_last(g->vex[p1].first_edge, node1); node2 = (ENode *)malloc(sizeof(ENode)); node2->next_edge = NULL; node2->ivex = p1; if(g->vex[p2].first_edge == NULL) g->vex[p2].first_edge = node2; else link_last(g->vex[p2].first_edge, node2); } } int min(int a, int b) { return a < b ? a : b; }// 求割点核心 void dfs(int cur, int father, Graph g, Info* info) { info->index++; info->num[cur] = info->index; info->low[cur] = info->index; info->child = 0;//记录每个顶点孩子数量 ENode *node; node = g.vex[cur].first_edge; while(node != NULL){ //访问 每个 临接点 if(info->num[node->ivex] == 0){ info->child++; dfs(node->ivex, cur, g, info); info->low[cur] = min(info->low[cur], info->low[node->ivex]); if(info->root != cur && info->low[node->ivex] >= info->num[cur] ) { info->flag[cur] = 1; info->cnt++; } if(info->root == cur && info->child == 2) { info->flag[cur] = 1; info->cnt++; } } else if(node->ivex != father){ info->low[cur] = min(info->low[cur], info->num[node->ivex]); } node = node->next_edge; } return ; } int main() { Graph g; create_graph(&g); Info info; info.index = 0; info.root = 0; int i; for(int i = 0; i < g.vex_num; i++ ){ info.num[i] = 0;// 这个必须初始化 为 0 表示未访问 info.cnt = 0; } dfs(0, 0, g, &info); if(info.cnt == 0){ printf("\n该图不存在割点"); return 0; } printf("\n此图有%d个割点 : ",info.cnt); for(i = 0; i < g.vex_num; i++ ){ if(info.flag[i] == 1) printf("%c ", g.vex[i].data); } return 0; }
你可能感兴趣的文章
Vim学习笔记——帮助
查看>>
Python学习笔记——网络通信过程
查看>>
Python学习笔记——正则表达式
查看>>
Python学习笔记——数据结构与算法
查看>>
Python学习笔记——顺序表
查看>>
Python学习笔记——链表
查看>>
MarkDown学习笔记——语法
查看>>
Python学习笔记——栈和队列
查看>>
Python学习笔记——排序与搜索
查看>>
Python学习笔记——爬虫之BeautifulSoup4数据提取
查看>>
Python学习笔记——爬虫的思路总结
查看>>
Python学习笔记——爬虫之动态HTML处理和机器图像识别
查看>>
Python学习笔记——爬虫之执行JavaScript语句与训练Tesseract
查看>>
Python学习笔记——爬虫之Scrapy框架
查看>>
Python学习笔记——爬虫之Scrapy项目实战
查看>>
Python学习笔记——爬虫之通过Fiddler进行手机抓包
查看>>
Python学习笔记——爬虫之Scrapy-Redis分布式组件
查看>>
Python学习笔记——爬虫之Scrapy-Redis实战
查看>>
Python学习笔记——大数据之Spark简介与环境搭建
查看>>
Python学习笔记——大数据之SPARK核心
查看>>