当前位置:   article > 正文

数据结构图论入门_无向连通图

无向连通图

图论基本知识

  图(Graph)可以简单表示为二元组G=<V,E>,其中V称为顶点(vertex)集合,E称为边(edge)的集合。图可分为以下几种类型

  • 1.有向图:E中的每一条边都具有方向的图。
    有向图
  • 2.无向图:E中每一条边不带方向,称为无向图。
    无向图
  • 3.混合图:E中一些边不带方向,另一些边带有方向。
    混合图
  • 4.多重图:含有平行边或自环的图。(有向图、无向图和混合图都属于简单图)
    在这里插入图片描述
  • 5.边的表示方法
  • 无向图的边叫无向边,用无序偶表示, ( v i , v j ) (v_i,v_j) (vi,vj)表示 i i i结点与 j j j结点之间的边,因为没有方向,所以 ( v i , v j ) ⇔ ( v j , v i ) (v_i,v_j)\Leftrightarrow(v_j,v_i) (vi,vj)(vj,vi)
  • 有向图的边叫有向边,用有序偶表示, &lt; v i , v j &gt; &lt;v_i,v_j&gt; <vi,vj>表示从 i i i指向 j j j的边或弧, v i v_i vi称为始点, v j v_j vj称为终端点, ( v i , v j ) ⇎ ( v j , v i ) (v_i,v_j)\nLeftrightarrow(v_j,v_i) (vi,vj)(vj,vi),称 v i v_i vi邻接 v j v_j vj, v j v_j vj邻接 v i v_i vi
  • 5.顶点的度
  • 无向图:无向图的度为与该顶点相关联的边的数目,各顶点的度数和等于边的数目的两倍。定义图中顶点数目为图的,若一个无向图中,每个顶点的度均为 n − 1 n-1 n1,称该图为 n n n阶无向完全图,其边的总数为 C n 2 = n ( n − 1 ) 2 C_n^2=\frac {n(n-1)}{2} Cn2=2n(n1)
  • 有向图:有向图的度分入度和出度,入度指终端点指向该点的弧的数目,出度指以该点为始点的弧的数目。若 n n n阶有向图每个顶点的入度等于出度等于 n − 1 n-1 n1,称该图为有向完全图,其弧的数目为 n ( n − 1 ) n(n-1) n(n1)
  • 6.图的连通性
  • 无向图:若从顶点 v i v_i vi到顶点 v j v_j vj有路径,则称 v i v_i vi v j v_j vj是连通的。若该图中任意两个顶点都是连通的,则称该图是连通图。
  • 有向图:在有向图中,略去所有边的方向形成的无向图如果是连通图,则该有向图是弱连通图,若在方向约束下,有向图中任意两个顶点互相可达,则称该有向图为强连通图。注:图的强弱连通只针对有向图。弱连通图可以理解为该图只是在表面上看起来有些“线”将顶点都连接了起来,但是由于有方向,该图并不能实现任意两个点互相可达。
  • 连通分量:无向图中,顶点之间的连通关系是一个等价关系,该等价关系将顶点集合划分的等价类成为连通分支即连通分量,这些等价类的数目称为连通分支数。可以这样理解,同一个连通分支中的所有顶点可以互相到达,任意两个连通分支中的两个顶点不能互相到达。
  • 7.生成树
  • 生成树:一个 n n n阶连通图的生成树是一个极小连通子图(包含最少的边的连通图),生成树包含 n n n个顶点, n − 1 n-1 n1条边,显然,一个连通图的生成树可能不唯一,其中所有边权值和最小的生成树称为最小生成树。在生成树中添加任意一条边,必然形成回路。
  • 最小生成树求解算法:Prim算法、Kluskal算法
  • 8.图的存储结构
    邻接矩阵
    邻接矩阵:用一个矩阵存储顶点之间是否直接有边相连,对于n阶图,设n阶方阵 a i j a_{ij} aij为该图的邻接矩阵,则
    a i j = { 1 , v i 邻 接 至 v j 0 , v i 不 邻 接 v j a_{ij}=\left\{
    1,vivj0,vivj
    \right.
    aij={1,vivj0,vivj

    例如如下无向图
    在这里插入图片描述

邻接矩阵为
A = [ 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0 ] A= \left[ 0amp;1amp;0amp;1amp;01amp;0amp;1amp;0amp;10amp;1amp;0amp;1amp;11amp;0amp;1amp;0amp;00amp;1amp;1amp;0amp;0 \right] A=0101010101010111010001100

邻接矩阵代码实现

#define MAX //最大顶点数
typedef struct
{
	int n;//n为实际顶点数
	ElemTp a[MAX][MAX];//邻接矩阵
	//这里的ElemTp为可选数据类型,若只是简单图,即没有边权值
	//则a[i][j]=1表示i和j之间有边存在,为0表示无边存在
	//其他图的邻接矩阵元素可以存储i到j的边权值,等
}Graph;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

邻接表
  使用链表对邻接矩阵进行改进,每个顶点只保存所有直接与它相连的顶点,所有这些顶点通过链表来动态保存。那么对于 n n n阶无向图,需要 n n n个头结点,每个结点后链接直接与其相连的顶点。例如图:
在这里插入图片描述
(1)首先可以看到,与0结点直接相连的有1,3,那么把1,3号结点插入到0结点的头结点后面去(1,3的顺序是任意的,后面所有表结点皆是,表结点之间的链接不表示任何关系,只关心该结点链接在哪个头结点之后)
(2)然后按此方法可以发现1后面有0,2,4;2后面有1,3,4;3后面有0,2;4后面有1,2;建立邻接表如下所示
邻接表
邻接表代码实现

//头结点
typedef struct
{
	//顶点数据(可选)
	ElemTp data;
	InfoTp info;//顶点信息,可选
	int i;//顶点下标
	ArcNode *firstarc;//第一邻接的表结点
}HNode;

//表结点
typedef struct node
{
	double w;//边或弧的权重,可选
	InfoTp info;//边或弧的信息,可选
	int j;//邻接点的下标
	struct node *nextarc;//下一表结点
}ArcNode;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/空白诗007/article/detail/891176
推荐阅读
相关标签
  

闽ICP备14008679号