• 数据结构-----图(graph)的储存和创建


    目录

    前言

    图的储存结构

    1.邻接矩阵

    无向图的邻接矩阵

     有向图的邻接矩阵

    网(赋权图)的邻接矩阵

     代码表示

    2.邻接表

    无向图的邻接表

    有向图的邻接表

    代码表示

    3.邻接矩阵和邻接表对比

    邻接矩阵

    邻接表

    图的创建

    1.邻接矩阵创建图(网)

     2.邻接表创建图(网)


    前言

            上一期我们学习了图的基础知识(链接:数据结构-----图(Graph)论必知必会知识-CSDN博客),这一期我们就学习怎么去储存图,和创建一个图,下面就一起来看看。

    图的储存结构

    1.邻接矩阵

    邻接矩阵是图的矩阵表示,借助它可以方便地存储图的结构,用线性代数的方法研究图的问题。 如果一个图有 n 个顶点,其邻接矩阵 W 为 ntimes n 的矩阵,矩阵元素 w_ {ij} 表示边 (i,j) 的权重。 如果两个顶点之间没有边连接,则在邻接矩阵中对应的元素为0。

    一个图G有n个顶点,就需要nxn矩阵来去表示。 

    无向图的邻接矩阵

    无向图的邻接矩阵特点:

    • 主对角线为0,右上和左下部分对称 
    • 第i个顶点的度等于第i行1的个数和,等于第i列1的个数和
     有向图的邻接矩阵

    有向图的邻接矩阵特点:

    • 主对角线为0,不一定对称
    • 第i个顶点的出度等于第i行1的个数
    • 第i个顶点的入度等于第i列1的个数
    • 顶点的度=第i行元素之和+第i列元素之和
    网(赋权图)的邻接矩阵

    网是带有路径长度的图,所以对比上面的矩阵,我们只需要把通路1,换成路径的长度即可。

     代码表示
    1. #define Maxnum 100//最大顶点数
    2. //数据类型
    3. typedef struct d {
    4. char id[10];
    5. //……
    6. }
    7. ElemType;
    8. //图的邻接数组
    9. typedef struct graph {
    10. ElemType vexs[Maxnum];//图数据
    11. int arcs[Maxnum][Maxnum];//二维数组
    12. int vexnum;//点数
    13. int arcnum;//边数
    14. }Graph;

    2.邻接表

    邻接表是图的一种最主要存储结构,用来描述图上的每一个点。对于图的每个顶点建立一个容器( n个顶点建立 n 个容器),第 i 个容器中的结点包含顶点vi 的所有邻接顶点。

    一个邻接表需要两种存储结构:顶点表结点边表结点 

    • 顶点:
      •  按编号顺序将顶点数据存储在一维数组中
    • 关联同一顶点的边 (以顶点为尾的弧)
      • 用线性链表存储

    无向图的邻接表

    特点:

    • 邻接表不唯一
    • 若无向图中有 n个顶点e条边,则其邻接表需 n个头结点和2e 个表结点。适宜存储稀疏图。

    有向图的邻接表

    特点:

    • 找出度易找入度难
    • 顶点 vi的出度为第i个单链表中的结点个数。
    • >顶点 vi的入度为整个单链表中邻接点域值是 i-1的结点个数。

    代码表示
    1. //数据结构体
    2. typedef struct d {
    3. char id[10];//字符串编号
    4. //………………
    5. }ElemType;
    6. //边节点存储结构
    7. typedef struct arcnode {
    8. int index;//指向顶点的位置
    9. int weight;//权
    10. struct arcnode* nextarc;//指向下一个边节点
    11. }Anode;
    12. //顶点结点存储结构
    13. typedef struct vexnode {
    14. ElemType data;
    15. Anode* firstarc;
    16. }Vhead;
    17. //图结构
    18. typedef struct {
    19. Vhead* vertices;
    20. int vexnum;
    21. int arcnum;
    22. }Graph;

    3.邻接矩阵和邻接表对比

    邻接矩阵

     优点

    • 直观、简单、好理解
    • 方面检查任意一对顶点间是否存在边
    • 方便找任一顶点的所有“邻接点”(有边直接相连的顶点)
    • 方便计算任一顶点的“度”

    缺点

    • 不便于增加和删除顶点
    • 浪费空间——存稀疏图 (点很多而边很少)有大量无效元素,但是对密图 (特别是完全图) 还是很合算的
    • 浪费时间——统计稀疏图中一共有多少条边
    邻接表

    优点

    • 对于稀疏图来说,邻接表比邻接矩阵更加省空间。
    • 方便遍历某个顶点的所有邻接点,时间复杂度为 O (degree)。
    • 邻接表算法实现简单,易于修改和扩展。

     缺点

    • 重边不好处理 判重比较麻烦 ,还要遍历已有的边,不能直接判断
    • 对确定边的操作效率不高
    • 不方便计算顶点的入度

    图的创建

    1.邻接矩阵创建图(网)

    下面代码是无向网的创建 

    1. #include
    2. #include
    3. #define Maxint 32767
    4. #define Maxnum 100//最大顶点数
    5. //数据类型
    6. typedef struct d {
    7. char id[10];
    8. //……
    9. }
    10. ElemType;
    11. //图的邻接数组
    12. typedef struct graph {
    13. ElemType vexs[Maxnum];//图数据
    14. int arcs[Maxnum][Maxnum];//二维数组
    15. int vexnum;//点数
    16. int arcnum;//边数
    17. }Graph;
    18. //节点id查找下标
    19. int Locate_vex(Graph G, char* id) {
    20. for (int i = 0; i < G.vexnum; i++)
    21. if (strcmp(G.vexs[i].id,id)==0)
    22. return i;
    23. return -1;
    24. }
    25. //构造邻接矩阵(无向图,对称矩阵)(有向图)赋权图
    26. void Create_graph(Graph* G) {
    27. printf("请输入顶点个数和边的个数:\n");
    28. scanf("%d %d", &G->vexnum, &G->arcnum);//输入点数边数
    29. printf("请输入顶点数据:\n");
    30. for (int i = 0; i < G->vexnum; i++) {
    31. scanf("%s", G->vexs[i].id);
    32. }
    33. for (int x = 0; x < G->vexnum; x++) {
    34. for (int y = 0; y < G->vexnum; y++) {
    35. if (x == y)
    36. G->arcs[x][y] = 0;//对角线初始化为0
    37. else
    38. G->arcs[x][y] = Maxint;//其他初始化为Maxint
    39. }
    40. }
    41. printf("请输入边相关数据:\n");
    42. for (int k = 0; k < G->arcnum; k++) {
    43. char a[10], b[10];
    44. int w;
    45. scanf("%s %s %d", a, b, &w);
    46. //a->b
    47. int i = Locate_vex(*G, a);
    48. int j = Locate_vex(*G, b);
    49. //矩阵赋值
    50. G->arcs[i][j] = w;
    51. G->arcs[j][i] = w;//删掉这个,表示有向图
    52. }
    53. }
    54. //输出矩阵
    55. void print_matrix(Graph G) {
    56. printf("矩阵为:\n");
    57. for (int i = 0; i < G.arcnum; i++) {
    58. for (int j = 0; j < G.arcnum; j++)
    59. printf("%-5d ", G.arcs[i][j]);
    60. printf("\n");
    61. }
    62. printf("图的顶点个数和边数:%d,%d\n", G.vexnum, G.arcnum);
    63. }

    结果如下: 

    输入图的结构如下所示: 

     2.邻接表创建图(网)

    对于邻接表的创建,我们是先去创建好顶点表数组,然后通过遍历和头插法把数据作为边表节点插入到顶点表的后面,最后形成邻接表链。代码如下:

    1. #include
    2. #include
    3. //数据结构体
    4. typedef struct datatype {
    5. char id[10];//字符串编号
    6. //………………
    7. }ElemType;
    8. //边节点存储结构
    9. typedef struct arcnode {
    10. int index;//指向顶点的位置
    11. int weight;//权
    12. struct arcnode* nextarc;//指向下一个边节点
    13. }Anode;
    14. //顶点结点存储结构
    15. typedef struct vexnode {
    16. ElemType data;
    17. Anode* firstarc;
    18. }Vhead;
    19. //图结构
    20. typedef struct {
    21. Vhead* vertices;
    22. int vexnum;
    23. int arcnum;
    24. }Graph;
    25. //顶点查找下标
    26. int Locate_vex(Graph G, ElemType v) {
    27. for (int i = 0; i < G.vexnum; i++)
    28. if (strcmp(G.vertices[i].data.id,v.id)==0)
    29. return i;
    30. return -1;
    31. }
    32. //创建头节点
    33. void Create_vexhead(Graph *G,int n) {
    34. G->vertices = (Vhead*)malloc(sizeof(Vhead) *n);
    35. if (!G->vertices) {
    36. printf("ERROR\n");
    37. exit(-1);
    38. }
    39. else {
    40. for (int i = 0; i < n ; i++) {
    41. scanf("%s", G->vertices[i].data.id);
    42. G->vertices[i].firstarc = NULL;
    43. }
    44. }
    45. }
    46. //创建一个边节点
    47. Anode* Create_arcnode(int loca, int w) {
    48. Anode* arc = (Anode*)malloc(sizeof(Anode));
    49. if (!arc)
    50. {
    51. printf("ERROR\n");
    52. exit(-1);
    53. }
    54. arc->index = loca;
    55. arc->nextarc = NULL;
    56. arc->weight = w;
    57. return arc;
    58. }
    59. //创建邻接表(无向图)(有向图)
    60. void Create_graph(Graph* G) {
    61. printf("输入顶点数和边数:\n");
    62. scanf("%d %d", &G->vexnum, &G->arcnum);
    63. printf("输入顶点数据:\n");
    64. Create_vexhead(G, G->vexnum);
    65. printf("输入边数据:\n");
    66. for (int k = 0; k arcnum; k++) {
    67. ElemType a, b;
    68. int w;
    69. scanf("%s%s%d", a.id, b.id, &w);
    70. int i = Locate_vex(*G, a);
    71. int j = Locate_vex(*G, b);
    72. //头插法
    73. //a->b
    74. Anode* p = Create_arcnode(j, w);
    75. p->nextarc = G->vertices[i].firstarc;
    76. G->vertices[i].firstarc = p;
    77. //如果创建有向图的话,直接把下面的代码删掉即可
    78. //b->a
    79. Anode* q = Create_arcnode(i, w);
    80. q->nextarc = G->vertices[j].firstarc;
    81. G->vertices[j].firstarc = q;
    82. }
    83. }
    84. //访问
    85. void visit(Graph G, int index) {
    86. printf("%s ", G.vertices[index].data.id);
    87. }
    88. //输出图
    89. void print(Graph G) {
    90. printf("以下是图的顶点连接关系:\n");
    91. for (int i = 0; i < G.vexnum; i++) {
    92. printf("%s:", G.vertices[i].data.id);
    93. Anode* cur= G.vertices[i].firstarc;
    94. while (cur) {
    95. visit(G, cur->index);
    96. cur = cur->nextarc;
    97. }
    98. printf("\n");
    99. }
    100. printf("顶点和边数分别是:%d %d\n", G.vexnum, G.arcnum);
    101. }

    测试结果:

    好了,以上就是今天的全部内容了,我们下一期学习图的遍历,下次见咯! 

    分享一张壁纸:

  • 相关阅读:
    数据大帝国:大数据与人工智能的巅峰融合
    程序员怎样才能学好算法,推荐好书送给大家
    java之多线程
    Mybatis出现空指针异常解决方法
    [机缘参悟-52]:交浅言深要因人而异
    【自考必看】你能学会的《信息资源管理》,计算机科学与基础(本科)
    Vue双向数据绑定原理(面试必问)
    Netty心跳机制和客户端重连的实现
    使用CNI网络插件(calico)实现docker容器跨主机互联
    团队协作如何确保项目Node版本的一致性?
  • 原文地址:https://blog.csdn.net/m0_73633088/article/details/133949646