首页 > 代码库 > 一步一步写算法(之图添加和删除)

一步一步写算法(之图添加和删除)

原文: 一步一步写算法(之图添加和删除)

【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱:feixiaoxing @163.com】


    前面我们谈到的图的数据结构、图的创建,今天我们就来说一说如何在图中添加和删除边。边的添加和删除并不复杂,但是关键有一点需要记住,那就是一定要在小函数的基础之上构建大函数,否则很容易出现错误。


    一、边的创建

    边的创建一般来说可以分为下面以下几个步骤:

    1)判断当前图中是否有节点,如果没有,那么在pGraph->head处添加一条边即可

    2)如果当前图中有节点,那么判断节点中有没有以start点开头的,如果没有创建一个顶点和边,并插入图的head处

    3)在当前有节点start中,判断是否end的边已经存在。如果end边存在,返回出错;否则在pVectex->neighbour处添加一条边

    4)添加的过程中注意点的个数和边的个数处理

STATUS insert_vectex_into_graph(GRAPH* pGraph, int start, int end, int weight){	VECTEX* pVectex;	LINE* pLine;	if(NULL == pGraph)		return FALSE;	if(NULL == pGraph->head){		pGraph->head = create_new_vectex_for_graph(start, end, weight);		pGraph->head->number ++;		pGraph->count ++;		return TRUE;	}	pVectex = find_vectex_in_graph(pGraph->head, start);	if(NULL == pVectex){		pVectex = create_new_vectex_for_graph(start, end, weight);		pVectex->next = pGraph->head;		pGraph->head = pVectex;		pGraph->head->number ++;		pGraph->count ++;		return TRUE;	}	pLine = find_line_in_graph(pVectex->neighbor, end);	if(NULL != pLine)		return FALSE;	pLine = create_new_line(end, weight);	pLine->next = pVectex->neighbor;	pVectex->neighbor = pLine;	pVectex->number ++;	return TRUE;}

    二、边的删除

    在进行边的删除之前,我们需要对链表子节点进行处理,构建delete小函数,这样可以在边删除函数中使用。

STATUS delete_old_vectex(VECTEX** ppVectex, int start){	VECTEX* pVectex;	VECTEX* prev;	if(NULL == ppVectex || NULL == *ppVectex)		return FALSE;		pVectex = find_vectex_in_graph(*ppVectex, start);	if(NULL == pVectex)		return FALSE;	if(pVectex == *ppVectex){		*ppVectex = pVectex->next;		free(pVectex);		return TRUE;	}		prev = *ppVectex;	while(pVectex != prev->next)		prev = prev->next;	prev->next = pVectex->next;	free(pVectex);	return TRUE;}STATUS delete_old_line(LINE** ppLine, int end){	LINE* pLine;	LINE* prev;	if(NULL == ppLine || NULL == *ppLine)		return FALSE;	pLine = find_line_in_graph(*ppLine, end);	if(NULL == pLine)		return FALSE;		if(pLine == *ppLine){		*ppLine = pLine->next;		free(pLine);		return TRUE;	}		prev = *ppLine;	while(pLine != prev->next)		prev = prev->next;		prev->next = pLine->next;	free(pLine);	return TRUE;}

    

一般来说,边的删除和边的添加是可逆的,过程如下所示:

    1)判断图中是否有节点存在,如果没有,返回出错

    2)判断图中节点start是否存在,如果不存在,返回出错

    3)判断节点start中是否end边存在,如果不存在,返回出错

    4)删除对应的边

    5)判断该节点的边计数number是否为0,如果为0,继续删除节点

    6)删除过程中注意边和顶点的个数处理

STATUS delete_vectex_from_graph(GRAPH* pGraph, int start, int end, int weight){	VECTEX* pVectex;	LINE* pLine;	STATUS result;	if(NULL == pGraph || NULL == pGraph->head)		return FALSE;	pVectex = find_vectex_in_graph(pGraph->head, start);	if(NULL == pVectex)		return FALSE;	pLine = find_line_in_graph(pVectex->neighbor, end);	if(NULL != pLine)		return FALSE;	result = delete_old_line(&pVectex->neighbor, end);	assert(TRUE == result);	pVectex->number --;	if(0 == pVectex->number)		result = delete_old_vectex(&pGraph->head, start);	assert(TRUE == result);	pGraph->count --;	return TRUE;}

注意事项:

    (1)注意写小函数,再复杂的功能都是有无数的小功能构建的,函数最好不要超过50行

    (2)老规矩,代码务必要测试

一步一步写算法(之图添加和删除)