首页 > 其他分享 >图——图的类型定义及存储结构

图——图的类型定义及存储结构

时间：2024-07-14 20:57:15浏览次数：9  
标签：存储 int vertex Vertex vertices 类型定义 邻接 顶点 结构

在上篇文章我们学习了图的定义和基本术语，大家可以通过下面的链接学习：

图的定义及基本术语

这篇文章我们就来系统的学习一下图的类型定义和存储结构。

案例引入：

六度空间理论:你和任何一个陌生人之间所间隔的人不会超过6个，也就是说，最多通过6个中间人你就能够认识任何一个陌生人。

把六度空间理论中的人际关系网络抽象成一个无向图G。用图G中的一个顶点表示一个人，两个人认识与否用代表这两个人的顶点之间是否有一条边来表示。从任一顶点出发用广度优先方法对图进行遍历，统计所有路径长度不超过7的顶点。 

一，图的类型定义

对图的基本操作有—— 

CreateGraph(&G,V,VR)

      初始条件：V是图的顶点集，VR是图中弧的集合。

      操作结果：按V和VR的定义构造图G。

DFSTraverse(G)

      初始条件：图G存在。

      操作结果：对图进行深度优先遍历。

BFSTraverse(G)

      初始条件：图G存在。

      操作结果：对图进行广度优先遍历。

知道了图的抽象类型定义，那么具体该如何在存储空间中实现对图的存储?

二，图的存储结构

我们知道，数据结构的存储结构一共有两种：顺序存储和链式存储，同样对于图而言，图的存储结构有以下方式：

1.顺序存储结构：数组表示法（邻接矩阵）

2.链式存储结构：多重链表（邻接表，邻接多重表，十字链表）

我们将重点学习——

邻接矩阵(数组)表示法

邻接表(链式)表示法

A. 邻接矩阵(数组)表示法

 建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）。

 设图 A = (V, E) 有 n 个顶点，则图的邻接矩阵是一个二维数组 A.Edge[n][n]，定义为：

 a.无向图的邻接矩阵表示法

分析1：无向图的邻接矩阵是对称的；

分析2：顶点i 的度＝第 i 行 (列) 中1 的个数；

特别：完全图的邻接矩阵中，对角元素为0，其余1

b.有向图的邻接矩阵表示法

注：在有向图的邻接矩阵中，

   第i行含义：以结点vi为尾的弧(即出度边）；

   第i列含义：以结点vi为头的弧(即入度边）。

分析1：

        有向图的邻接矩阵可能是不对称的。

分析2：

       顶点的出度=第i行元素之和

       顶点的入度=第i列元素之和

       顶点的度=第i行元素之和+第i列元素之和

c. 网（即有权图）的邻接矩阵表示法

用代码如何实现邻接矩阵表示法对于图的存储？

我们用两个数组分别存储顶点表和邻接矩阵

#define MaxInt 32767                    	//表示极大值，即∞
#define MVNum 100                       	//最大顶点数 
typedef char VerTexType;              	//假设顶点的数据类型为字符型 
typedef int ArcType;                  	//假设边的权值类型为整型 
typedef struct{ 
  VerTexType vexs[MVNum];            		//顶点表 
  ArcType arcs[MVNum][MVNum];      	//邻接矩阵 
  int vexnum,arcnum;                		//图的当前点数和边数 
}AMGraph;

邻接矩阵表示法来创建无向网

 具体代码如下：

#include <stdio.h>

void create_undirected_graph(int vertices, int edges) {
    // 创建一个大小为顶点数乘以顶点数的邻接矩阵，并初始化为0
    int adjacency_matrix[vertices][vertices];
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            adjacency_matrix[i][j] = 0;
        }
    }
    
    // 遍历每条边的信息，更新邻接矩阵
    for (int i = 0; i < edges; i++) {
        int u, v, weight;
        printf("Enter edge %d: ", i + 1);
        scanf("%d %d %d", &u, &v, &weight);
        adjacency_matrix[u][v] = weight;
        adjacency_matrix[v][u] = weight;
    }
    
    // 打印邻接矩阵
    printf("Adjacency Matrix:");
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            printf("%d ", adjacency_matrix[i][j]);
        }
        printf("");
    }
}

int main() {
    int vertices, edges;
    printf("Enter the number of vertices: ");
    scanf("%d", &vertices);
    printf("Enter the number of edges: ");
    scanf("%d", &edges);
    create_undirected_graph(vertices, edges);
    return 0;
}

 输入案例

