Responsive image

问题 F: 第6关:基于邻接表的顶点的删除

问题 F: 第6关:基于邻接表的顶点的删除

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 16
[提交][状态][讨论版][命题人:]

题目描述

给定一个无向图,在此无向图中删除一个顶点。
#include<iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MVNum 100     //最大顶点数
using namespace std;
typedef struct ArcNode
{//边结点
int adjvex;                //邻接点域:该边所指向的顶点的位置
int data;                  //数据域:存储和边相关的信息
struct ArcNode* nextarc;   //链域:指向下一条边的指针
}ArcNode;
typedef struct VNode
{//顶点信息
int data;              //顶点结点的数据域
ArcNode* firstarc;     //链域:指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum];     //AdjList表示邻接表类型
typedef struct
{//邻接表
AdjList vertices;
int vexnum,arcnum;    //图的当前顶点数和边数
}ALGragh;
int CreateUDG(ALGragh &G,int vexnum,int arcnum)
{//采用邻接表表示法,创建无向图G
G.vexnum=vexnum;     //输入总顶点数
G.arcnum=arcnum;     //输入总边数
if(G.vexnum>MVNum) return ERROR;  //超出最大顶点数则结束函数
  for(int i=0;i<G.vexnum;++i)       //构造表头结点表
    {
        G.vertices[i].data=i+1;       //输入顶点值
        G.vertices[i].firstarc=NULL;   //初始化表头结点的指针域为NULL
    }
  for(int j=0;j<G.arcnum;j++)      //输入各边,构造邻接表
    {
        int h,k;
cin>>h>>k;                  //输入一条边依附的两个顶点h和k
ArcNode* p1=new ArcNode;        //生成一个新的边结点*p1
p1->adjvex=h-1;                 //邻接点序号为h-1,即顶点在G.vertices中的序号
p1->data=k;
p1->nextarc=G.vertices[h-1].firstarc;   //将新结点*p1插入顶点vh-1的边表头部
G.vertices[h-1].firstarc=p1;
        ArcNode* p2=new ArcNode;         //生成一个新的边结点*p2
        p2->adjvex=k-1;                  //邻接点序号为k-1,即顶点在G.vertices中的序号
        p2->data=h;
        p2->nextarc=G.vertices[k-1].firstarc;     //将新结点*p2插入顶点vk-1的边表头部
        G.vertices[k-1].firstarc=p2;
    }
  return OK;
}
void DeleteAdjList(VNode &List)
{//删除指定顶点链表上的边结点
    ArcNode *p=List.firstarc;           //结点p用于指代当前结点的前驱,初始化指顶点链表上的第一个边结点
    ArcNode *q=List.firstarc->nextarc;  //结点q用于指代当前结点;
    while (q){
        delete p;
        p=q;
        q=q->nextarc;
    }  
}
int DeleteVex(ALGragh &G)
{//删除G中顶点f及其相关的弧
/**************begin************/










    /**************end************/
}
int PrintGraph(ALGragh G)
{//输出图G
  for(int i=0;i<G.vexnum;i++)
    {
cout<<G.vertices[i].data;        //先输出顶点信息
ArcNode* p=G.vertices[i].firstarc;     //初始化指针p指向与顶点邻接的第一个边结点
if(p==NULL)               //不存在与顶点邻接的第一个边结点
        {
            cout<<endl;
            continue;
        }
        else                    //存在时遍历边表
        {
            cout<<" ";
            while(p->nextarc)
            {
cout<<p->data<<" ";
p=p->nextarc;
}
cout<<p->data<<endl;
        }
    }
    return OK;
}
int main()
{
int n,m;
while(cin>>n>>m)
{
      if(n==0&&m==0) break;     //输入结束标志
      ALGragh G;
        CreateUDG(G,n,m);      //采用邻接表表示法,创建无向图G
      DeleteVex(G);        //删除G中顶点f及其相关的弧
    PrintGraph(G);      //输出图G
}
return 0;
}

输入描述

多组数据,每组m+2行。第一行有两个数字n和m,代表有n个顶点和m条边。顶点编号为1到n。第二行到第m+1行每行有两个数字h和k,代表边依附的两个顶点。第m+2行有一个数字f,代表删除的顶点编号。当n和m都等于0时,输入结束。

输出描述

每组数据输出n-1行。为删除顶点后的邻接表。每两个数字之间用空格隔开。

样例输入

3 2
1 2
2 3
1
2 1
1 2
2
0 0

样例输出

2 3
3 2
1

提示


组合提交代码,你需要提交



int DeleteVex(ALGragh &G)

{//删除G中顶点f及其相关的弧

/**************begin************/





















    /**************end************/

}





[提交][状态]
ACM算法攻关部