0
16

图在数据结构中是多对多的关系,一个顶点可以和多个顶点有联系。其通常表示为:G(V,E),其中G表示一个图,V表示图的顶点集合,E表示图的边集合。

1.图的定义

有向图:

图中任意两个顶点间的边都是有向边,则称该图为有向图。连接两个顶点间的有向边称为弧,弧起点称为弧头,终点称为弧尾,表示方法为<A,B>A为弧尾,B为弧头。

如果图中任意两个顶点间都存在互为来往的有向边,则称该图为有向完全图。有向完全图的边长总数为\(n*(n-1)\),其中n是顶点个数。

有向图顶点的度和弧的关系:\(e=\sum_{i=1}^{n}ID(v_i)=\sum_{i=1}^{n}OD(v_i)\)。其中e是图的边长总数,n为图的顶点总数,\(ID(v_i)\)是顶点的入度,\(OD(v_i)\)是顶点的出度。

无向图:

图中任意两个顶点间的边都是无向的,则称该图为无向图。无向边表示方法为(A,B)

如果图中任意两个顶点间都存在无向边,则称该图为无向完全图。无向完全图的边长总数是\(n*(n-1)/2\),其中n是顶点个数。

无向图顶点的度和边长的关系:\(e=\frac{1}{2}\sum_{i=1}^{n}TD(v_i)\)。其中\(TD(v_i)\)是顶点\(v_i\)的度,e是图的边长总数,n为图的顶点总数。

网:

边或弧带权的图称为网。

2.图的存储结构

邻接矩阵:

图的邻接矩阵存储方式是将图的顶点和图的边或弧分开存储,将图的顶点存入到一个一维数组,图的边或弧存储到二维数组。

邻接矩阵是一个\(n*n\)的方阵,表示方法如下:

\(arc[i][j]=\left\{\begin{array}{}1,若(v_i,v_j)\in\textbf{E}或<v_i,v_j>\in\textbf{E}, \\ 0,反之\end{array}\right.\)

定义数据结构为:

const int MAXVEX=100;//顶点的最大个数
template<class VertexType,class EdgeType>
class MGraph
{
//成员数据私有化
private:
    VertexType vexs[MAXVEX];	//顶点表
    EdgeType arc[MAXVEX][MAXVEX];//邻接矩阵
    int numVertexs,numEdges;
};

构造一个图:

void Creat

<

发布回复

请输入评论!
请输入你的名字