Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3882020
  • 博文数量: 408
  • 博客积分: 10227
  • 博客等级: 上将
  • 技术积分: 9820
  • 用 户 组: 普通用户
  • 注册时间: 2009-04-17 21:48
个人简介

非淡泊无以明志,非宁静无以致远

文章存档

2022年(1)

2021年(1)

2020年(2)

2019年(5)

2018年(4)

2017年(3)

2016年(24)

2015年(8)

2014年(7)

2013年(3)

2012年(1)

2011年(23)

2010年(179)

2009年(147)

分类: C/C++

2010-06-01 21:15:16

1.图的邻接矩阵

1)定义:

在图的邻接矩阵表示法中:

 ① 用邻接矩阵表示顶点间的相邻关系

 ② 用一个顺序表来存储顶点信息

G=(VE)是具有n个顶点的图,则G的邻接矩阵是具有如下性质的n阶方阵:A[i,j]=1,if (vi,vj)EG)中的边

  A[i,j]=0,if (vi,vj)不是EG)中的边

      

2)从图的邻接矩阵表示法中可以得到如下结论:

1)对于n个顶点的无向图,有Aii=01in

2)无向图的邻接矩阵是对称的,即Aij=Aji),1in1jn

3)有向图的邻接矩阵不一定对称的。因此用邻接矩阵来表示一个具有n个顶点的有向图时需要n的平方个单位来存储邻接矩阵;对有n个顶点的无向图则需存入上(下)三角形,故只需nn+1/2个单位。

4)无向图的邻接矩阵的第i行(或第i列)非零元素的个数正好是第i个顶点的度TDvi)。

5)有向图的邻接矩阵的第i行(或第i列)非零元素的个数正好是第i个顶点的出度ODvi[或入度IDvi]

 

3 网(带权值的图)的邻接矩阵

G是网络,则邻接矩阵可定义为:

  A[I,j]=Wij           if (Vi,Vj)E(G)中的边

  A[I,j]=0或是无穷大  if (Vi,Vj)不是E(G)中的边

  其中:

      wij表示边上的权值;

      ∞表示一个计算机允许的、大于所有边上权值的数。

4)邻接矩阵的图类

const int MaxVertices=10;

const int MaxWeight=32767;

class AdjMWGraph

  {

private:

   int Vertices[10];           //顶点信息的数组

   int Edge[MaxVertices][MaxVertices];         //边的权值信息的矩阵

    int numE;            //当前的边数

    int numV;            //当前的顶点数

    public: ………;          //公有函数

    private: ………;          //私有函数

  }

  注意:

 ① 在简单应用中,可直接用二维数组作为图的邻接矩阵(顶点表及顶点数等均可省略)。

  当邻接矩阵中的元素仅表示相应的边是否存在时,EdgeTyPe可定义为值为01的枚举类型。

  无向图的邻接矩阵是对称矩阵,对规模特大的邻接矩阵可压缩存储。

  邻接矩阵表示法的空间复杂度S(n)=0(n2)

2.图的邻接链表
     邻接链表(Adjacency List)是图的一种链式存储结构,与树型结构中的孩子链表相似。通常邻接链表也称邻接表。
1 邻接表的结点结构
边结点结构

data   adjvex

邻接表中每个表结点均有两个域:
  邻接点域adjvex
  存放与vi相邻接的顶点vj的序号j
  链域next
  将邻接表的所有表结点链在一起。
 
注意:

     如果带权图,则在表结点中还应增加一个保存权值等相关信息info

dest  weight   next

2) 邻接表的表示

     对于无向图,vi的邻接表中每个表结点都对应于与vi相关联的一条边。因此,将邻接表的表头向量称为顶点表。将无向图的邻接表称为边表。
 
注意:

    n个顶点e条边的无向图的邻接表表示中有n个顶点表结点和2e个边表结点。
   
对于有向图,vi的邻接表中每个表结点都对应于以vi为始点射出的一条边。因此,将有向图的邻接表称为出边表。
  注意:

    n个顶点e条边的有向图,它的邻接表表示中有n个顶点表结点和e个边表结点。

3) 有向图的逆邻接表
        
在有向图中,为图中每个顶点vi建立一个入边表的方法称逆邻接表表示法。入边表中的每个表结点均对应一条以vi为终点(即射入vi)的边。

阅读(2820) | 评论(0) | 转发(1) |
0

上一篇:linux超级服务器inetd详解

下一篇:图的遍历

给主人留下些什么吧!~~