假设用邻接矩阵存储无向图,设计算法,求出度数最大的顶点编号 急急急紧急急急急急急急急急急急急急急急急急急急急急急
5条回答 默认 最新
- frank_20080215 2015-07-10 14:32关注
首先以一个结构体存储一个图:
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;
}解决 无用评论 打赏 举报
悬赏问题
- ¥15 关于#python#的问题:求帮写python代码
- ¥20 MATLAB画图图形出现上下震荡的线条
- ¥15 LiBeAs的带隙等于0.997eV,计算阴离子的N和P
- ¥15 关于#windows#的问题:怎么用WIN 11系统的电脑 克隆WIN NT3.51-4.0系统的硬盘
- ¥15 来真人,不要ai!matlab有关常微分方程的问题求解决,
- ¥15 perl MISA分析p3_in脚本出错
- ¥15 k8s部署jupyterlab,jupyterlab保存不了文件
- ¥15 ubuntu虚拟机打包apk错误
- ¥199 rust编程架构设计的方案 有偿
- ¥15 回答4f系统的像差计算