重点：邻接矩阵（数组）表示法 和 邻接表（链式）表示法
一：数组（邻接矩阵）表示法
１，先建立一个顶点表（记录各个顶点的信息）和一个邻接矩阵（表示各个顶点之间的关系）．
顶点表是一个一维数组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; }
