邻接矩阵
邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn} [1] 。G的邻接矩阵是一个具有下列性质的n阶方阵：
①对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零（在此仅讨论无向简单图），副对角线不一定为0，有向图则不一定如此。
②在无向图中，任一顶点i的度为第i列（或第i行）所有非零元素的个数，在有向图中顶点i的出度为第i行所有非零元素的个数，而入度为第i列所有非零元素的个数。
③用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n（n-1）/2个空间。
用一个一维数组存放顶点集合，一个二维数组存放边的信息（称为邻接矩阵），边可以是带权值的，也可以是 不带权值的这里用的是带权值的。此外一个邻接表可以存放有向图，也可以存放无向图，在这里是无向图，无向图一定是对称矩阵，这一点在代码中也有体现。它适合用来存放稠密图。对于下列的创建算法，n个顶点和e条边的无向网图，时间复杂度为O(n + n^2 + e) 其中邻接矩阵G.arc的初始化耗费了O(n^2) (两层的嵌套循环)
#include <stdio.h>
#define MAXVEX 100 /*最多顶点数量*/
#define INFINITY 65535 /*定义的个极大值*/
typedef char VertexType; /*顶点的类型*/
typedef int EdgeType; /*边的类型*/
typedef struct {
VertexType vexs[MAXVEX]; /*一维数组存放顶点表*/
EdgeType arc[MAXVEX][MAXVEX]; /*二维数组存放边表*/
int numVertexes, numEdges; /*当前的顶点数和边数*/
}MGraph;
void CreateMGraph(MGraph * G){
int i, j, k, w;
printf("请输入顶点数和边数:\n");
scanf("%d %d", &G->numVertexes, &G->numEdges);
printf("请输入各顶点的名字：\n");
for(i = 0; i < G->numVertexes; i++){
scanf("%c", &G->vexs[i]);
}
/*初始化邻接矩阵*/
for(i = 0; i < G->numVertexes; i++){
for(j = 0; j < G->numVertexes; j++){
G->arc[i][j] = INFINITY;
}
}
for(k = 0; k < G->numEdges; k++){
printf("请输入边对应的下标i 下标j 以及权值w:\n");
scanf("%d %d %d", &i, &j, &w);
G->arc[i][j] = w;
G->arc[j][i] = G->arc[i][j]; /*无向图，保证矩阵对称*/
}
}
邻接表
图的邻接表存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。
顶点用一个一维数组存储，对于顶点数组每一个数据元素还需要存储指向第一个邻接点的指针，以便查询该结点的边信息。邻接表适合用于稀疏他图。
对应下列的创建算法一个n个顶点e条边的无向网图，其时间复杂度为O(n + e)
#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 100 /*最多顶点数量*/
#define INFINITY 65535 /*定义的个极大值*/
typedef char VertexType; /*顶点的类型*/
typedef int EdgeType; /*边的类型*/
/*边表结点*/
typedef struct EdgeNode {
int adjvex; /*邻接点域*/
EdgeType weight; /*权值*/
EdgeNode * next;
}EdgeNode;
/*顶点表结点*/
typedef struct VextexNode {
VertexType data;
EdgeNode * firstEdge; /*指向第一个临界点*/
}VertexNode, AdjList[MAXVEX];
typedef struct {
AdjList adjList;
int numVertexes, numEdges;
}GraphAdjList;
void CreateALGraph(GraphAdjList * G){
int i, j, k, w;
EdgeNode * e;
printf("请输入顶点数和边:\n");
scanf("%d %d", &G->numVertexes, &G->numEdges);
/*读入顶点信息，建立顶点表*/
for(i = 0; i < G->numVertexes; i++){
scanf("%c", &G->adjList[i].data);
G->adjList[i].firstEdge = NULL;
}
/*建立边表*/
for(k = 0; k < G->numEdges; k++){
printf("请输入边(vi,vj)对应的序号i,j以及权值w\n");
scanf("%d %d %d", &i, &j, &w);
e = (EdgeNode*) malloc(sizeof(EdgeNode));
e->adjvex = j;
e->weight = w;
e->next = G->adjList[i].firstEdge; /*单链表的头插法*/
G->adjList[i].firstEdge = e;
/*由于我们这里建立的是一个无向图，所以它必须是对称的，所以接下来对i进行相反的操作*/
e = (EdgeNode*) malloc(sizeof(EdgeNode));
e->adjvex = i;
e->weight = w;
e->next = G->adjList[j].firstEdge;
G->adjList[j].firstEdge = e;
}
}
网友评论