本题要求建立一个无向图,采用邻接矩阵做为存储结构。 例如 函数接口定义: void CreatMGraph(MGraph &G);//创建图G int locate(MGraph G,char v);//返回顶点v的下标 G 为图,采用邻接矩阵存储结构,v 是顶点的值。 裁判测试程序样例: #include <stdio.h> #define MVNum 100 //最大顶点数 typedef struct{ char vexs[MVNum]; //存放顶点的一维数组 int arcs[MVNum][MVNum]; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和边数 }MGraph; void CreatMGraph(MGraph &G);/* 创建图 */ void printGraph(MGraph G);/*输出图 */ int locate(MGraph G,char v);//返回顶点v的下标 int main() { MGraph G; CreatMGraph(G);//创建图G printGraph(G);//打印该图 return 0; } void printGraph(MGraph G)//打印图 { int i,j; for(i=0;i<G.vexnum;i++) { printf("%c:",G.vexs[i]); for(j=0;j<G.vexnum;j++) if (G.arcs[i][j]) printf(" %c",G.vexs[j]); printf("\n"); } } /* 请在这里填写答案 */ 输入信息为:第一行给出图的顶点数n和边数e。第二行给出n个字符,表示n个顶点的数据元素的值。后面是e行,给出每一条边的两个顶点的值(顶点之间无空格)。 输出每个顶点的值以及各顶点的邻接点的值。 输入样例: 7 9 0123456 02 03 04 13 15 23 25 45 56 输出样例: 0: 2 3 4 1: 3 5 2: 0 3 5 3: 0 1 2 4: 0 5 5: 1 2 4 6 6: 5 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
时间: 2024-03-31 18:35:45 浏览: 28
题目描述
本题要求建立一个无向图,采用邻接矩阵做为存储结构。
例如 函数接口定义:
void CreatMGraph(MGraph &G);//创建图G
int locate(MGraph G,char v);//返回顶点v的下标
G 为图,采用邻接矩阵存储结构,v 是顶点的值。
裁判测试程序样例:
#include <stdio.h>
#define MVNum 100 //最大顶点数
typedef struct{
char vexs[MVNum]; //存放顶点的一维数组
int arcs[MVNum][MVNum]; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和边数
}MGraph;
void CreatMGraph(MGraph &G);/* 创建图 */
void printGraph(MGraph G);/*输出图 */
int locate(MGraph G,char v);//返回顶点v的下标
int main() {
MGraph G;
CreatMGraph(G);//创建图G
printGraph(G);//打印该图
return 0;
}
void printGraph(MGraph G)//打印图
{
int i,j;
for(i=0;i<G.vexnum;i++)
{
printf("%c:",G.vexs[i]);
for(j=0;j<G.vexnum;j++)
if (G.arcs[i][j]) printf(" %c",G.vexs[j]);
printf("\n");
}
}
/* 请在这里填写答案 */
输入信息为:第一行给出图的顶点数n和边数e。第二行给出n个字符,表示n个顶点的数据元素的值。后面是e行,给出每一条边的两个顶点的值(顶点之间无空格)。
输出每个顶点的值以及各顶点的邻接点的值。
输入样例:
7 9
0123456
02
03
04
13
15
23
25
45
56
输出样例:
0: 2 3 4
1: 3 5
2: 0 3 5
3: 0 1 2
4: 0 5
5: 1 2 4 6
6: 5
算法1
(邻接矩阵) $O(E)$
建立无向图,采用邻接矩阵存储结构。
时间复杂度
参考文献
python3 代码
C++ 代码
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码