一、图的表示
对于一个图（graph）G=（V，E）由顶点集V（）和边集E（edges）组成 。每一条边就是一个点对（u，w），其中u、w属于V 。
1.邻接矩阵（）
邻接矩阵本质上就是一个二维数组，例如对于每条边（u，w），可以表示为A[u][w]=1（边没有权值），否则A[u][w]=0（这条边不存在） 。如果边有权值，可以令A[u][w]=权值 。
2.邻接表
邻接表使用一个表来存放所有邻接的顶点 。

文章插图
邻接表：由上图可知，邻接表节点由头结点和表节点组成
（1）头表结点结构
┌────┬─────┐
│data││
└────┴─────┘
顶点vi邻接表的头结点包含两个域：
①顶点域data
存放顶点vi的信息
②指针域
vi的邻接表的头指针 。
（2）边表结点结构
┌────┬───┐
││next│
└────┴───┘
邻接表中每个表结点均有两个域:
①邻接点域
存放与vi相邻接的顶点vj的序号j 。
②链域next
将邻接表的所有表结点链在一起 。
注意：
--- 若要表示边上的信息(如权值)，则在表结点中还应增加一个数据域 。
---上述图用邻接表表示为：
ABCD
A0111
B1001
C1000
D1100
二、C代码实现其数据结构 1.邻接矩阵
在C语言中，如果我们想表示标准C语言不存在的数据类型，一般使用结构体来实现 。把已有的数据类型组合成我们想要的数据类型 。表示一张图，需要的参数有：图的顶点数，图的边数，一个二维数组，因此可以定义一个结构体包含三种类型的数据
#define ROW 100#define COL 100typedefstruct AdjMatrix{int matrix[ROW][COL];int NumVertex;//图的顶点数int Numedges;//图的边数}MGraph;//使用指针进行构建，自己管理内存typedefstruct AdjMatrix_P{int *matrix;int NumVertex;//图的顶点个数int Numedges;//图的边数}MPGraph;
这里使用了两种方法去构建图的数据类型，第一种方法定义了一个固定长度的二维数组，第二种方法定义一个指向整形类型的指针，但在使用前需要为其分配内存，来存放图的节点和边的信息 。
使用第一个数据类型构建一张图：

文章插图
void CreateGraph_AM(MGraph *G){int i=0,j=0;int s,t,w;cout<<"请输入顶点数和边数：";cin>>G->NumVertex>>G->Numedges;for(i=0;iNumVertex;i++)for(j=0;jNumVertex;j++){G->matrix[i][j]=0;}for(i=0;iNumedges;i++){cout<<"请输入第"<>s>>t>>w;G->matrix[s][t]=w;}}void print_AM(MGraph *G){int i=0,j=0;for(i=0;iNumVertex;i++){for(j=0;jNumVertex;j++){cout<
图的运行效果：

文章插图
使用第二种数据类型构建一张图：
void CreateGraph_AMP(MPGraph *G){int i=0,j=0;int s,t,w;cout<<"请输入顶点数和边数：";cin>>G->NumVertex>>G->Numedges;G->matrix=(int *)malloc(G->NumVertex*G->NumVertex*sizeof(int));if(G->matrix==NULL){cout<<"内存分配失败";return;}for(i=0;iNumVertex;i++)//初始化for(j=0;jNumVertex;j++){*(G->matrix+i*G->NumVertex+j)=0;}for(i=0;iNumedges;i++){cout<<"请输入第"<>s>>t>>w;*(G->matrix+s*G->NumVertex+t)=w;}}void print_AMP(MPGraph *G){int i=0,j=0;for(i=0;iNumVertex;i++){for(j=0;jNumVertex;j++){cout<

• 上一页
• 1
• 2
• 3
• 下一页

• 一张图点开是长图怎么制作,微信长图怎么制作？
• 一张图分辨风寒vs风热,怎样区分风寒，风热感冒？
• 20 时序图图形含义
• vue中图片和视频加载不出
• 绿色农业和生态农业的区别
• 一开5孔开关接线实物图,一开5孔开关接线实物图
• 一室一厅小户型装修,一室一厅小户型装修效果图 一室一厅一卫装修
• 一室一厅的廉租房图片,...想申请公租房一室一厅的
• 一幅春天简笔画图片,春天像一幅美丽的图画英文
• 南京一教授还原三国古地图发现关羽是路盲？