浅谈【数据结构】图-图的概念

目录

1、图

1.1图的分类

1.2路径

1.3连通图

2、图的存储结构

2.1数组表示法

---

谢谢帅气美丽且优秀的你看完我的文章还要点赞、收藏加关注

没错，说的就是你，不用再怀疑！！！

希望我的文章内容能对你有帮助，一起努力吧！！！

---

1、图

图的定义：图（graph）非线性的数据结构，形式描述为：graph=（V,R）

其中V是图中元素Vn（称为顶点Vertex）的集合，当n=0，V是空集

其中R是图中顶点之间的关系集，为顶点vi、vj之间是否存在路径（关系）的判断条件。即vi、vj之 间存在关系，则关系属于R

1.1图的分类

• 有向图（Digraph）
  • 有方向的图就是有向图
  • 有向图的那个方向的线条称为：弧
• 无向图（Undigraph）
  • 没有方向的图就是无向图
  • 无向图的那个线条称为：边
• 网：
  • 若在图的关系上面,或者是上去附加一个值w，称w为弧上或者是边上的权值。
  • 带权的图称为：网（权值w的具体含义在不同的应用场景下去定义，比如：顶点表示城市）

顶点的度

顶点的度：顶点的边或者是顶点的弧条数称为：度

但是有向图分为：入度和出度。

1.2路径

路径：一个顶点到另一个顶点的方式（怎么到达的）

1.3连通图

两个顶点之间存在路径（到达方式），说明它们是连通。若任意两个顶点之间都是连通的话，则图是连 通图。

有向图则称为：强连通图

2、图的存储结构

数组表示法、邻接表、逆邻接表、十字链表、...

2.1数组表示法

数组表示法：又称邻接矩阵

使用一个二维数组来描述图的顶点之间的关系集R。 G=(V,R)

用一个一维数组来存储图中顶点集V

***示例代码***

#include <iostream>// 顶点数量是10个
#define VertexMaxCount 10// 图类型
typedef struct 
{// 关系集bool R[VertexMaxCount][VertexMaxCount];// 顶点集std::string V[VertexMaxCount];// 顶点数量int vertex_count;
}Graph;// 关系类型
typedef  struct 
{int index_s; // 关系开始顶点下标int index_e; // 关系结束顶点下标bool r;  // 关系
}R;/*@brief 为一个邻接矩阵图增加一个顶点@param graph  需要增加顶点的图指针@param vertex 需要增加的顶点
*/
void addVertex(Graph *graph,std::string vertex)
{// 判断图是否存在if(!graph)return;// 添加新顶点graph->V[graph->vertex_count] = vertex;// 更新顶点数量graph->vertex_count++;
}int getIndex(Graph*graph,std::string vertex)
{if(!graph)return -1;for(int index=0;index < VertexMaxCount;index++)if(graph->V[index] == vertex)return index; // 返回顶点在图中的下标return -1; // 表示顶点不在图中
}/*@brief 为一个邻接矩阵图增加关系@param graph 需要增加关系的图指针@param r 增加新关系
*/
void addR(Graph *graph,R r)
{// 判断图是否存在if(!graph)return;// 添加关系graph->R[r.index_s][r.index_e] = r.r;
}Graph *creatGraph()
{// 申请了一个邻接矩阵的空间Graph * graph = new Graph;std::cout << "请依次输入顶点：";// 增加顶点while(1){std::string vertex = "结束";std::cin >> vertex;if(vertex == "结束")break; // 增加进入图addVertex(graph,vertex);}// 先初始化关系for(int row = 0;row < VertexMaxCount;row++){for(int column = 0;column < VertexMaxCount;column++)if(row == column)graph->R[row][column] = true;elsegraph->R[row][column] = false;}// 增加关系while(1){std::cout << "请输入顶点之间的关系：";std::string start_vertex = "结束";std::string end_vertex = "结束";std::cin >> start_vertex;std::cin >> end_vertex;if(start_vertex == "结束"||end_vertex == "结束")break;R r;r.index_s = getIndex(graph,start_vertex);r.index_e = getIndex(graph,end_vertex);r.r = true;// 判断结点下班是否有效if(r.index_s == -1||r.index_e == -1)continue;// 存入关系addR(graph,r);}return graph;
}/*@brief 打印一个邻接矩阵图@param graph 需要打印的邻接矩阵图指针
*/
void printGraph(Graph *graph)
{if(!graph)return ;std::cout << "\t";// 打印顶点for(int count=0;count < VertexMaxCount;count++)std::cout << graph->V[count] << "\t";std::cout << std::endl;// 打印关系for(int row = 0;row < VertexMaxCount;row++){std::cout << graph->V[row] << "\t";for(int column = 0;column < VertexMaxCount;column++){// 存在关系if(graph->R[row][column])std::cout << "○";elsestd::cout << "×";std::cout << "\t";}std::cout << std::endl;}
}int main()
{Graph *g = creatGraph();printGraph(g);delete g;return 0;
}