重点：邻接矩阵（数组）表示法 和 邻接表（链式）表示法
一：数组（邻接矩阵）表示法
１，先建立一个顶点表（记录各个顶点的信息）和一个邻接矩阵（表示各个顶点之间的关系）．
顶点表是一个一维数组Vexs[n]
无向图邻接矩阵是一个二维数组arcs[n][n],如果两个顶点间有边相连，那么arcs[n][n] = 1,否则arcs[n][n] = 0（n为两个顶点的下标）n取决于顶点个数
有向图邻接矩阵是一个二维数组arcs[i][j],如果存在着由i顶点发出的,到j顶点弧，那么arcs[i][j] = 1,别的位置都为0
无向图的邻接矩阵特点：
１，无向图的邻接矩阵是对称的；
２，顶点i的度 ＝ 第i行（列）中１的个数；
３，全完图的邻接矩阵中，对角元素为0，其余都是１；
在有向图的邻接矩阵中
第i行含义：以结点vi为尾的弧（即出度边）
第j列含义：以结点vj为头的弧（即入度边）
有向图的邻接矩阵特点：
１，有向图的邻接矩阵可能是不对称的．
２，顶点的出度 ＝ 第i行元素之和；顶点的入度 ＝ 第j列元素之和．
３，顶点的度 ＝ 第i行的元素之和 + 第j列的元素之和
网（即有权图）的邻接矩阵表示法
无向网的邻接矩阵，就是把无向图的邻接矩阵中的１，变成权值，0变成无穷大
有向网的邻接矩阵，就是把有向图的邻接矩阵中的１，变成权值，0变成无穷大
二，邻接矩阵代码实现
邻接矩阵的存储表示：用两个数组分别存储顶点表和邻接矩阵
#include
#include
#define MAXSIZE 100 //最大顶点数
typedef struct{
char vexs[MAXSIZE];//这里的数据类型根据实际情况而定
int arcs[MAXSIZE][MAXSIZE];//这里的数据类型根据实际情况而定
int vexnum, arcnum;//图的当前顶点数和边数
}G;
int main()
{
printf("Hello world!\n");
return 0;
}
算法思想：１，输入总顶点数和总边数
２，依次输入顶点的信息存入顶点表中．
３，初始化邻接矩阵，使每个权值初始化为极大值．
４，构造邻接矩阵．
#include
#include
#define MAXSIZE 100 //最大顶点数
#define MAX_INT 32767//设置最大值
typedef struct{
char vexs[MAXSIZE];//这里的数据类型根据实际情况而定
int arcs[MAXSIZE][MAXSIZE];//这里的数据类型根据实际情况而定
int vexnum, arcnum;//图的当前顶点数和边数
}Graph;
int get_index(char* arr,char m)
{
int i = 0;
for(i = 0; i < MAXSIZE; i++)
{
if(arr[i] == m)return i;
}
return -1;
}
void CreatGraph(Graph* G)
{
int i,j = 0;
printf("请输入顶点和边的数量:>");
scanf("%d%d",&G->vexnum,&G->arcnum);//把输入的值保存到图结构体中
for(i = 0; i < G->vexnum; i++)//初始化邻接矩阵
{
for(j = 0; j < G->vexnum; j++)
{
G->arcs[i][j] = MAX_INT;//边的权值设置为极大值
}
}
for(i = 0; i < G->vexnum; i++)
{
printf("请输入每个顶点的值:>");
getchar();//清除键盘缓存区的回车键
scanf("%c", &G->vexs[i]);//把输入的值保存到顶点数组当中
}
for(i = 0; i < G->arcnum; i++)//有几条边，循环几次
{
char m,n;//用来接收两个顶点
int w;//用来接收权值
int j,k;//接收顶点的下标
printf("请输入哪两个顶点之间有边，以及边的权值,格式为:ab 10:>");
getchar();
scanf("%c%c%d",&m,&n,&w);
j = get_index(G->vexs,m);//得到输入的m的值，在顶点数组中的下标
k = get_index(G->vexs,n);//得到输入的n的值，在顶点数组中的下标
G->arcs[j][k] = w;//给邻接矩阵对应的位置赋权值
G->arcs[k][j] = w;//因为是无向网，所以是对称的，给对称点赋相同值
}
}
int main()
{
Graph G;
CreatGraph(&G);
return 0;
}
会创建无向网了，无向图就只是初始化的时候，全部初始化为零，然后权值都为１
有向网就更容易了，别的都不变，只要把G->arcs[k][j] = w去掉，因为有向网不对称
数组（邻接矩阵）表示法的优点是：
１，直观，简单，好理解
２，方便检查任意一对顶点间是否存在边
３，方便找任一顶点的所有＂邻接点＂（有边直接相连的顶点）
４，方便计算任一顶点的度（从该点发出的边数为＂出度＂，指向该点的边数为＂入度＂）
无向图：对应行（或列）非0元素的个数
有向图：对应行非0元素的个数是＂出度＂，对应列非0元素的个数是＂入度＂
数组（邻接矩阵）表示法的缺点是：
１，不便于增加和删除顶点
２，浪费空间－－存稀疏图（点很多而边很少）有大量无效元素，空间复杂度为Ｏ（n*n)
３，浪费时间－－统计稀疏图中一共有多少条边,时间复杂度也为Ｏ（n*n)
三，邻接表表示法（链式）
１，顶点
按编号将顶点数据存储在一维数组中；
２，关联同一顶点的边（以顶点为尾的弧）
用线性链表存储
无 向 图特点：
１邻接表不唯一（上面表结点中１和３可以换位置）
２若无向图中有n个顶点，e条边，则其邻接表需要n个头结点和2e个表结点．适宜存储稀疏图
３无向图中顶点vi的度为第i个单链表中的结点数
有 向 图特点：
１顶点vi的出度为第i个单链表中的结点个数
２顶点vi的入度为整个单链表中邻接点域值是i-1的结点个数
这种邻接表，找出度容易，找入度难，所以就有另外一种逆邻接表
特点：
１顶点vi的入度为第i个单链表中的结点个数
２顶点vi的出度为整个单链表中邻接点域值是i-1的结点个数
这种邻接表，找入度容易，找出度难，所以我们可以根据实际情况选择合适的邻接表
四，图（网）的邻接表存储代码实现
用邻接表创建一个无向网：
表结点的结构体：
#include
#include
typedef struct TableNode{
int index;//结点在数组中的下标
TableNode* nextarc;
int info;//权值
}TNode;
int main()
{
return 0;
}
头结点和整个无向网结构体：
#include
#include
typedef struct TableNode{//表结点
int index;//结点在数组中的下标
TableNode* nextarc;
int info;//权值
}TNode;
typedef struct{//头结点
char data;
TNode* firstarc;
}HNode;
typedef struct{//整个无向网的结构体
HNode* Gragh;
int vexnum,arc;
}
int main()
{
return 0;
}
算法思想：１，输入顶点和边的数量，并保存在网结构体中
２，通过输入的顶点个数，创建头结点的数组
３，输入顶点的值，并把顶点的firstarc值赋空值
４，输入每条边的两个顶点值和这条边的权值
５，利用输入的值创建表结点，并用头插法加入到对应的头结点
具体的代码如下：
#include
#include
typedef struct TableNode{//表结点
int index;//结点在数组中的下标
struct TableNode* nextarc;
int info;//权值
}TNode;
typedef struct{//头结点
char data;
TNode* firstarc;
}HNode;
typedef struct{//整个无向网的结构体
HNode* Gragh;
int vexnum,arc;
}UnGragh;
int get_index(HNode* arr, char m, int nums)
{
int i = 0;
for(i = 0; i < nums; i++)
{
if(arr[i].data == m)
{
return i;
}
}
return -1;
}
void CreatUndigraghNet(UnGragh* G)
{
printf("请输入顶点和边的数量:>");
scanf("%d%d",&G->vexnum,&G->arc);
G->Gragh = malloc(sizeof(HNode)*G->vexnum);
int i = 0;
for(i = 0;i < G->vexnum; i++)
{
printf("请输入顶点的值:>");
getchar();
scanf("%c",&G->Gragh[i].data);
G->Gragh[i].firstarc = NULL;
}
for(i = 0;i < G->arc; i++)
{
char m,n;//用来接收两个顶点
int w;//用来接收权值
int j,k;//接收顶点的下标
printf("请输入哪两个顶点之间有边，以及边的权值,格式为:ab 10:>");
getchar();
scanf("%c%c%d",&m,&n,&w);
j = get_index(G->Gragh,m,G->vexnum);//得到输入的m的值，在顶点数组中的下标
k = get_index(G->Gragh,n,G->vexnum);//得到输入的n的值，在顶点数组中的下标
TNode* P1 = (TNode*)malloc(sizeof(TNode));//创建一个表结点
P1->index = k;//给表结点赋值
P1->info = w;
P1->nextarc = G->Gragh[j].firstarc;//利用头插法把表结点插入到头结点后面
G->Gragh[j].firstarc = P1;
//因为是无向的，所以下面还要再建立一个反向的边
TNode* P2 = (TNode*)malloc(sizeof(TNode));
P2->index = j;
P2->info = w;
P2->nextarc = G->Gragh[k].firstarc;
G->Gragh[k].firstarc = P2;
}
}
int main()
{
UnGragh G;
CreatUndigraghNet(&G);
return 0;
}
五，图的 十字链表 表示法
十字链表，就是集中了 邻结表 和 逆邻结表 的优势，找出度和找入度都容易的一种链表，适用于有向图或网的查找
firstout可以理解为邻结表的表头，方便查出度（指向出度）
firstin 可以理解为逆邻结表的表头，方便查入度（指向入度）
headvex 作为出度时对应头结点数组中的下标（弧头位置）
tailvex 作为入度时对应头结点数组中的下标（弧尾位置）
Tlink 弧尾相同的下一条弧
Hlink 弧头相同的下一条弧
继续用上面的例子：
把两个表揉合在一起，组成十字链表为：
用Ｃ语言，生成十字链表有向图，代码为：
#include
#include
typedef struct TableNode{//表结点
int headvex;//弧头位置（下标）
int tailvex;//弧尾位置（下标）
struct TableNode* Hlink;//弧头相同的下一条弧
struct TableNode* Tlink;//弧尾相同的下一条弧
}TNode;
typedef struct{//头结点
char data;
TNode* firstin;//指向入度
TNode* firstout;//指向出度
}HNode;
typedef struct{//整个有向图的结构体
HNode* Gragh;
int vexnum,arc;
}UnGragh;
int get_index(HNode* arr, char m, int nums)
{
int i = 0;
for(i = 0; i < nums; i++)
{
if(arr[i].data == m)
{
return i;
}
}
return -1;
}
void CreatUndigraghNet(UnGragh* G)
{
printf("请输入顶点和边的数量:>");
scanf("%d%d",&G->vexnum,&G->arc);
G->Gragh = malloc(sizeof(HNode)*G->vexnum);
int i = 0;
for(i = 0;i < G->vexnum; i++)
{
printf("请输入顶点的值:>");
getchar();
scanf("%c",&G->Gragh[i].data);
G->Gragh[i].firstin = NULL;
G->Gragh[i].firstout = NULL;
}
for(i = 0;i < G->arc; i++)
{
char m,n;//用来接收两个顶点
int j,k;//接收顶点的下标
printf("请按方向输入每一条边的两个顶点值,格式为:ab>");
getchar();
scanf("%c%c",&m,&n);
j = get_index(G->Gragh,m,G->vexnum);//得到输入的m的值，在顶点数组中的下标
k = get_index(G->Gragh,n,G->vexnum);//得到输入的n的值，在顶点数组中的下标
TNode* P1 = (TNode*)malloc(sizeof(TNode));//创建一个表结点
//利用头插法把出度边插入到G->Gragh[j]后面
P1->tailvex = j;
P1->headvex = k;
P1->Tlink = G->Gragh[j].firstout;
G->Gragh[j].firstout = P1;
//利用头插法把入度边插入到G->Gragh[k]后面
P1->Hlink = G->Gragh[k].firstin;
G->Gragh[k].firstin = P1;
}
}
int main()
{
UnGragh G;
CreatUndigraghNet(&G);
return 0;
}
邻接多重表主要是用在无向图中，解决无向图中每条边都要存储两遍，造成浪费的问题
邻接多重表的头结点和表结点的存储结构为：
data:顶点的值
firstedge:连接该顶点的第一条边
ivex, jvex:为一条边的两个顶点的下标
ilink:关联 ivex下标代表的头结点的下一条边
jlink:关联 jvex下标代表的头结点的下一条边
例：
具体的生成代码为：
#include
#include
typedef struct TableNode{//表结点
int ivex;
int jvex;//一条边的两个顶点
struct TableNode* ilink;//关联ivex的下一条边指针
struct TableNode* jlink;//关联jvex的下一条边指针
}TNode;
typedef struct{//头结点
char data;
TNode* firstedge;//指向第一条边
}HNode;
typedef struct{//无向图的结构体
HNode* Gragh;
int vexnum,arc;
}UnGragh;
int get_index(HNode* arr, char m, int nums)//根据输入得到下标
{
int i = 0;
for(i = 0; i < nums; i++)
{
if(arr[i].data == m)
{
return i;
}
}
return -1;
}
void CreatUndigraghNet(UnGragh* G)
{
printf("请输入顶点和边的数量:>");
scanf("%d%d",&G->vexnum,&G->arc);
G->Gragh = malloc(sizeof(HNode)*G->vexnum);
int i = 0;
for(i = 0;i < G->vexnum; i++)
{
printf("请输入顶点的值:>");
getchar();
scanf("%c",&G->Gragh[i].data);
G->Gragh[i].firstedge = NULL;
}
for(i = 0;i < G->arc; i++)
{
char m,n;//用来接收两个顶点
int j,k;//接收顶点的下标
printf("请按方向输入每一条边的两个顶点值,格式为:ab>");
getchar();
scanf("%c%c",&m,&n);
j = get_index(G->Gragh,m,G->vexnum);//得到输入的m的值，在顶点数组中的下标
k = get_index(G->Gragh,n,G->vexnum);//得到输入的n的值，在顶点数组中的下标
TNode* P1 = (TNode*)malloc(sizeof(TNode));//创建一个表结点
//利用头插法把输入的第一条边插入到头结点G->Gragh[j]后
P1->ivex = j;
P1->jvex = k;
P1->ilink = G->Gragh[j].firstedge;
G->Gragh[j].firstedge = P1;
//利用头插法把输入的第一条边插入到头结点G->Gragh[k]后面
P1->jlink = G->Gragh[k].firstedge;
G->Gragh[k].firstedge = P1;
}
}
int main()
{
UnGragh G;
CreatUndigraghNet(&G);
return 0;
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）