数据结构~16.图的基本概念和存储结构

朴灿烈づ我的快乐病毒、 2022-11-27 03:14 234阅读 0赞

# 图的基本概念和存储结构 #

## [本文是上一篇文章的后续,详情点击该链接~][Link 1] ##

## 图的基本概念 ##

### 什么是图? ###

图这个数据结构是由结点的有穷集合V和边的集合E组成。为了和树形结构进行区别,在图结构中常常将结点称为顶点,边是顶点的有序偶对。如果两个顶点之间存在一条边,那么就表示这两个顶点具有相邻关系。

##### 什么是有向图,什么是无向图? #####

通俗的说,就是有方向的叫做有向图,没方向的就叫做无向图。就像我画的这两个图,有箭头的那个就是有方向,没箭头就是没方向...

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDI0Njg4_size_16_color_FFFFFF_t_70_pic_center]

##### 什么是弧? #####

在有向图里面,一般都是把边称为弧。有箭头的那一端,就叫做弧头,另一端就是弧尾。记作< Vi,Vj >。也就是从顶点 Vi 到顶点 Vj 有一条边,那个就是弧。

那么无向图呢?它就等价于在有向图中< Vi,Vj >和< Vj,Vi >两条边。和顶点V相关的边的条数就是顶点的V度。

##### 什么是权?什么是网? #####

在图中的每一条边,都可以有一个对应的数。这种和边相关的数我们就称之为权。权,它可以表示从一个顶点到另一个顶点所花费的代价。边上带有权的图,就称之为带权图,也叫作网

##### 什么是有向完全图和无向完全图? #####

比如说,一个有向图中有n个顶点,那么它就最多只有n(n - 1)条边。也就是,图中的任意两个顶点都有两条边相连。一般具备这种条件的有向图,我们就称之为有向完全图。

那么,什么是无向完全图呢? 比如说,无向图中有n个顶点,那么它就最多只有 n (n - 1) / 2 条边。也就是任意两个顶点之间都有一条边。这种情况下的无向图,我们就称之为无向完全图。

##### 路径和路径长度 #####

在一个图中,路径是相邻顶点序偶所构成的序列。而路径的长度,其实就是指路径上边的数目。就打个比方,我刚才画的那张图 < B , A > < A , D >就是一条路径,长度为2。< A , D > < D , C > < C , B > 也是一条路径,长度是3。而序列中顶点不重复的路径,我们就称为简单路径。当一条路径中的第一个结点和最后一个结点都相同。那么这条路径我们就称为回路。

##### 连通图和连通分量 #####

在无向图中,如果从顶点Vi到顶点Vj有路径,那么我们就称Vi和Vj连通。如果图中任意两个顶点之间都是连通的,那么这个图我们就叫它连通图。不然的话,图中的极大连通子图。就称为连通分量。

而在有向图里面,如果从 Vi 到 Vj 和从 Vj 到 Vi 都有路径,我们就叫他强连通图。不然的话就是极大强连通分量。

--------------------

## 图的存储结构 ##

### 邻接矩阵 ###

邻接矩阵其实就是图的顺序存储结构。通常是由邻接矩阵的行数和列数就可以知道图中的顶点数。

我们可以设G = (V , E)是一个具有 n 个顶点的图。这个顶点的序号呢,就依次为0 , 1 , 2 ... , n - 1。

那么这个方阵,比如说 Array\[ i \] \[ j \] = 1 那么就表示顶点 i 和 顶点 j 邻接。即 i 和 j 之间存在边或者弧。

那么,Array\[ i \]\[ j \] = 0 就表示顶点 i 和 j 不邻接。

对于无向图来说,邻接矩阵是对称的，在矩阵中 1 的个数往往是图中总边数的两倍。而在矩阵中第 i 行或者第 i 列的元素之和就是顶点 i 的度。

那么对于有向图呢,矩阵中 1 的个数也就是图的边数。矩阵中第 i 行的元素之和就是顶点 i 的出度,第 j 列的元素之和,就是顶点 j 的入度。

### 邻接矩阵存储 ###

#####        此图为无权图,矩阵中只有0和1。 0 表示 从顶点 i 到顶点 j 无边存在,1则是有。 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDI0Njg4_size_16_color_FFFFFF_t_70_pic_center 1]

--------------------

### 邻接矩阵结构体定义如下 ###

#define MAXSIZE 100
    typedef struct { 
    	int no;							//顶点编号
    	char info;						//顶点其他信息
    }VertexType;						//顶点类型
    
    typedef struct { 					//图的定义
    	int matrix[MAXSIZE][MAXSIZE];	//矩阵的定义
    	int vertexs;					//顶点数
    	int sides;						//边数
    	VertexType vex[MAXSIZE];		//存放结点的信息
    }Adjacency;							//图的邻接矩阵类型

--------------------

### 邻接表 ###

邻接表是图的一种链式存储结构。所谓邻接表就是对图中的每个顶点 i 都给它建立一个单链表。每个单链表的第一个结点都存放有关顶点的信息,而这个结点,我们就可以看作是链表的表头,其余的结点呢,我们就存放有关边的信息。

所以说,邻接表就是由单链表的表头形成的顶点表和单链表其余结点形成的两表两部分组成。一般来说,顶点表存放顶点信息然后又指向第一个边结点指针。边结点存放与当前顶点相邻接顶点的序号和指向下一个边结点的指针。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDI0Njg4_size_16_color_FFFFFF_t_70_pic_center 2]

--------------------

### 结构体定义 ###

#define MAXSIZE 100
    typedef struct ArcNode { 
    	int arcplace;						//该边所指向的结点的位置
    	struct ArcNode* nextarc;			//下一条边的指针
    	int info;							//该边相关信息
    }Arc;
    
    typedef struct { 
    	char data;							//顶点信息
    	Arc* firstarc;						//指向第一条边的指针
    }Vertex;
    
    typedef struct { 
    	Vertex adjacencyList[MAXSIZE];		//邻接表
    	int vertexs;						//顶点数
    	int sides;							//边数
    }Graph;									//图的邻接表类型

[Link 1]: https://blog.csdn.net/qq_41424688/article/details/107957236
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDI0Njg4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/b8427cf2c18c43ac8b212f0927892dd9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDI0Njg4_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/b76407b9802343c68616c1f18fcd8e66.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDI0Njg4_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/109253af6838475d8623b045b8528cff.png