数据布局之图的分类和存储

图

图(Graph)G由两个聚集V和E组成，记为：G=(V,E)，此中V是极点的有穷非空聚集(实在就是极点)，E是V 中极点偶对的有穷聚集(就是边)。V(G)和E(G)通常分别表现图G的极点聚集以及边聚集，E(G)可以为空聚集，但是此时的图只有极点，没有边。
举个例子：
一个地图：       极点：都会     边：路   大概只有都会没有路就是E(G)可以为空聚集，图只有极点，没有边。
多个都会  a b c d e
a 到b的方法(a到其他)  ：a - b   a -c -  b   a  - c - d  - b
到a也有许多方法 b-a  c-b-a 如许就形成了网状布局
1. 图的分类

• 有向图：
  

边是有方向的。类似车道的单行道
这意味着每条边都从一个极点指向另一个极点，并且这种指向关系是有序的，有向图的 谁人方向的线条称为弧。在有向图中，假如有一条从极点A到极点B的边，那么我们说A指向B（A是出发点，B是尽头），但这并不 意味着B也指向A
示例

• 无向图：
  

边没有方向。这意味着每条边都毗连两个极点，但不区分出发点和终点。在无向图中，假如两个极点由一 条边毗连，那么它们是相邻的，并且这种相邻关系是对称的。
示例

• 网（带权图）
  

假如在图的每条边（大概弧）都被赋予一个权重（常用于表现节点之间毗连的成本或间隔），即为网 （带权图）

极点的度
表现与极点相连的边的数量。

• 无向图
  

• 有向图
  

在有向图中，极点的度分为入度（In-degree）和出度（Out-degree）。
入度：指向该极点的边的数量。
出度：从该极点出发的边的数量。

• 路径
  

图的路径是指由图中的极点和边所构成的序列，此中极点之间通过边相连。
两个极点之间存在路径（到达方式），阐明它们是连通。
路径可以是有向的或无向 的，这取决于图的范例。

a->c连通   c->a不是由于 这是有向图c到a没有路径到达
若恣意两个极点之间都是连通的话，则图是连通图。

这就是联通图

• 毗邻点
  

毗邻点的界说是：假如两个极点之间存在一条边，那么这两个极点就互为毗邻点
2 图的存储

2.1 毗邻矩阵

矩阵（二维数组）
毗邻矩阵是表现极点间相邻关系的矩阵。
对于n个极点的图，毗邻矩阵是一个n×n的二维数组（只存储0 1）。两个极点存在直接毗连到边就是1，否则是0，本身到本身一样平常也是0
在无向图中，毗邻矩阵是对称的（对于对角线对称），而在有向图中则不愿定。

• 
  
  
  
  • 无向图
    
  
  

对应的毗邻矩阵是
12345101001210001300011400100511100

• ​
  
  
  
  • 有向图
    
  
  

对应的毗邻矩阵是
12345101000210001300000400100510100代码如下：

• 有向图：
  

1. #include <iostream>
2. using namespace std;
4. #define MAX_VERTICES 100 // 最大定点数
6. // 初始化邻接矩阵  int(*p)[MAX_VERTICES]也可以数组指针
7. void initalizeGraph(int adjMartix[MAX_VERTICES][MAX_VERTICES], int n)
8. {
9.     for (int i = 0; i < n; i++)
10.     {
11.         for (int j = 0; j < n; j++)
12.         {
13.             adjMartix[i][j] = 0; // 初始化为0，表示没有边
14.         }
15.     }
16. }
18. // 添加有向边
19. void addDirectedEdge(int adjMartix[MAX_VERTICES][MAX_VERTICES], int u, int v) // uv是出度也是入度
20. {
21.     // 两目标直接连接 有向图
22.     adjMartix[u][v] = 1;
23.     // // 无向图
24.     // adjMartix[v][u]  = 1;
25. }
26. void printGraph(int adjMartix[MAX_VERTICES][MAX_VERTICES], int n)
27. {
28.     for (int i = 0; i < n; i++)
29.     {
30.         for (int j = 0; j < n; j++)
31.         {
32.             printf("%d ", adjMartix[i][j]); // 初始化为0，表示没有边
33.         }
34.         printf("\n");
35.     }
36. }
37. //  打印图
39. int main()
40. {
41.     int adjMartix[MAX_VERTICES][MAX_VERTICES]; // 图
42.     // 节点
43.     int n = 5;
44.     // 初始化图
45.     initalizeGraph(adjMartix, n);
47.     // 添加有向边
48.     addDirectedEdge(adjMartix, 0, 1);
49.     addDirectedEdge(adjMartix, 1, 0);
50.     addDirectedEdge(adjMartix, 1, 4);
51.     addDirectedEdge(adjMartix, 4, 0);
52.     addDirectedEdge(adjMartix, 4, 2);
53.     addDirectedEdge(adjMartix, 3, 2);
55.     // 打印有向图
56.     printGraph(adjMartix, n);
57.    
58.     return 0;
59. }

