当前位置：首页 → 问答吧 → 帮忙看下，有关图的代码，oj上测试不过

帮忙看下，有关图的代码，oj上测试不过

时间：2011-12-13

来源：互联网

这是有关图的程序，其题目如下：设有一无向图G，采用邻接矩阵存储，现要求设计一个函数，用于求图中度数最大的顶点，并输出其对应的存储编号（下标）。（注：度数最大的顶点可能有多个）
/ B- m3 ]$ N9 b+ L6 j0 R可我在oj上测试不过，不知道问题出在哪里了，下面是我的代码，大家帮忙看下（看//输出度数最大的顶点编号（下标）
/ w& f+ v5 x, y, t& V* M! @void MGraph::MaxDegree() 这部分就行了）：
2 n9 R0 [9 h# |0 U6 m, c) d

复制内容到剪贴板

代码:

#include<iostream>
#include<string>
using namespace std;
const int MaxSize=10;
class MGraph
{
public:
MGraph(string a[],int n,int e); //构造函数，初始化具有n个顶点的图
~MGraph(){}
void Degree(int v); //输出顶点编号（下标）为v的度
void MaxDegree(); //输出度数最大的顶点编号（下标）
private:
string vertex[MaxSize]; //存放图中顶点的数组
int arc[MaxSize][MaxSize]; //存放图中边的数组
int vertexNum,arcNum; //图的顶点数和边数
};

MGraph::MGraph(string a[], int n, int e)
{
vertexNum=n; //顶点数
arcNum=e; //边数
int i,j,k;
for(i=0; i<vertexNum; i++)
vertex=a;
for(i=0; i<vertexNum; i++) //初始化邻接矩阵
for(j=0; j<vertexNum; j++)
arc[j]=0;
for(k=0; k<arcNum; k++) //依次输入每一条边，并修改邻接矩阵的相应元素
{
//cout<<"请输入依附于第"<<k+1<<"条边两顶点的序号：";
cin>>i>>j;
arc[j]=1; //置有边标志
arc[j]=1;
}
}

//输出度数最大的顶点编号（下标）
void MGraph::MaxDegree()
{
int count=0;
int a[MaxSize];
int i=0;
for( i=0;i<vertexNum;i++)
{
for(int j=0;j<vertexNum;j++)
{
if(arc[j]==1)
count++;
}
a=count;
count=0;
}
int max=0;int b=0;
for(int k=0;k<vertexNum;k++)
{
if(max<a[k])
{
max=a[k];
b=k;
}
}
cout<<b<<endl;
int c=0;
for(i=0;i<vertexNum;i++)
{
if(a==max&&i!=b)
{
c=i;
cout<<c<<endl;
}
}
}
void main()
{
int vexnum;
string vex[MaxSize];
//cout<<"请输入顶点数(1~"<<MaxSize<<")：";
cin>>vexnum;
//自动生成各顶点信息，分别为v0、v1、v2......
for(int i=0;i<vexnum;i++)
{
vex="v";
vex+='0'+i;
//cout<<"第"<<i+1<<"个顶点信息为："<<vex<<endl;
}
//cout<<endl<<"请输入边数(0~"<<vexnum*(vexnum-1)/2<<")：";
int edgenum;
cin>>edgenum;
MGraph g(vex,vexnum,edgenum);
g.MaxDegree();
}

6 P% b0 I6 S+ x8 ~, [, b4 o

& X/ @& Z% r/ f7 G6 Z) {[ 本帖最后由洛宇于 2011-12-13 14:45 编辑 ]

作者: 洛宇发布时间: 2011-12-13

又是ACM啊....楼主要是逻辑没错的话，可能要考虑效率问题，毕竟大数据量的情况是有的。

作者: Bill_Hoo 发布时间: 2011-12-13

复制内容到剪贴板

代码:

//输出度数最大的顶点编号（下标）
void MGraph::MaxDegree()
{
int a[MaxSize];
int i=0;
for( i=0;i<vertexNum;i++)
{
int count=0;//在这里初始化
for(int j=0;j<vertexNum;j++)
{
if(arc[j]==1)
count++;
}
a=count;
count=0;
}
int max=0;int b=0;
for(int k=0;k<vertexNum;k++)
{
if(max<a[k])
{
max=a[k];
b=k;
}
}
cout<<b<<endl;
int c=0;
for(i=0;i<vertexNum;i++)
{
if(a==max&&i!=b)
{
c=i;
cout<<c<<endl;
}
}
}

[ 本帖最后由月夜幻影于 2011-12-13 18:41 编辑 ]

作者: 月夜幻影发布时间: 2011-12-13

嗯嗯，不过不用两个for循环不知该怎么查找了，还有这不是ACM的，只是借用了oj平台测试。

作者: 洛宇发布时间: 2011-12-13