邻接矩阵和邻接表

清醒疯子 2018-05-04

图有两种主要的表示方法:邻接矩阵和邻接表。

决定我们采用邻接矩阵还是采用邻接表来表示图,需要判断一个图是稀疏图还是稠密图。邻接矩阵和邻接表表示图所需的存贮空间和算法时间度相差非常大,所以判断一个图是稀疏的还是稠密的非常重要。

判断标准如下:

假设一个图G=(V,E)有n个节点,图G的每个节点的出度是一个固定的常数:k。由于E=kV=O(V) ,所以我们把符合E=O(V) 条件的图称为稀疏图。

同理 :

如果一个图G=(V,E)有n个节点,假设图G的每个节点的出度是关于n的一个小数,并且0<f<=1,我们把符合E=fV2(平方)=V2(平方)条件的图称为稠密图。

比如:一个图节点为16,节点的出度为4,那么f = 0.25。

邻接矩阵

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

邻接矩阵是对称矩阵

有了这个二维数组组成的对称矩阵,我们就可以很容易的知道图中的信息:

- 要判定任意两顶点是否有边无边就非常容易了;

-要知道某个顶点的度,其实就是这个顶点Vi在邻接矩阵中第i行(或第i列)的元素之和;

-求顶点Vi的所有邻接点就是将矩阵中的第i行元素扫描一遍,A[i][j]是1的就是邻接点咯;

有向图的邻接矩阵中要分方向,所以每个位置上都是行指向列比如A[1][2]就是下标为1的顶点指向下标为2的顶点而A[2][1]就是下标为2的顶点指向下标为1的顶点。

有向图要考虑出度和入度,顶点V1的入度为V1列的各数之和,顶点V1的出度为V2列的各数之和。

/* 图的邻接矩阵表示法(C语言实现) */
#define MaxVertexNum 100  /* 最大顶点数设为100 */
#define INFINITY 65535  /* ∞设为双字节无符号整数的最大值65535*/
typedef char VertexType; /* 顶点类型设为字符型 */
typedef int EdgeType; /* 边的权值设为整型 */
enum GraphType { DG, UG, DN, UN };
/* 有向图,无向图,有向网图,无向网图*/
 
typedef struct {
  VertexType Vertices[ MaxVertexNum ]; /* 顶点表 */
  EdgeType Edges[ MaxVertexNum ][ MaxVertexNum ];
  /* 邻接矩阵,即边表 */<br />  int n, e; /* 顶点数n和边数e */<br />  enum GraphType GType; /* 图的类型分4种:UG、DG、UN、DN */
} MGraph; /* MGragh是以邻接矩阵存储的图类型 */
 
void CreateMGraph ( MGraph *G )
{
  int i, j, k, w;
  G-> GType = UN; /* Undirected Network 无向网图 */
  printf( "请输入顶点数和边数(输入格式为:顶点数, 边数):\n" );
  scanf( "%d, %d",&(G->n), &(G->e) ); /* 输入顶点数和边数 */
  printf("请输入顶点信息(输入格式为:顶点号<CR>):\n");
  for ( i = ; i < G->n; i++ )
     scanf( "%c",&(G-> Vertices[i]) ); /* 输入顶点信息,建立顶点表 */
  for ( i = ; i < G->n; i++ )
    for ( j = ; j < G->n; j++ )
      G->Edges[i][j] = INFINITY; /* 初始化邻接矩阵 */
  printf( "请输入每条边对应的两个顶点的序号和权值,输入格式为:i, j, w:\n" );
  for ( k = ; k < G->e; k++ ) {
    scanf("%d,%d,%d ",&i, &j, &w); /* 输入e条边上的权,建立邻接矩阵 */
    G->Edges[i][j] = w;
    G->Edges[j][i] = w; /* 因为无向网图的邻接矩阵是对称的 */
  }
}

邻接表

邻接表是图的标准方法

具体方法:

先用一个指针数组表示每一个顶点,指针后面有一个链表,表示有指针表示的顶点的邻接顶点。

/* 图的邻接表表示法(C语言实现) */
#define  MaxVertexNum  100     /* 最大顶点数为100 */
enum GraphType { DG, UG, DN, UN }; 
/* 有向图,无向图,有向网图,无向网图*/
typedef  struct  node{   /* 边表结点 */
    int AdjV;            /* 邻接点域 */
    struct  node  *Next;  /* 指向下一个邻接点的指针域 */
    /* 若要表示边上的权值信息,则应增加一个数据域Weight */
} EdgeNode;
typedef  char  VertexType;   /* 顶点用字符表示 */
typedef  struct  Vnode{      /* 顶点表结点 */
    VertexType  Vertex;      /* 顶点域 */
    EdgeNode  *FirstEdge; /* 边表头指针 */
} VertexNode; 
typedef VertexNode AdjList[ MaxVertexNum ]; /* AdjList是邻接表类型 */
typedef  struct{  
    AdjList  adjlist;    /* 邻接表 */
    int  n, e;               /* 顶点数和边数 */
    enum GraphType GType;    /* 图的类型分4种:UG、DG、UN、DN */
} ALGraph;  /*ALGraph是以邻接表方式存储的图类型 */
  
void CreateALGraph( ALGraph *G )
{
    int i, j, k;
    EdgeNode *edge;
    G-> GType = DG;  /* Directed Graph  有向图  */
    printf( "请输入顶点数和边数(输入格式为:顶点数,边数):\n" );
    scanf( "%d,%d", &(G->n), &(G->e) ); /* 读入顶点数和边数 */ 
    printf( "请输入顶点信息(输入格式为:顶点号<CR>):\n" );
    for ( i=; i < G->n; i++ ) {   /* 建立有n个顶点的顶点表 */
        scanf( " %c", &(G->adjlist[i].Vertex) );  /* 读入顶点信息 */
       G->adjlist[i].FirstEdge = NULL; /* 顶点的边表头指针设为空 */
    }
    printf( "请输入边的信息(输入格式为: i, j <CR>):\n" );
    for ( k=; k < G->e; k++ ){   /* 建立边表 */
       scanf( "\n%d,%d", &i, &j); /* 读入边<vi,vj>的顶点对应序号*/
       edge = (EdgeNode*)malloc(sizeof(EdgeNode)); /* 生成新边结点edge */
       edge->AdjV = j; /* 邻接点序号为j */
       edge->Next = G->adjlist[i].FirstEdge;
       /* 将新边表结点edge插入到顶点vi的边表头部 */
       G->adjlist[i].FirstEdge = edge;
       /* 若是无向图,还要生成一个结点,用来表示边< vj, vi>  */
    }
}