购物网站开发将商品导入数据库,wordpress图片弹出,免费seo关键词优化排名,企业网站建设湖南岚鸿hnust 1963: 邻接矩阵表示法
题目描述 输入一个图#xff0c;用邻接矩阵存储#xff0c;并实现一些操作。 拷贝下面的代码#xff0c;按要求完成其中的FirstAdjVex#xff0c;NextAdjVex和CreateUDG操作#xff0c;其他地方不得改动。
//邻接矩阵表示图
#include io…hnust 1963: 邻接矩阵表示法
题目描述 输入一个图用邻接矩阵存储并实现一些操作。 拷贝下面的代码按要求完成其中的FirstAdjVexNextAdjVex和CreateUDG操作其他地方不得改动。
//邻接矩阵表示图
#include iostream
#include iomanip
#include cstdio
using namespace std;#define MVNum 100 //最大顶点数
typedef string VerTexType; //假设顶点的数据类型为字符串
typedef int ArcType; //假设边的权值类型为整型//------------图的邻接矩阵------------------
typedef struct {VerTexType vexs[MVNum]; //顶点表ArcType arcs[MVNum][MVNum]; //邻接矩阵int vexnum, arcnum; //图的当前点数和边数
} Graph;//得到顶点i的数据
VerTexType Vertexdata(const Graph g, int i)
{return g.vexs[i];
}int LocateVex(const Graph g, VerTexType v)
{//确定点v在G中的位置for(int i 0; i g.vexnum; i)if(g.vexs[i] v)return i;return -1;
}//LocateVexint FirstAdjVex(const Graph g, int v)
{//返回v的第一个邻接点编号没有返回-1/****在此下面完成代码***************//***********************************/
}//FirstAdjVexint NextAdjVex(const Graph g, int v, int w)
{//返回v相对于w的下一个邻接点没有返回-1/****在此下面完成代码***************//***********************************/
}//NextAdjVexvoid CreateUDG(Graph g)
{//采用邻接矩阵表示法创建无向图G/****在此下面完成代码***************//***********************************/
}//CreateUDNvoid DestroyUDG(Graph g)
{//you should do this
}//输出邻接矩阵
void PrintUDG(const Graph g)
{int i, j;cout ;for(i 0; i g.vexnum; i) {cout setw(4) g.vexs[i] ;}cout endl;for(i 0; i g.vexnum; i) {cout setw(4) g.vexs[i];for(j 0; j g.vexnum; j) {cout setw(4) g.arcs[i][j];}cout endl;}
}int main()
{Graph g;CreateUDG(g);//输出各个顶点的邻接点for(int i 0; i g.vexnum; i) {cout Vertexdata(g, i) :;for(int w FirstAdjVex(g, i); w 0; w NextAdjVex(g, i, w)) {cout Vertexdata(g, w);}cout endl;}PrintUDG(g);DestroyUDG(g);return 0;
}//main输入 输入的第一行是两个整数分别是图的总顶点数n和总边数e
第二行是n个空格分开的字符串是顶点的名字依次对应编号0~n-1。
随后有e行每行两个空格分开的顶点名字表示一条边的两个顶点。
具体见样例。
输出 首先输出n行每行是第i个顶点的邻接顶点。
再输出该图的邻接矩阵。
具体见样例。
样例输入 Copy
8 9
v1 v2 v3 v4 v5 v6 v7 v8
v1 v2
v1 v3
v2 v4
v2 v5
v3 v6
v3 v7
v4 v8
v5 v8
v6 v7
样例输出 Copy
v1: v2 v3
v2: v1 v4 v5
v3: v1 v6 v7
v4: v2 v8
v5: v2 v8
v6: v3 v7
v7: v3 v6
v8: v4 v5v1 v2 v3 v4 v5 v6 v7 v8v1 0 1 1 0 0 0 0 0v2 1 0 0 1 1 0 0 0v3 1 0 0 0 0 1 1 0v4 0 1 0 0 0 0 0 1v5 0 1 0 0 0 0 0 1v6 0 0 1 0 0 0 1 0v7 0 0 1 0 0 1 0 0v8 0 0 0 1 1 0 0 0提示 样例对应教材6.5的图G4
解题过程
数组(邻接矩阵)表示法 定义 图没有顺序存储结构但可以借助二维数组来表示元素间的关系
在无向图的邻接矩阵中它的特点 无向图的邻接矩阵是对称的 顶点 i 的度 第 i 行/列 中 1 的个数
有向图的邻接矩阵 第 i 行含义以节点 Vi 为尾的弧(即出度边) 第 i 列含义以节点 Vi 为头的弧(即入度边)
在有向图的邻接矩阵中它的特点 有向图的邻接矩阵可能是不对称的 顶点的出度 第 i 行元素之和 顶点的入度 第 i 列元素之和 顶点的度 第 i 行元素之和 第 i 列元素之和 网(即有权图)的邻接矩阵表示法 定义为A.arcs[i][j] Wij 存在从 i 顶点到 j 顶点的弧或者边的权否则 A.arcs[i][j] 无穷大
邻接矩阵的优缺点 优点 直观、简单、好理解 方便检查任意一对顶点间是否存在边 方便找任一顶点的所有邻接点(右边直接相连的顶点) 方便计算任一顶点的度(从该点发出的边数为出度指向该点的边数为入度) 无向图对应行(或列)非0元素的个数 有向图对应行非0元素的个数是出度对应列非0元素的个数是入度
缺点 不便于增加和删除顶点 浪费空间-存稀疏图(点很多而边很少)有大量无效元素 对稠密图(特别是完全图)还是很合算的 浪费时间-统计稀疏图中一共有多少条边
这段C代码实现了无向图的创建、遍历和销毁使用了邻接矩阵来表示图。下面是对代码的详细解析
1. 头文件和命名空间
包含bits/stdc.h提供标准库支持。使用using namespace std;简化代码。
2. 宏定义和类型定义
MVNum定义了最大顶点数。VerTexType和ArcType分别定义了顶点和边的数据类型。
3. 图结构定义
Graph结构体定义了图的邻接矩阵表示包含顶点数组、邻接矩阵以及顶点数和边数。
4. 函数定义
LocateVex查找顶点在图中的位置如果找到则返回索引否则返回-1。FirstAdjVex返回顶点的第一个邻接点的索引如果没有邻接点则返回-1。NextAdjVex返回顶点相对于给定邻接点的下一个邻接点的索引如果没有则返回-1。
5. 图的创建函数CreateUDG
读取顶点数和边数。读取顶点信息并存储到顶点数组中。循环读取边的信息使用LocateVex找到顶点的索引并在邻接矩阵中相应位置设置边的信息。
6. 图的销毁函数DestroyUDG
使用memset将邻接矩阵的所有元素设置为0销毁图。
7. 图的输出函数PrintUDG
输出图的邻接矩阵格式化输出顶点和对应的邻接点。
8. 主函数main
创建图g并调用CreateUDG函数。遍历所有顶点输出每个顶点及其邻接点。调用PrintUDG函数输出整个图的邻接矩阵。调用DestroyUDG函数销毁图。
代码逻辑分析
代码首先定义了图的数据结构和相关操作函数。使用CreateUDG函数根据用户输入创建图。使用FirstAdjVex和NextAdjVex函数遍历每个顶点的邻接点。使用PrintUDG函数输出图的邻接矩阵以便于观察。最后使用DestroyUDG函数清理图占用的资源。
潜在问题
CreateUDG函数中如果输入的边信息中顶点不在顶点数组中程序将不会报错但这些顶点不会在图中表示。DestroyUDG函数中只销毁了邻接矩阵的数据没有销毁顶点数组。
改进建议
在CreateUDG函数中添加对输入边的顶点是否存在的检查。考虑动态分配顶点数组和邻接矩阵的内存并在DestroyUDG函数中释放这些内存。考虑添加更多图操作的函数如搜索、路径查找等。考虑使用std::vector来代替固定大小的数组以提高代码的灵活性和安全性。
部分代码
typedef struct
{VerTexType vexs[MVNum]; //顶点表,用以存储顶点ArcType arcs[MVNum][MVNum]; //邻接矩阵int vexnum, arcnum; //图的当前点数和边数
} Graph;
int LocateVex(const Graph g, VerTexType v)
{//确定点v在G中顶点表的位置for(int i 0; i g.vexnum; i)if(g.vexs[i] v)return i;return -1;
}//LocateVexint FirstAdjVex(const Graph g, int v)
{//返回顶点v的第一个邻接点编号没有返回-1/****在此下面完成代码***************/for(int i0; ig.vexnum; i)if(g.arcs[v][i])return i;return -1;/***********************************/
}//FirstAdjVex
int NextAdjVex(const Graph g, int v, int w)
{//返回顶点v相对于w的下一个邻接点没有返回-1/****在此下面完成代码***************/for(int iw1; ig.vexnum; i)if(g.arcs[v][i])return i;return -1;/***********************************/
}//NextAdjVexvoid CreateUDG(Graph g)
{//采用邻接矩阵表示法创建无向图G/****在此下面完成代码***************/cing.vexnumg.arcnum;for(int i0; ig.vexnum; i)cing.vexs[i];while(g.arcnum--){string x1,x2;cinx1x2;int mLocateVex(g,x1),nLocateVex(g,x2);if(m!-1n!-1)g.arcs[m][n]g.arcs[n][m]1;}/***********************************/
}//CreateUDNvoid DestroyUDG(Graph g)
{memset(g.arcs,0,sizeof(g.arcs));
}
//输出邻接矩阵
void PrintUDG(const Graph g)
{int i, j;cout ;for(i 0; i g.vexnum; i){cout setw(4) g.vexs[i] ;}cout endl;for(i 0; i g.vexnum; i){cout setw(4) g.vexs[i];for(j 0; j g.vexnum; j){cout setw(4) g.arcs[i][j];}cout endl;}
}AC代码
#includebits/stdc.h
using namespace std;#define MVNum 100 //最大顶点数
typedef string VerTexType; //假设顶点的数据类型为字符串
typedef int ArcType; //假设边的权值类型为整型//------------图的邻接矩阵------------------
typedef struct
{VerTexType vexs[MVNum]; //顶点表,用以存储顶点ArcType arcs[MVNum][MVNum]; //邻接矩阵int vexnum, arcnum; //图的当前点数和边数
} Graph;
int LocateVex(const Graph g, VerTexType v)
{//确定点v在G中顶点表的位置for(int i 0; i g.vexnum; i)if(g.vexs[i] v)return i;return -1;
}//LocateVexint FirstAdjVex(const Graph g, int v)
{//返回顶点v的第一个邻接点编号没有返回-1/****在此下面完成代码***************/for(int i0; ig.vexnum; i)if(g.arcs[v][i])return i;return -1;/***********************************/
}//FirstAdjVexint NextAdjVex(const Graph g, int v, int w)
{//返回顶点v相对于w的下一个邻接点没有返回-1/****在此下面完成代码***************/for(int iw1; ig.vexnum; i)if(g.arcs[v][i])return i;return -1;/***********************************/
}//NextAdjVexvoid CreateUDG(Graph g)
{//采用邻接矩阵表示法创建无向图G/****在此下面完成代码***************/cing.vexnumg.arcnum;for(int i0; ig.vexnum; i)cing.vexs[i];while(g.arcnum--){string x1,x2;cinx1x2;int mLocateVex(g,x1),nLocateVex(g,x2);if(m!-1n!-1)g.arcs[m][n]g.arcs[n][m]1;}/***********************************/
}//CreateUDNvoid DestroyUDG(Graph g)
{memset(g.arcs,0,sizeof(g.arcs));
}//输出邻接矩阵
void PrintUDG(const Graph g)
{int i, j;cout ;for(i 0; i g.vexnum; i){cout setw(4) g.vexs[i] ;}cout endl;for(i 0; i g.vexnum; i){cout setw(4) g.vexs[i];for(j 0; j g.vexnum; j){cout setw(4) g.arcs[i][j];}cout endl;}
}int main()
{Graph g;CreateUDG(g);//输出各个顶点的邻接点for(int i 0; i g.vexnum; i){cout g.vexs[i] :;for(int w FirstAdjVex(g, i); w 0; w NextAdjVex(g, i, w)){cout g.vexs[w];}cout endl;}PrintUDG(g);DestroyUDG(g);return 0;
}