输出案例： 

邻接矩阵表示法的优缺点：

 

 B.邻接表(链式)表示法

对每个顶点vi 建立一个单链表，把与vi有关联的边的信息链接起来，每个结点设为3个域；

每个单链表有一个头结点（设为2个域），存vi信息； 

每个单链表的头结点另外用顺序存储(一维数组)结构存储。

无向图的邻接表表示：

邻接表不唯一，因各个边结点的链入顺序是任意的

空间效率为O(n+2e)。

若是稀疏图(e<<n2)，比邻接矩阵表示法O(n2)省空间。

TD(Vi)=单链表中链接的结点个数

有向图的邻接表表示：

 空间效率为O(n+e)

 出度 ：OD(Vi)＝单链出边表中链接的结点数

入度 ：ID(Vi)＝邻接点域为Vi的弧个数

   度  ：  TD(Vi) = OD( Vi )  +  I D( Vi )

例：已知某网的邻接（出边）表，请画出该网络。 

当邻接表的存储结构形成后，图便唯一确定！ 

邻接表的存储结构：

我们需要知道顶点及边的结构

 下面是实际的代码实现：

#include <stdio.h>
#include <stdlib.h>

typedef struct EdgeNode {
    int adjvex; // 邻接点域，存储该边所指向的顶点的位置
    struct EdgeNode *next; // 链接到下一个邻接点的指针
} EdgeNode;

typedef struct VertexNode {
    char data; // 顶点信息
    EdgeNode *firstedge; // 指向第一个邻接点的指针
} VertexNode, AdjList[100];

typedef struct {
    AdjList adjList;
    int numVertexes, numEdges;
} GraphAdjList;

// 创建图的邻接表结构
void createGraph(GraphAdjList *G) {
    printf("Enter the number of vertices: ");
    scanf("%d", &G->numVertexes);
    printf("Enter the number of edges: ");
    scanf("%d", &G->numEdges);

    for (int i = 0; i < G->numVertexes; i++) {
        printf("Enter the data for vertex %d: ", i + 1);
        getchar(); // 清除缓冲区中的换行符
        scanf("%c", &G->adjList[i].data);
        G->adjList[i].firstedge = NULL;
    }

    for (int i = 0; i < G->numEdges; i++) {
        int u, v;
        printf("Enter edge %d (u, v): ", i + 1);
        scanf("%d %d", &u, &v);

        EdgeNode *newEdge = (EdgeNode *)malloc(sizeof(EdgeNode));
        newEdge->adjvex = v - 1; // 减1是为了将顶点编号转换为数组下标
        newEdge->next = G->adjList[u - 1].firstedge;
        G->adjList[u - 1].firstedge = newEdge;

        // 如果是无向图，需要添加反向边
        EdgeNode *reverseEdge = (EdgeNode *)malloc(sizeof(EdgeNode));
        reverseEdge->adjvex = u - 1;
        reverseEdge->next = G->adjList[v - 1].firstedge;
        G->adjList[v - 1].firstedge = reverseEdge;
    }
}

int main() {
    GraphAdjList graph;
    createGraph(&graph);
    return 0;
}

输入步骤

  1. 输入顶点数：5
  2. 输入边数：6

然后，依次输入每个顶点的数据：

  • 输入顶点1的数据: A
  • 输入顶点2的数据: B
  • 输入顶点3的数据: C
  • 输入顶点4的数据: D
  • 输入顶点5的数据: E

接着，输入每条边的信息：

  • 输入边1: 1 2 10
  • 输入边2: 1 3 20
  • 输入边3: 2 3 30
  • 输入边4: 2 4 40
  • 输入边5: 3 5 50
  • 输入边6: 4 5 60

  输出的邻接表将如下：

 

顶点1 (A) 的邻接表：

  • 顶点2 (B) 权重10
  • 顶点3 (C) 权重20

顶点2 (B) 的邻接表：

  • 顶点1 (A) 权重10
  • 顶点3 (C) 权重30
  • 顶点4 (D) 权重40

顶点3 (C) 的邻接表：

  • 顶点1 (A) 权重20
  • 顶点2 (B) 权重30
  • 顶点5 (E) 权重50

顶点4 (D) 的邻接表：

  • 顶点2 (B) 权重40
  • 顶点5 (E) 权重60

