|
图是一种复杂的数据结构，顶点之间的逻辑关系错综复杂，因此图的存储结构也分多种，由于图是由顶点和边或弧这两部分组成，所以将这两部分合到一个结构中比较困难。所以我们使用两个结构去存储图这种结构。这里主要介绍两种基本的存储结构，即邻接矩阵与邻接表。 
存储结构
邻接矩阵无向图有向图网图代码
邻接表无向图有向图网图代码
邻接矩阵
图的邻接矩阵(Adjacency Matrix) 存储方式是用两个数组来表示图。一个一维 数组存储图中顶点信息， 一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
无向图
若图中有n个顶点，则邻接矩阵是一个n*n的二维数组，定义为  举例示意图如下：  可知: 1.我们要判定任意两顶点是否有边无边就观察这两顶点的交叉点是1还是0。 2.我们要知道某个顶点的度，其实就是这个顶点在邻接矩阵中第i行(或第i列)的元素之和。比如顶点B的度就是1+0+1+0=2。 3.求顶点的所有邻接点就是将矩阵中第i行元素扫描一遍。 4.无向图的邻接矩阵是一个对称矩阵。
有向图
举例示意图如下：  可知： 1.一个顶点的入度为这个顶点所在列的各数之和，出度为这个顶点所在行的各数之和。eg:A的入度为0+0+0+1=1；出度为0+1+0+0=1。 2.判断顶点Ai 到Aj 是否存在弧，只需要查找矩阵中arc[i][j] 是否为1即可。 3.要求Ai的所有邻接点(Ai邻接到Aj)就是将矩阵第i行元素扫描一遍，查找arc[i][j]为1的顶点。
网图
若网图中有n个顶点，则邻接矩阵是一个n*n的二维数组，定义为： 
举例示意图如下：  网图与无向图或有向图的定义方式不同罢了，分析方法同上。
代码
//*****图——邻接矩阵*******
#include
#include
typedef char datatype;
typedef int edgetype;
#define MAXVEX 20 //顶点最大数，由使用者自定义
#define INFINITY 65535 //代指无限大
typedef struct
{
datatype data[MAXVEX]; //顶点表
edgetype arc[MAXVEX][MAXVEX]; //存储边或弧的权的邻接矩阵
int numVertexes,numEdges; //顶点数,边或弧的个数
}MGraph;//图结构--邻接矩阵
void Creat_MGraph(MGraph *G);
int main()
{
MGraph G;
Creat_MGraph(&G);
int i,j;
//将边表进行输出检查
printf
for(i=0;inumEdges=b;
//初始化邻接矩阵
for(i=0;iarc[i][j]=INFINITY;
}
}
//给每个顶点赋值
for(i=0;idata[i]=ch;
}
//给每条边或弧赋值
for(i=0;iarc[x][y]=w;
G->arc[y][x]= G->arc[x][y]; // 若为无向图，矩阵对称。否则删除即可
}
//n:顶点数，e:边数 时间复杂度O(n^2+n+e)--------->O(n^2)
}
输出结果： 
邻接表
邻接矩阵是不错的一种图存储结构， 但是我们也发现，对于边数相对顶点较少的图，这种结构是存在对存储空间的极大浪费的。于是我们考虑对边或弧使用链式存储的方式，这样的话，不管有多少边，也不会存在空间浪费问题。
这种数组与链表相结合的存储方法称为邻接表(Adjacency List)。
邻接表的处理办法是这样。 1.图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。另外,对于顶点数组中,每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。  2.图中每个顶点的所有邻接点构成一个线性表， 由于邻接点的个数不定，所以用单链表存储，无向图称为顶点的边表，有向图则称为顶点作为弧尾的出边表。. 
无向图
有向图
网图
 其实只要这些结构图能够被我们画出来，那么我们也会更清晰直观的理解两种存储结构。
代码
//*****图——邻接表*******
#include
#include
typedef char datatype;
typedef int edgetype;
#define MAXVEX 20
typedef struct ENode
{
int adjvex; //当前顶点的邻接点在顶点表中的下标
edgetype w; //权数
struct ENode *next; //指向下一个邻接点
}EdgeNode;//边表结构
typedef struct VNode
{
datatype data;
EdgeNode *firstedge; //当前顶点的第一个邻接点，边表头指针
}VertexNode,AdjList[MAXVEX];//顶点结构
typedef struct
{
AdjList adjList; //储存所有的顶点的数组
int numVertexes,numEdges;//图中顶点数,边或弧的个数
}GraphAdjList;//图结构--邻接表
void Creat_GraphAdjList(GraphAdjList *G);
int main()
{
GraphAdjList G;
Creat_GraphAdjList(&G);
}
//使用图的邻接表存储方式创建网图 无向网图
void Creat_GraphAdjList(GraphAdjList *G)
{
int v_num,e_num;
int i,x,y;
EdgeNode *e;
datatype ch;
edgetype w;
printf("Please input numVertexes,numEdges:");
scanf("%d,%d",&v_num,&e_num); //顶点个数 , 边或弧的个数
G->numVertexes=v_num;
G->numEdges=e_num;
//给每个顶点赋值
for(i=0;iadjList[i].data=ch;
G->adjList[i].firstedge=NULL;
}
//建立边表
/*建立有向图时，输入一次下标时
只需将其中一个顶点作为弧尾或弧头的形式 进行建立边表
不用管另一个顶点的边也要反向建立*/
for(i=0;iadjvex=y;
e->w=w;
e->next=G->adjList[x].firstedge; //以头插法的形式将边插入到边表中
G->adjList[x].firstedge=e;
e=(EdgeNode*)malloc(sizeof(EdgeNode));
e->adjvex=x;
e->w=w;
e->next=G->adjList[y].firstedge;
G->adjList[y].firstedge=e;
}
//n:顶点数，e:边数 时间复杂度--------->O(n+e)
//打印邻接表
printf("邻接表为:\n");
for(i=0;inumVertexes;i++){
e=G->adjList[i].firstedge;
while(e){
printf("(%c,%c)",G->adjList[i].data,G->adjList[e->adjvex].data);
e=e->next;
}
printf("\n");
}
}
输出结果：  画图不易啊、画图不易啊、画图不易啊！！！！  不足之处，还请批评指正。 十字链表法传送门。
|