图

图

图删除顶点应该用的思想是：用图（g）最后一个顶点（maxVertex）去覆盖要删除的顶点（vindex）。

1.图的结构如下：

#include<stdio.h>
#include<malloc.h>
//顶点的邻接顶点组成的链表的结点的结构
typedef struct edge
{int destIndex; //邻接顶点的下标struct edge *next;
}Edge;
//顶点的结构
typedef struct vertex
{char VertexValue; //顶点本身的值Edge *list; //指向当前顶点的邻接顶点组成的链表的指针
}Vertex;
//图结构
typedef struct graph
{Vertex *VertexArr; //顶点的一维数组int MaxVertex;    //最大的顶点个数int NumVertex;    //实际的顶点个数int NumEdge;     //边的条数
}Graph;

2.具体做法：

1）先删除顶点中有关的边（如果是无向图需要删除顶点v1-v2,v2-v1）。

2）先覆盖要删除顶点，包括覆盖值以及指针。

3）遍历最后一个顶点的边链表，找出要修改下标的顶点。

4）在要修改下标的顶点中找到最大顶点的值，将其修改为要删除顶点的下标。

删除边：

int GetVertexIndex(Graph *g,char vertex)
{int i;for(i = 0;i<g->NumVertex;i++){if(g->VertexArr[i].VertexValue == vertex)return i;}return -1;
}
void DelEdge(Graph *g,char v1,char v2)
{//先获得顶点的下标int p1 = GetVertexIndex(g,v1);int p2 = GetVertexIndex(g,v2);if(p1 == -1 || p2 == -1)return;/*先删除v1-v2的边，即是在v1的边链表中查找v2的下标的那个结点，并删除*/Edge *p = NULL,*pf = NULL; //p循环查找，pf指向要删除的前一个结点p = g->VertexArr[p1].list; //p指向v1的边链表//在边链表中查找p2while(p != NULL && p->destIndex != p2){pf = p;p = p->next;}if(p == NULL) //找到末尾还没找到，说明没边return;//找到了，分为两种情况，要么删除的是头，要么是中间或者末尾if(pf == NULL) //p == g->VertexArr[p1].list{g->VertexArr[p1].list = p->next;}else{pf->next = p->next;}free(p);//无向图，还需要删除v2-v1pf = NULL;p = g->VertexArr[p2].list;while(p->destIndex != p1){pf = p;p = p->next;}if(pf == NULL){g->VertexArr[p2].list = p->next;}else{pf->next = p->next;}free(p);p = NULL;g->NumEdge--;
}

删除顶点的完整代码：

void DelVertex(Graph *g,char vertex)
{int vindex = GetVertexIndex(g,vertex);if(vindex == -1)return;Edge *p = NULL;char destVertex; //和顶点vertex相关联的顶点//p指针指向顶点vertex的边链表p = g->VertexArr[vindex].list; //先删除和顶点vertex相关联的所有的边//循环边链表，删除边while(p != NULL){destVertex = g->VertexArr[p->destIndex].VertexValue; //相关联的顶点//删除vertex-destVertex的边DelEdge(g,vertex,destVertex);p = g->VertexArr[vindex].list; //p重新指向删除关联的边后的边链表}/*删除顶点，在数组中，如果像以前删除数组中元素的方法(要删除的元素后面的前移),需要修改和移动的太多，改动比较大，比较麻烦采取覆盖的方式--用数组中最后一个顶点的所有去覆盖要删除的顶点的所有，然后修改和最后一个相关联的顶点的值为现在的下标*/g->NumVertex--;//覆盖g->VertexArr[vindex].VertexValue = g->VertexArr[g->NumVertex].VertexValue;g->VertexArr[vindex].list = g->VertexArr[g->NumVertex].list;//修改Edge *q = NULL; //相关联的顶点的边链表p = g->VertexArr[vindex].list;while(p != NULL) //循环当前边链表，依次修改{int k = p->destIndex;q = g->VertexArr[k].list;while(q){if(q->destIndex == g->NumVertex){q->destIndex = vindex;break;}q = q->next;}p = p->next;}
}