1 邻接矩阵
图的邻接矩阵表示属于图的顺序存储结构。邻接矩阵可以唯一地表示图。
用一个一维数组存放顶点信息，一个二维数组（矩阵）存放顶点间的相邻关系。
1.1 有向图和无向图的邻接矩阵
下面的有向图与无向图对应的矩阵分别是A和B：
1.2 网络（带权图）及邻接矩阵：
邻接矩阵的C语言描述：
# 100 //将最大顶点数高为100
char ;
int ;
vex[]; //顶点表
edges[][]; //邻接矩阵，即边表
int n,e; //顶点数和边数
} ; //是以邻接矩阵存储的图类型
2 邻接表
2.1 无向图邻接表
邻接表（ List）是图的一种顺序存储与链式存储相结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表，再将所有顶点的领接表表头放到数组中，就构成了图的邻接表。
邻接表把邻接矩阵的n行改为n个单链表，把同一个顶点发出的边链接在同一个称为边链表（出边表）的单链表中，单链表的每一个结点代表一条边，叫做边结点，结点中保存有与边相关联的另一顶点的顶点下标dest和指向同一链表中下一边结点的指针link。
由上图可见，相对于邻接矩阵的边关系会存储n*n个元素信息（如果是n个顶点的话），而邻接表则会小于n*n个信息，也就是会忽略掉顶点无连接（边）的信息。
邻接表由于各边链入边链表的顺序可以不同，所以不能唯一地表示图；
在邻接表中，统计某顶点i的出边表所含结点的个数，即可得到该顶点的出度；
在邻接表表示中有两种结点结构：
顶点表由顶点域和指向第一条 邻接边的指针域构成。
边表（邻接表）由邻接结点域和指向下一条邻接边的指针域构成。
如下图所示：
对于网，其边表需再增设一个存储边上信息（如权值）的域（info），如下图所示：
图的邻接表的存储表示可以用C语言描述如下：
# 100 //最大顶点数
node //边表结点
int ; //邻接点域
node *next; //指向下一个邻接点的指针域
} ; //若要表示边上信息，则应增加一个数据域info
vnode //顶点表结点
; //顶点域，顶点的名字
*; //边表头指针
} ;
[]; //是邻接表类型
; //邻接表
int n,e; //顶点数和边数
} ; //是以邻接表方式存储的图类型
2.2 有向图邻接表
在无向图的邻接表中，顶点vi的度恰为第i个链表中的结点数；在有向图中，第i个链表中的结点个数只是顶点vi的出度，有时，为了便于确定顶点的入度，可以建立一个有向图的逆邻接表，如下图所示：
3 无向图的邻接多重表
图的每一条边用一个边结点表示，这个边结点由5个域组成，如下图所示：
mark：标记域，标记该边是否已处理；
, ：顶点域，指明该边的两个顶点的顶点域；
link1, link2：链接指针，指向与和关联的下一条边。
还可以设置一个域cost存放该边的权值；
存储顶点信息的顶点表以一维数组方式组织，每个顶点有两个域，如上图所示。
data：存入顶点信息；
：指针域，指向该顶点所关联的第一条边；
在邻接多重链表中，依附于同一个顶点的所有边都链接在同一单链表中。只要从顶点i出发，即可循链找出依附于该顶点的所有边（以及它的所有邻接顶点）。
无向图的邻接多重表的数据结构用C语言定义如下：
…(参照邻接矩阵存储表示)
Enode //边结点定义
int mark; //边的访问标记
cost; //边上的权值
int ,; //边的两个端点的顶点号
Enode *link1, *link2; //边链表中下一条边指针
};
Vnode //顶点的定义
Type data; //顶点的数据
Enode *; //边链表的头指针
};
{
[];
int , ; //图中实际顶点个数和边的条数
} ;
4 有向图的十字链表
合并有向图的邻接表和逆邻接表，就可以得到有向图的十字链表表示。
在有向图的十字链表中，每个边结点也有5个域，如下图所示：
－End－
———END———
限 时 特 惠： 本站每日持续更新海量各大内部创业教程，永久会员只需109元，全站资源免费下载 点击查看详情
站 长 微 信： nanadh666
