关于数据结构的简单问题完整算法 C语言 假设用邻接矩阵存储无向图，设计算法，求出度数最大的顶点编号

假设用邻接矩阵存储无向图，设计算法，求出度数最大的顶点编号 急急急紧急急急急急急急急急急急急急急急急急急急急急急

首先以一个结构体存储一个图：

struct MGraph
{
int vertex[maxvertex]; //存顶点
int arc[maxvertex][maxvertex]; //存边（邻接矩阵）
int vertexnum,arcnum; //顶点数和边数
};

其次是对图的初始化：

void CreatMGraph(MGraph *&G)
{
int i,j;
cin1>>G->vertexnum>>G->arcnum; //输入顶点数和边数

for(i=0;ivertexnum;i++) //输入每个顶点的值
cin1>>G->vertex[i];

for(i=0;ivertexnum;i++) //初始化邻接矩阵
for(j=0;jvertexnum;j++)
G->arc[i][j]=0;

for(i=0;iarcnum;i++)

{
int n,m,w;
cin1>>n>>m>>w; //修改邻接矩阵中的值
G->arc[n][m]=w;
G->arc[m][n]=w;
}
}

在此之前需要定义一个全局变量的visited数组：

int visited[maxvertex]; //标记已被访问过的顶点(全局变量)

//广度优先遍历

void BFS(MGraph *&G,int v)

{
queue q;
int x,j;
if(!visited[v]) //即为visited[v]==0，也就是未被访问过
{
cout<vertex[v]<<" ";
visited[v]=1;
q.push(v); //被访问的顶点入队
}

while(!q.empty()) //队不空进循环
{
x=q.front(); //取队头元素
q.pop(); //队头出队
for(j=0;jvertexnum;j++)
if (G->arc[x][j]&&!visited[j])
{
cout<vertex[j]<<" ";
visited[j]=1; //标记为访问过
q.push(j); //被访问的顶点继续入队
}
}
}

//深度优先遍历
void DFS(MGraph *&G,int v)

{
nt j;
if(!visited[v])

{
cout<vertex[v]<<" ";
visited[v]=1; //标记为访问过
}

for(j=0;jvertexnum;j++)
if (G->arc[v][j]&&!visited[j])//邻接矩阵的第(v,j)元素不为0
{ //且未被访问过则递归
DFS(G,j);
}
}

此为图的邻接矩阵的输出函数：

void Print(MGraph *G)
{
int i,j;
for(i=0;ivertexnum;i++)
{
for(j=0;jvertexnum;j++)
cout<arc[i][j]<<" ";
cout<<endl;
}
}

main函数调用上面函数：

int main()
{
MGraph *G=new MGraph;
CreatMGraph(G);

cout<<"输出邻接矩阵:"<<endl;
Print(G);

cout<<"深度优先搜索:";
DFS(G,0);
cout<<endl;

memset(visited,0,sizeof(visited));//非常重要！！在下一个搜索之前一定要将标志位全部重新赋值为0

cout<<"广度优先搜索:";
BFS(G,0);
cout<<endl;

return 0;
}

先是存储结构后是伪代码，你想要算法就看注释吧~

Typedef struct Node
{
Char vex; //顶点
Int degree; //度数
}Node;
Node ArrDegree[m]; //m+1为顶点个数

For(i =0; i ArrDegree[i].degree = 0;
For(i=0; i {
For(j=0; j {
If(Metrix[i][j] == 1)
{
ArrDegree[i].degree++;
ArrDegree[j].degree++;
}
}
}
Max = 0; //min为最大度数
Number = -1；//number为最大度数顶点的编号
For(i = 0; i {
If(ArrDegree[i].degree > Max)
{
Max = ArrDegree[m];
Number = i;
}
}
Return i;

参考：http://www.docin.com/p-428957290.html

这道题高能，，一楼写的是对的，但是不能直接运行，http://blog.csdn.net/csu54zzg/article/details/38829437
这个是java版本的应该可以直接运行