顶点5 (E) 的邻接表：

  • 顶点3 (C) 权重50
  • 顶点4 (D) 权重60

邻接表的操作举例

如何用邻接表表示法创建无向网：

算法思想：

 实际的代码实现：

#include <stdio.h>
#include <stdlib.h>

// 定义边的结构体
typedef struct Edge {
    int src, dest;
} Edge;

// 定义顶点的结构体
typedef struct Vertex {
    int id;
    Edge *edges; // 指向边的数组的指针
    int numEdges; // 顶点的边的数量
} Vertex;

// 创建一个新的顶点
Vertex* createVertex(int id) {
    Vertex *vertex = (Vertex *)malloc(sizeof(Vertex));
    vertex->id = id;
    vertex->edges = NULL;
    vertex->numEdges = 0;
    return vertex;
}

// 添加一条边到顶点
void addEdge(Vertex *vertex, int src, int dest) {
    // 扩展边的数组大小
    vertex->edges = (Edge *)realloc(vertex->edges, (vertex->numEdges + 1) * sizeof(Edge));
    // 设置新的边的信息
    vertex->edges[vertex->numEdges].src = src;
    vertex->edges[vertex->numEdges].dest = dest;
    // 增加边的数量
    vertex->numEdges++;
}

// 打印邻接表
void printAdjacencyList(Vertex **vertices, int numVertices) {
    for (int i = 0; i < numVertices; i++) {
        printf("Vertex %d: ", vertices[i]->id);
        for (int j = 0; j < vertices[i]->numEdges; j++) {
            printf("(%d, %d) ", vertices[i]->edges[j].src, vertices[i]->edges[j].dest);
        }
        printf("\n");
    }
}

int main() {
    int numVertices = 5; // 假设有5个顶点
    Vertex **vertices = (Vertex **)malloc(numVertices * sizeof(Vertex *));

    // 创建顶点并初始化邻接表
    for (int i = 0; i < numVertices; i++) {
        vertices[i] = createVertex(i);
    }

    // 添加边到邻接表
    addEdge(vertices[0], 0, 1);
    addEdge(vertices[0], 0, 4);
    addEdge(vertices[1], 1, 2);
    addEdge(vertices[1], 1, 3);
    addEdge(vertices[1], 1, 4);
    addEdge(vertices[2], 2, 3);
    addEdge(vertices[3], 3, 4);

    // 打印邻接表
    printAdjacencyList(vertices, numVertices);

    // 释放内存
    for (int i = 0; i < numVertices; i++) {
        free(vertices[i]->edges);
        free(vertices[i]);
    }
    free(vertices);

    return 0;
}

 得到的无向网的邻接表：

 邻接表表示法的优缺点

邻接表与邻接矩阵表示法的关系：

首先是两者的联系

 然后是区别

 对于邻接表来说，又存在以下问题，因此我们又引入了十字链表与邻接多重表来提升效率。

 C .十字链表（用于有向图）

十字链表(Orthogonal List)是有向图的另一种链式存储结构。我们也可以把它看成是将有向图的邻接表和逆邻接表结合起来形成的一种链表。

有向图中的每一条弧对应十字链表中的一个弧结点，同时有向图中的每个顶点在十字链表中对应有一个结点，叫做顶点结点。

对于邻接表来说，顶点结点除了存储顶点的数据外，还有一个指针域指向他的一个邻接点，这个邻接点除了存储此邻接点的数据，还有一个指针指向第一个顶点的又一个邻接点。

而在十字链表中，我们对于顶点结点和边结点都有所修改。

 对于顶点结点

对于边结点

画图理解： 

#include <stdio.h>
#include <stdlib.h>

// 定义十字链表的节点结构体
typedef struct CrossListNode {
    int row; // 行号
    int col; // 列号
    int data; // 数据域
    struct CrossListNode *right; // 指向同一行右侧节点的指针
    struct CrossListNode *down; // 指向同一列下方节点的指针
} CrossListNode;

// 创建一个新的十字链表节点
CrossListNode* createNode(int row, int col, int data) {
    CrossListNode *newNode = (CrossListNode *)malloc(sizeof(CrossListNode));
    newNode->row = row;
    newNode->col = col;
    newNode->data = data;
    newNode->right = NULL;
    newNode->down = NULL;
    return newNode;
}

