【408考点之数据结构】图的基本概念

图的基本概念

图是一种重要的数据结构，它由顶点和顶点之间的边组成。图广泛应用于计算机科学、工程、数学和其他领域，用于表示和解决各种复杂问题。

一、图的定义

1. 图的基本定义：

   • 图 (G) 由一个顶点集合 (V(G)) 和一个边集合 (E(G)) 组成，记为 (G(V, E))。
   • 顶点（Vertex）：图中的一个节点。
   • 边（Edge）：连接两个顶点的连线。

2. 边的类型：

   • 无向边：没有方向性的边，用双向箭头表示，例如 ( (v1, v2) )。
   • 有向边：有方向性的边，用单向箭头表示，例如 ( <v1, v2> )。

二、图的分类

1. 按边的方向分类：

   • 无向图：边没有方向性的图。
   • 有向图：边有方向性的图。

2. 按边的权值分类：

   • 无权图：边没有权值的图。
   • 加权图：边有权值的图，通常表示边的长度、费用等。

三、图的表示方法

1. 邻接矩阵：

   • 用一个二维数组表示顶点之间的连接关系。
   • 对于无向图，矩阵是对称的；对于有向图，矩阵不一定对称。
   • 优点：简单直观，易于实现。
   • 缺点：空间复杂度高，对于稀疏图不适用。

   #define MAXVEX 100
   typedef struct {
       int vexs[MAXVEX];            // 顶点表
       int arc[MAXVEX][MAXVEX];     // 邻接矩阵
       int numVertexes, numEdges;   // 图中当前的顶点数和边数
   } MGraph;
   1
   2
   3
   4
   5
   6

2. 邻接表：

   • 每个顶点对应一个链表，链表中的节点表示与该顶点相连的其他顶点。
   • 优点：节省空间，适用于稀疏图。
   • 缺点：查找顶点之间的边不如邻接矩阵方便。

   typedef struct EdgeNode {        // 边表结点
       int adjvex;                  // 邻接点域，存储该顶点对应的下标
       int weight;                  // 用于存储权值，对于非网图可以不需要
       struct EdgeNode *next;       // 链域，指向下一个邻接点
   } EdgeNode;
   
   typedef struct VertexNode {      // 顶点表结点
       int data;                    // 顶点域，存储顶点信息
       EdgeNode *firstEdge;         // 边表头指针
   } VertexNode, AdjList[MAXVEX];
   
   typedef struct {
       AdjList adjList;
       int numVertexes, numEdges;   // 图中当前顶点数和边数
   } GraphAdjList;
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15

四、图的基本性质

1. 度：

   • 无向图中，顶点的度是与其相连的边的条数。
   • 有向图中，顶点的出度是其出边的条数，入度是其入边的条数。

2. 路径和回路：

   • 路径：从一个顶点到另一个顶点所经过的顶点序列。
   • 简单路径：路径中不包含重复顶点。
   • 回路：路径的起点和终点是同一个顶点。

3. 连通性：

   • 无向图中，如果任意两个顶点之间存在路径，则该图是连通的。
   • 有向图中，如果任意两个顶点之间存在双向路径，则该图是强连通的。

五、图的应用

图的应用非常广泛，以下是一些常见的应用场景：

1. 社交网络分析：用图表示用户及其关系。
2. 交通网络：用图表示城市和道路。
3. 通信网络：用图表示网络节点和通信线路。
4. 电路设计：用图表示电路元件和连接关系。