图的邻接矩阵表示法的特点是什么（图的邻接矩阵 Feel之家 ITeye技术网站）

1．图的邻接矩阵表示法

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

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

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

2．图的邻接矩阵(Adacency Matrix)

　设G=(V    
    
    
    ，E)是具有n个顶点的图  


     


     


     


，则G的邻接矩阵是具有如下性质的n阶方阵：

【例】下图中无向图G5

和有向图G6

的邻接矩阵分别为Al

和A2

 
    
    
    
。

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

（1）对于n个顶点的无向图


 




 




 




，有A（i   

   

   

   ，i）=0   

     

     

     

，1≤i≤n
     


     


     


    。

（2）无向图的邻接矩阵是对称的



  




  




  




，即A（i  


  


  


  ，j）=A（j    
     
     
     
，i）




   




   




   




，1≤i≤n 



 



 



 ，1≤j≤n 




 




 




 


。

（3）有向图的邻接矩阵不一定对称的 

   

   

   

。因此用邻接矩阵来表示一个具有n个顶点的有向图时需要n2

个单位来存储邻接矩阵；对有n个顶点的无向图则需存入上（下）三角形                    ，故只需n（n+1）/2个单位
     

     

     

   。

（4）无向图的邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度TD（vi

）  




  




  




  

。

（5）有向图的邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的出度OD（vi

）[或入度ID（vi

）] 


  


  


  


。

3．网（带权值的图）的邻接矩阵

　若G是网络




    




    




    




，则邻接矩阵可定义为：

其中：

wij

表示边上的权值；

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

【例】下面(a)是一个带权图















，（b）是对应的邻接矩阵的存储结构

（a）带权图 （b）邻接矩阵

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可定义为值为0和1的枚举类型 



 



 



 



。

　③ 无向图的邻接矩阵是对称矩阵
















，对规模特大的邻接矩阵可压缩存储                。

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

)
    




    




    




    。

声明：本站所有文章    
    
    
    ，如无特殊说明或标注  


     


     


     


，均为本站原创发布



















。任何个人或组织


 




 




 




，在未征得本站同意时   

   

   

   ，禁止复制
     


     


     


    、盗用 




 




 




 


、采集 

   

   

   

、发布本站内容到任何网站
     

     

     

   、书籍等各类媒体平台                。如若本站内容侵犯了原著者的合法权益   

     

     

     

，可联系我们进行处理
     



     



     



     。