复制代码

无向图：

1. #include <iostream>
2. using namespace std;
4. #define MAX_VERTICES 100 // 最大定点数
6. // 初始化邻接矩阵  int(*p)[MAX_VERTICES]也可以数组指针
7. void initalizeGraph(int adjMartix[MAX_VERTICES][MAX_VERTICES], int n)
8. {
9.     for (int i = 0; i < n; i++)
10.     {
11.         for (int j = 0; j < n; j++)
12.         {
13.             adjMartix[i][j] = 0; // 初始化为0，表示没有边
14.         }
15.     }
16. }
18. // 添加有向边
19. void addDirectedEdge(int adjMartix[MAX_VERTICES][MAX_VERTICES], int u, int v) // uv是出度也是入度
20. {
21.     // 两目标直接连接 有向图
22.     adjMartix[u][v] = 1;
23.     // // 无向图
24.     adjMartix[v][u]  = 1;
25. }
26. void printGraph(int adjMartix[MAX_VERTICES][MAX_VERTICES], int n)
27. {
28.     for (int i = 0; i < n; i++)
29.     {
30.         for (int j = 0; j < n; j++)
31.         {
32.             printf("%d ", adjMartix[i][j]); // 初始化为0，表示没有边
33.         }
34.         printf("\n");
35.     }
36. }
37. //  打印图
39. int main()
40. {
41.     int adjMartix[MAX_VERTICES][MAX_VERTICES]; // 图
42.     // 节点
43.     int n = 5;
44.     // 初始化图
45.     initalizeGraph(adjMartix, n);
47.     // 添加有向边
48.     addDirectedEdge(adjMartix, 0, 1);
49.     addDirectedEdge(adjMartix, 0, 4);
50.     addDirectedEdge(adjMartix, 1, 4);
51.     addDirectedEdge(adjMartix, 5, 3);
52.     addDirectedEdge(adjMartix, 3, 4);
54.     // 打印有向图
55.     printGraph(adjMartix, n);
56.    
57.     return 0;
58. }

复制代码

长处：
编码简单，轻易明确。
便于查抄图中恣意两个极点之间是否存在边。
便于盘算图中极点的度。
缺点：
对于希罕图，毗邻矩阵会浪费大量存储空间，由于矩阵中的大部门元素都是0。
在举行图的遍历等操作时，大概必要遍历整个矩阵，服从较低。
2.2 毗邻表

毗邻表是图的一种链式存储布局。对于图中的每个极点，毗邻表都存储一个链表，该链表包含与该极点相邻的全部极点。
比方下图1包含和他相邻的全部极点，2和3
可以省略边：毗连关系2-3（隐含表现边）（下节讲，下面的代码不省略）
1 - 2 - 3
1 - 3

代码如下