// 插入一个新的节点到十字链表中
void insertNode(CrossListNode **head, int row, int col, int data) {
    if (*head == NULL) {
        *head = createNode(row, col, data);
        (*head)->right = createNode(row, col, data);
        (*head)->down = createNode(row, col, data);
    } else {
        CrossListNode *temp = *head;
        while (temp->down != NULL && temp->down->col != col) {
            temp = temp->down;
        }
        if (temp->down == NULL || temp->down->col != col) {
            CrossListNode *newColHead = createNode(row, col, data);
            newColHead->down = temp->down;
            temp->down = newColHead;
        }
        while (temp->right != NULL && temp->right->row != row) {
            temp = temp->right;
        }
        if (temp->right == NULL || temp->right->row != row) {
            CrossListNode *newRowHead = createNode(row, col, data);
            newRowHead->right = temp->right;
            temp->right = newRowHead;
        }
    }
}

// 打印十字链表
void printCrossList(CrossListNode *head) {
    if (head == NULL) {
        printf("Empty cross list.");
        return;
    }
    CrossListNode *rowHead = head;
    while (rowHead != NULL) {
        CrossListNode *colHead = rowHead;
        while (colHead != NULL) {
            printf("(%d, %d) = %d ", colHead->row, colHead->col, colHead->data);
            colHead = colHead->right;
        }
        rowHead = rowHead->down;
    }
}

int main() {
    CrossListNode *head = NULL;
    insertNode(&head, 0, 0, 1);
    insertNode(&head, 0, 1, 2);
    insertNode(&head, 1, 0, 3);
    insertNode(&head, 1, 1, 4);
    printCrossList(head);
    return 0;
}

 结果为：

(0, 0) = 1 (0, 0) = 1 (1, 0) = 3 (0, 0) = 1 (0, 1) = 2 (1, 1) = 4 (0, 1) = 2 

D .邻接多重表（用于无向图）

回顾邻接表

 因此在邻接多重表中，对于顶点结点和边结点我们再次改进

顶点结点：

 边结点：

 画图理解

实际的代码实现：

#include <stdio.h>
#include <stdlib.h>

// 定义顶点的结构体
typedef struct Vertex {
    int id; // 顶点的标识符
    int degree; // 顶点的度数
    struct Edge *edges; // 指向边的数组的指针
} Vertex;

// 定义边的结构体
typedef struct Edge {
    int dest; // 边的终点
    struct Edge *next; // 指向下一条边的指针
} Edge;

// 创建一个新的顶点
Vertex* createVertex(int id) {
    Vertex *vertex = (Vertex *)malloc(sizeof(Vertex));
    vertex->id = id;
    vertex->degree = 0;
    vertex->edges = NULL;
    return vertex;
}

// 添加一条边到顶点
void addEdge(Vertex *vertex, int dest) {
    Edge *newEdge = (Edge *)malloc(sizeof(Edge));
    newEdge->dest = dest;
    newEdge->next = vertex->edges;
    vertex->edges = newEdge;
    vertex->degree++;
}

// 打印邻接多重表
void printAdjacencyList(Vertex **vertices, int numVertices) {
    for (int i = 0; i < numVertices; i++) {
        printf("Vertex %d: ", vertices[i]->id);
        Edge *edge = vertices[i]->edges;
        while (edge != NULL) {
            printf("%d ", edge->dest);
            edge = edge->next;
        }
        printf("");
    }
}

int main() {
    int numVertices = 5; // 假设有5个顶点
    Vertex **vertices = (Vertex **)malloc(numVertices * sizeof(Vertex *));

    // 创建顶点并初始化邻接多重表
    for (int i = 0; i < numVertices; i++) {
        vertices[i] = createVertex(i);
    }

    // 添加边到邻接多重表
    addEdge(vertices[0], 1);
    addEdge(vertices[0], 4);
    addEdge(vertices[1], 2);
    addEdge(vertices[1], 3);
    addEdge(vertices[1], 4);
    addEdge(vertices[2], 3);
    addEdge(vertices[3], 4);

    // 打印邻接多重表
    printAdjacencyList(vertices, numVertices);

    // 释放内存
    for (int i = 0; i < numVertices; i++) {
        Edge *edge = vertices[i]->edges;
        while (edge != NULL) {
            Edge *temp = edge;
            edge = edge->next;
            free(temp);
        }
        free(vertices[i]);
    }
    free(vertices);

    return 0;
}

 结果如下：

