图的存储结构

目录

• 图的存储结构
  • 邻接矩阵
  • 邻接表

图的存储结构

邻接矩阵

邻接矩阵(Adjacency Matrix)是表示顶点之间相邻关系的矩阵。

用邻接矩阵表示法表示图，除了一个用千存储邻接矩阵的二维数组外， 还需要用一个一维数 组来存储顶点信息。 其形式说明如下：

//-----图的邻接矩阵存储表示－－－－－
#define Maxint 32767      //表示极大值
#define MVNum 100         //最大顶点数
typedef char VerTexType;  //假设顶点的数据类型为字符型
typedef int ArcType;
typedef struct
{
  VerTexType vexs [MVNum] ;     //顶点表
  ArcType arcs[MVNum] [MVNum];  //邻接矩阵
  int vexnum,arcnum;            //图的当前点数和边数
                     }AMGraph; 

采用邻接矩阵表示法创建无向网

【算法步骤】

1. 输入总顶点数和总边数。
2. 依次输入点的信息存入顶点表中。
3. 初始化邻接矩阵，使每个权值初始化为极大值。
4. 构造邻接矩阵。依次输入每条边依附的顶点和其权值，确定两个顶点在图中的位置之后， 使相应边赋予相应的权值，同时使其对称边赋予相同的权值。

【算法描述】

Status CreateUDN(AMGraph &G) 
{//采用邻接矩阵表示法，创建无向网G
  cin>>G.vexnum>>G.arcnum; 
  for(i=O;i<G.vexnum;++i) 
     cin>>G.vexs[i); 
  for(i=O;i<G.vexnum;++习
     for (j =0; j <G. vexnum; ++j) 
         G.arcs[i) [j)=Maxint;
  for(k=O;k<G.arcnum;++k) 
   {
       cin>>vl>>v2>>w;
       i=LocateVex(G,vl);j=LocateVex(G,v2); //确定vl和v2在G中的位置，即顶点数组的下标
       G.arcs[i][j]=w; //边<vl, v2>的权值置为w
       G.arcs[j] [i]=G.arcs[i][j];
   }
   return OK; 
                    }

邻接矩阵表示法的优缺点

(1)优点 ：便于判断两个顶点之间是否有边， 即根据A[i] [j]= 0或1来判断； 便于计算各个顶点的度。

(2) 缺点：不便于增加和删除顶点；不便于统计边的数目，需要扫描邻接矩阵所有元素才能统计完毕；空间复杂度高。

邻接表

邻接表(Adjacency List) 是图的一种链式存储结构。在邻接表中，对图中每个顶点Vi建立一个单链表，把与 Vi相邻接的顶点放在这个链表中。邻接表中每个单链表的第一个结点存放有关顶点的信息， 把这一结点看成链表的表头， 其余结点存放有关边的信息， 这样邻接表便由两部分组成：表头结点表和边表。

(1) 表头结点表：由所有表头结点以顺序结构的形式存储， 以便可以随机访问任一顶点的边链表。表头结点包括数据域 (data) 和链域 (firstarc) 两部分

(2)边表：由表示图中顶点间关系的 2n个边链表组成。 边链表中边结点包括邻接点域 (adjvex)、数据域 (info) 和链域 (nextarc) 三部分

邻接表存储结构说明如下：

//- - - - -图的邻接表存储表示－ －－－－
#define MVNum 100           //最大顶点数
typedef struct ArcNode      //边结点
{ 
   int adjvex;              //该边所指向的顶点的位置
   struct ArcNode * nextarc; //指向下一条边的指针
   Otherinfo info;           //和边相关的信息
}ArcNode; 
typedef struct VNode         //顶点信息
{ 
   VerTexType data;          //指向第一条依附该顶点的边的指针
 ArcNode *firstarc; 
}VNode,AdjList[MVNum]; 
typedef struct 
{
  AdjList vertices; 
  int vexnum,arcnum; 
}ALGraph;

邻接表表示法的优缺点

(1) 优点：

便于增加和删除顶点；

便于统计边的数目， 按顶点表顺序扫描 所有边表可得到边的数目，时间复杂度为 O(n + e) ；

空间效率高。对于一个具有n个顶点e条边的图 G, 若 G 是无向图，则在其邻接表表示 中有 n 个顶点表结点和 2e 个边表结点；若 G 是有向图，则在它的邻接表表示或逆邻接表表示中均有 n 个顶点表结点和e个边表结点。

(2)缺点 ：

不便于判断顶点之间是否有边，要判定 Vi和vj之间是否有边，就需扫描第i个边表，最坏情况下要耗费 O(n)时间；

不便于计算有向图各个顶点的度。

推荐这些文章：

35.图

1.定义变量
private ArrayList<String> vertexList; //存储顶点集合
private int[][] edges; //存储图对应的邻结矩阵
private int numOfEdges; //表示边的数目
//定义给数组boolean[], 记录某个结点是否被访问
private boolean[] isVisited;
 
2.构造器
public Graph(int n) {
//初始化矩阵和vertexList
edges = new int[n][n];
vertexList = new ArrayLis...

数据结构---图的定义和存储结构

目录图的定义和基本术语基本术语图的类型定义图的存储结构1.邻接矩阵表示法无向图的邻接矩阵有向图的邻接矩阵图的邻接矩阵存储表示创建无向网创建无向图创建有向网创建有向图邻接矩阵优缺点：优点缺点2.邻接表表头结点表：边表：图的邻接表的存储表示创建无向图创建有向图创建有向/无向网邻接表表示法的优缺点优点：缺点：邻接矩阵和邻接表表示法的关系区别：3.十字链表十字链表的存储表示4.邻接多重表邻接多重表存储表示
图的定义和基本术语
图(Graph) G由两个集合V和E组成，记为G=(V,E) , 其中V是顶点的有穷非空集合，E是V中顶点偶对的有穷集合，这些顶点偶对称为边。其中点不能为空，边可以为空。
无向...

数据机构之图

一、图的概念

通常图表示为偶对，是顶点和边的集合
G = (V,E)V:顶点(数据元素)的又穷非空集合G:边的又穷集合

1.图的分类
1.通常根据边有无方向分为：又向图和无向图。
2.根据任意两个顶点之间是否有边相连称为：完全图其中：无向完全图中  n个顶点有 n(n-1)/2 条边          有向完全图中  n个顶点有 n(n-1) 条边
3.稀疏图：有很少边或弧的图（e<n logn）   稠密图：有较多边或弧的图   网：边/弧带权的图   ...

有向图的十字链表储存及相关算法

# include<iostream># include<stdlib.h># include<queue># include<cstring>using namespace std;const int N = 10050;typedef struct Arcbox{ int tailvex,headvex;//弧尾和弧头的 位置（方向是弧尾能走到弧头） struct Arcbox *hlink,*tlink;//相同弧头，相同弧尾的弧的链
}Arcbox;//存储边的信息
typedef struct{ 　　int data;//数据域...