求割点（邻接表无向图）C~

上一篇 ： 图割点（邻接矩阵）

邻接表 ： 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<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#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;	
	}