1. #include <iostream>
2. using namespace std;
4. // 定义边
5. typedef struct EdgeNode
6. {
7.     int adjvex;            // 邻接点 终点
8.     struct EdgeNode *next; // 下一条边 个指针用于连接同一起点的多条边。这样，我们就可以通
9.     // 过遍历next指针来访问从A出发的所有边。
10. } EdgeNode;
12. // 定义顶点
13. typedef struct VertexNode
14. {
15.     int data;            // 起点信息
16.     EdgeNode *FirstNode; // 这个指针用于从顶点出发找到其第一条边 。这样，我们就可以从任意一
17.     // 个顶点开始，通过firstedge找到其所有邻接点。
18. } VertexNode;
20. typedef struct Grasp_List
21. {
22.     VertexNode *newNode; // 顶点
23.     int numVertices;     // 顶点数
24.     int numEdges;        // 边数
25. } Grasp_List;
27. // 初始化函数
28. void InitGraph(Grasp_List *graph, int n)
29. {
30.     graph->newNode = new VertexNode[n](); // 分配内存 ()会进行初始化
31.     graph->numVertices = n;               //// 顶点5
32.     graph->numEdges = 0;                  // 边0
33.     for (int i = 0; i < n; i++)
34.     {
35.         graph->newNode[i].data = i;            // 初始化每个顶点的数据
36.         graph->newNode[i].FirstNode = nullptr; // 初始化第一条边为空
37.     }
38. }
40. // 向图中添加边 u起始顶点 v邻接点
41. void AddEdge(Grasp_List *graph, int u, int v)
42. {
43.     // 创建边
44.     EdgeNode *newEdgeNode = (EdgeNode *)malloc(sizeof(EdgeNode)); // 创建新边节点
45.     // 分配失败
46.     if (!newEdgeNode)
47.     {
48.         perror("分配失败");
49.         return;
50.     }
51.     newEdgeNode->adjvex = v; // 设置邻接点 也就是终点
52.     // 插入 头插法 把边直接
53.     newEdgeNode->next = graph->newNode[u].FirstNode; // 下一条边=原来的第一条边
54.     graph->newNode[u].FirstNode = newEdgeNode;       // 更新第一条边
55.     graph->numEdges++;                               // 边数加1
57.     //// 如果是无向图 还需要再添加一条边
58.     // EdgeNode* newNodeV = (EdgeNode*)malloc(sizeof(EdgeNode)); // 创建新边节点
59.     // if (!newNodeV)
60.     //{
61.     //     printf("申请内存失败\n");
62.     //     exit(-1);
63.     // }
64.     // newNodeV->adjvex = u;                     // 设置邻接点
65.     ////头插法
66.     // newNodeV->next = G->adjList[v].firstedge; // 下一条边 = 原来的第一条边
67.     // G->adjList[v].firstedge = newNodeV;       // 更新第一条边
68. }
70. // 打印邻接表
71. void printGraph(Grasp_List *graph)
72. {
73.     if (graph == nullptr)
74.     {
75.         cout << "我是空图" << endl;
76.         return;
77.     }
78.     printf("Graph with %d vertices and  %d edge:\n", graph->numVertices, graph->numEdges);
79.     // 根据定点数遍历
80.     for (int i = 0; i < graph->numVertices; i++)
81.     {
82.         printf("vertices %d: ", graph->newNode[i].data); // 打印顶点
83.         // 找到顶点第一条边
84.         EdgeNode *p = graph->newNode[i].FirstNode; // 保存
85.         while (p)
86.         {
87.             // 邻接点
88.             printf(" %d", p->adjvex);
89.             // 下一条边
90.             p = p->next;
91.         }
92.         printf("\n");
93.     }
94. }
96. // 释放图占用的内存
97. void freeGraph(Grasp_List *graph)
98. {
99.     if (graph == NULL)
100.     {
101.         return;
102.     }
103.     // 释放边内存
104.     for (int i = 0; i < graph->numVertices; i++)
105.     {
106.         EdgeNode *curerent = graph->newNode[i].FirstNode;
107.         EdgeNode *tmp = nullptr;
108.         while (curerent)
109.         {
110.             tmp = curerent;
111.             curerent = curerent->next;
112.             free(tmp);
113.             tmp = nullptr;
114.         }
115.         curerent = nullptr;
116.     }
117.     // 释放顶点内存
118.     delete[] (graph->newNode);
119.     graph->newNode = nullptr;
121.     // 释放图本身的内存
122.     delete graph;
123. }
125. // 主函数实例
126. int main()
127. {
129.     Grasp_List *G  = new Grasp_List;
130.     // 初始化图
131.     InitGraph(G, 5);
133.     // 添加边
134.     AddEdge(G, 0, 1);
136.     AddEdge(G, 0, 4);
137.     AddEdge(G, 1, 2);
138.     AddEdge(G, 1, 3);
139.     AddEdge(G, 2, 3);
141.     // 打印图
142.     printGraph(G);
144.     // 释放图
145.     freeGraph(G);
147.     return 0;
148. }

复制代码

表明一个遍创建的过程

1. AddEdge(G, 0, 1);

复制代码

• 这表现在图 G 中添加一条从极点 0 到极点 1 的边。
  
• 详细步调如下：
  
  
  
  • 创建一个新边节点 newEdgeNode，并为其分配内存。
    
  • 将新边的毗邻点设置为 1。
    
  • 使用头插法将新边插入到极点 0 的边链表中，使新边成为极点 0 的第一条边。
    
  • 图的边数增长 1
    
  
  
• 形成链表的过程
  在调用 AddEdge(G, 0, 1) 后，极点 0 和极点 1 通过一条边毗连起来。详细来说：
  
  
  
  • 极点 0 的边链表中新增了一个边节点，其 adjvex 字段为 1。
    
  • 这个边节点通过 next 指针毗连到原来极点 0 的边链表
    
  
  

长处：
节流存储空间，特别是对于希罕图。
便于添加和删除边。
便于举行图的遍历等操作。
缺点：
未便于查抄图中恣意两个极点之间是否存在边（必要遍历两个极点的毗邻表）。
在某些环境下，大概必要额外的空间来存储极点的信息（如极点的索引或名称）。