邻接表问题

算法

相关的介绍

描述

图的邻接矩阵存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。如词条概念图所示，表结点存放的是邻接顶点在数组中的索引。对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点，在无向图内会成环。

实际的意义

邻接表是图的一种最主要存储结构,用来描述图上的每一个点。对图的每个顶点建立一个容器（n个顶点建立n个容器），第i个容器中的结点包含顶点Vi的所有邻接顶点。实际上我们常用的邻接矩阵就是一种未离散化每个点的边集的邻接表。

有向图中

在有向图中，描述每个点向别的节点连的边（点a->点b这种情况）。

无向图中

在无向图中，描述每个点所有的边(点a-点b这种情况)无方向

表示法

n个顶点e条边的无向图的邻接表表示中有n个顶点表结点和2e个边表结点。(换句话说，每条边（i,j）在邻接表 中出现两次：一次在关于i的邻接表中，另一次在关于j的邻接表中)

总结

先祖节点是哪一个点，则该点都直接与之相连。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#define  MaxVertexNum 100  
  
typedef char VertexType;  
typedef struct node   //边表节点  
{  
   int adjvex;  
   node* next;  
}EdgeNode;  
  
typedef struct     //顶点表节点  
{  
   VertexType vertex;  
   EdgeNode* firstedge;  
}VertexNode;  
  
typedef VertexNode AdjList[MaxVertexNum];  
  
typedef struct   
{   
    AdjList adjlist;  
    int n,e;  
  
}ALGraph;

友情链接

http://blog.csdn.net/linxinyuluo/article/details/6847851