Vertex 0: 4 1 Vertex 1: 4 3 2 Vertex 2: 3 Vertex 3: 4 Vertex 4:

 

到此图的类型定义和存储结构就结束啦，如果文章对你有用的话请个赞支持一下吧！

下篇文章将更新图的遍历内容。

标签：存储,int,vertex,Vertex,vertices,类型定义,邻接,顶点,结构
From： https://blog.csdn.net/Blusher1/article/details/140420178

相关文章

  • 数据结构（单链表（1））
    前言线性表中有着许多的结构，如顺序表和链表。而单链表则是链表的最基础的一种形式，下面就让我们对其做一个了解。概念概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。结构我们可以将单链表的结构想象成火车的......
  • MySQL存储引擎的选择：深入解析与策略
    MySQL数据库管理系统之所以强大，部分原因在于它提供了多种存储引擎，每种引擎都针对特定的应用场景进行了优化。尽管MySQL支持多种存储引擎，但其中最常用且值得深入探讨的无疑是MyISAM、InnoDB以及MEMORY（HEAP）这三种。每种存储引擎都有其独特的优缺点，合理选择能够显著提升数据库的性......
  • PMP-组织结构类型
      职能型、矩阵型（强、弱、均衡）、项目导向（复合型、混合型），最常考，矩阵型为主。 矩阵型具有多重的的汇报关系，但是他有专门的项目目的，好处是更高的提升项目的资源使用效率，又让项目不至于太高的人力成本。职能型组织 ▪层级型结构，横向沟通困难，项目一般在职能部门内执行为主......
  • DedeCMS模板目录的文件目录结构
    templets ┣━default·······································默认模板目录 ┃   ┣━style·······································模板CSS样式目录 ┃   ┣━js··......
  • 高级数据结构-可并堆
    可并堆，就是可以合并的堆。堆满足一个性质，就是当前节点，都大于或者等于他的所有子树上的节点，自然在这里我所讲的是结点的权值。显而易见，既然可并堆是堆的一种，容易推出，可并堆也满足这个性质。现在思考一个问题，当题目里需要合并两个堆的时候，该如何合并呢？如果只是普通的堆的话，我们可以......
  • 高质量C/C++编程指南总结（一）—— 文件结构
    1.版权和版本的声明应位于头文件和定义文件的开头，主要包括的内容有：版本信息。文件名称、文件标识、摘要。当前的版本号、作者/修改者、完成日期。历史版本信息（取代版本、原作者、完成日期）。2.头文件结构为了防止头文件被重复引用，应当使用ifndef/define/endif结构产生......
  • 数据结构与算法分析实验7 构造哈夫曼树和生成哈夫曼编码
    文章目录1.上机名称2.上机要求3.上机环境4.程序清单(写明运行结果及结果分析)4.1程序清单4.1.1head.h头文件内容如下：4.1.2head.cpp实现文件内容如下:4.1.3源文件main.cpp内容如下：4.2程序运行结果5.上机体会1.上机名称构造哈夫曼树和生成哈夫曼编码2.上机......
  • 如何恢复VMFS存储卷中的数据
    一、评估与准备评估损失：首先，需要确定数据损失的程度和范围，了解哪些虚拟机受到了影响。备份现有数据：在进行任何恢复操作之前，应尽可能备份现有的VMFS卷和受影响的虚拟机文件，以防恢复过程中数据进一步损坏。准备恢复环境：建立一个安全、可靠且与生产环境隔离的恢复环境，以便在其......
  • 衡庐浅析·C语言程序设计·第三章·三种基本结构之顺序结构
        本文适用于大学的期中期末考试、专升本（专接本、专插本）考试、408等考研预科。如有相关题目疑问或建议欢迎在评论区进行互动。    转载请标明出处。在介绍C的三种基本结构之前，我们首先来逐字逐句的解析一些代码语句，以便更好地上手并学习接下来的内容。此处......
  • 光纤存储中raid5出现故障数据恢复
    一、故障检测与评估检查RAID状态：使用RAID管理或存储管理工具检查RAID5阵列的状态，确认故障的具体表现和受影响的硬盘。评估数据损失：确定哪些数据受到影响，评估数据恢复的重要性和紧急性。二、数据保护立即停止写入操作：一旦发现RAID5故障，应立即停止对存储卷的任何写入操作，......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99