图相关文章：
1. 图的建立 - 邻接矩阵与邻接表https://blog.csdn.net/m15253053181/article/details/127552328?spm=1001.2014.3001.55012. 图的遍历 - DFS与BFShttps://blog.csdn.net/m15253053181/article/details/127558368?spm=1001.2014.3001.55013. 顶点度的计算https://blog.csdn.net/m15253053181/article/details/127558599?spm=1001.2014.3001.55014. 最小生成树 - Prim与Kruskalhttps://blog.csdn.net/m15253053181/article/details/127589852?spm=1001.2014.3001.55015. 单源最短路径 - Dijkstra与Bellman-Fordhttps://blog.csdn.net/m15253053181/article/details/127630356?spm=1001.2014.3001.55016. 多源最短路径 - Floydhttps://blog.csdn.net/m15253053181/article/details/128039852?spm=1001.2014.3001.55017. 拓扑排序AOV网https://blog.csdn.net/m15253053181/article/details/128042358?spm=1001.2014.3001.5501
目录
图的建立
1 邻接矩阵
1.1 基本概念
1.2 由文件创建邻接矩阵图
2 邻接表
2.1 基本概念
2.2 由文件创建邻接表
3 邻接矩阵与邻接表之间的转换
3.1 邻接矩阵转邻接表
3.2 邻接表转邻接矩阵
图的建立
以图无向图为例进行讲解（有向图原理一致）。
推荐一个图论画图的网站：CS Academy
1 邻接矩阵
1.1 基本概念
以邻接矩阵G[N][N]表示含有N个顶点的无向图（编号为0~N-1），dis<v_i,v_j>表示两顶点间的距离。
复杂度分析：
- 时间复杂度：O(n^2)
- 空间复杂度：O(n^2)
优点：
① 便于判断任一对顶点是否有边；
② 方便找任意顶点的邻接点；
③ 方便计算任意顶点的度。
缺点：
① 适合稠密图，对于稀疏图来说比较浪费空间；
② 统计稀疏图中的边数时浪费时间。
1.2 由文件创建邻接矩阵图
（1）图的数据结构
/* 邻接矩阵存储图 */
typedef struct MGraph
{
int numV; // 顶点数
int numE; // 边数
char nameV[MaxVertexNum]; // 顶点的名字
int dis[MaxVertexNum][MaxVertexNum]; // 邻接矩阵
} MG, *MGraph;（2）由文件创建邻接矩阵图
想要从文件中读取一个图，我们要知道图中共有几个顶点，每个顶点的编号是什么，各个顶点间边的信息。因此规定数据写入格式如下：
需要注意的是，对于无向图来说，起点与终点是谁并不重要。并且在生成矩阵时，需要注意为实对称矩阵，不连通顶点之间距离记为-1。
结果示例：
代码如下，注释比较清晰，不再赘述：文章来源：https://www.toymoban.com/news/detail-463174.html
/* 由文件创建邻接矩阵图 */
MGraph createMGraphByFile(FILE *fp)
{
assert(fp);
MGraph graph = (MGraph)malloc(sizeof(struct MGraph));
int i, j, count;
char temp[MaxVertexNum];
char buffer[MaxVertexNum];
int nums[3]; // 存放内容：起点 终点 距离
int countOfEdge = 0;
// 读入顶点数 - 第一行
fgets(buffer, MaxVertexNum, fp);
graph->numV = atoi(buffer);
// 读入顶点的名字 - 仅限1个char
for (i = 0; i < graph->numV; i++)
{
fgets(buffer, MaxVertexNum, fp);
graph->nameV[i] = buffer[0];
}
// 初始化邻接矩阵
for (i = 0; i < graph->numV; i++)
for (j = 0; j < graph->numV; j++)
graph->dis[i][j] = -1;
// 读入邻接矩阵
while (fgets(buffer, MaxVertexNum, fp))
{
j = 0;
for (i = 0; i < 3; i++) // 起点 终点 距离 3个数据
{
count = 0;
while (buffer[j] >= '0' && buffer[j] <= '9')
{
temp[count] = buffer[j];
count++;
j++;
}
temp[count] = '\0';
nums[i] = atoi(temp);
j++;
}
graph->dis[nums[0]][nums[1]] = nums[2];
graph->dis[nums[1]][nums[0]] = nums[2];
countOfEdge++; // 记录边数
}
// 读入边数
graph->numE = countOfEdge;
return graph;
}2 邻接表
2.1 基本概念
使用指针数组G[N]，G[i]代表以第i个顶点为头结点的链表，只存与之邻接的顶点。
复杂度分析：
- 时间复杂度：O(n+2e)
- 空间复杂度：O(n+2e)
优点：
① 方便找任意顶点的邻接点；
② 节约稀疏图的空间。仅需要N个头指针和2E个结点（每个结点至少2个域）；
③ 方便计算无向图的度与有向图的出度，对于有向图的入度，需构造“逆邻接表”（存指向自己的边）来方便计算。
缺点：
① 难以判断任一对顶点是否有边。
2.2 由文件创建邻接表
（1）图的数据结构
/* 邻接表存储图 */
typedef struct LGNode
{
int v; // 邻接点下标
int dis; // 与邻接表该行顶点的距离
struct LGNode *next; // 下一个结点
} LG, *LGNode;
typedef struct AdjList
{
int numV; // 顶点数
int numE; // 边数
char nameV[MaxVertexNum]; // 顶点的名字
LGNode list; // 表 - 动态数组
} AdjL, *AdjList;（2）由文件创建邻接矩阵图
文件信息和邻接矩阵相同。
结果示例：
代码如下，注释比较清晰，不再赘述：
/* 由文件创建邻接表 */
AdjList createAdjListByFile(FILE *fp)
{
assert(fp);
AdjList L = (AdjList)malloc(sizeof(struct AdjList));
int i, j, count;
char temp[MaxVertexNum];
char buffer[MaxVertexNum];
int nums[3]; // 存放内容：起点 终点 距离
int countOfEdge = 0;
// 读入顶点数
fgets(buffer, MaxVertexNum, fp);
L->numV = atoi(buffer);
// 读入顶点的名字 - 仅限1个char
for (i = 0; i < L->numV; i++)
{
fgets(buffer, MaxVertexNum, fp);
L->nameV[i] = buffer[0];
}
// 初始化邻接表
L->list = (LGNode)malloc(sizeof(struct LGNode) * L->numV);
for (i = 0; i < L->numV; i++)
{
L->list[i].v = i;
L->list[i].dis = -1;
L->list[i].next = NULL;
}
// 读入邻接表
while (fgets(buffer, MaxVertexNum, fp))
{
j = 0;
for (i = 0; i < 3; i++) // 起点 终点 距离 3个数据
{
count = 0;
// 顶点数可能大于1位数
while (buffer[j] >= '0' && buffer[j] <= '9')
{
temp[count] = buffer[j];
count++;
j++;
}
temp[count] = '\0';
nums[i] = atoi(temp);
j++;
}
// 头插法，需将边添加到邻接表对应两行中
LGNode newNode1 = (LGNode)malloc(sizeof(struct LGNode));
newNode1->next = L->list[nums[0]].next;
newNode1->v = nums[1];
newNode1->dis = nums[2];
L->list[nums[0]].next = newNode1;
LGNode newNode2 = (LGNode)malloc(sizeof(struct LGNode));
newNode2->next = L->list[nums[1]].next;
newNode2->v = nums[0];
newNode2->dis = nums[2];
L->list[nums[1]].next = newNode2;
countOfEdge++; // 记录边数
}
// 读入边数
L->numE = countOfEdge;
return L;
}3 邻接矩阵与邻接表之间的转换
不常用的功能，仅作参考。文章来源地址https://www.toymoban.com/news/detail-463174.html
3.1 邻接矩阵转邻接表
/* 邻接矩阵转邻接表 */
AdjList MGraphToAdjList(MGraph graph)
{
int i, j;
// 初始化邻接表
AdjList L = (AdjList)malloc(sizeof(struct AdjList));
L->numV = graph->numV; // 顶点数
L->numE = graph->numE; // 边数
for (i = 0; i < L->numV; i++) // 顶点的名字
L->nameV[i] = graph->nameV[i];
L->list = (LGNode)malloc(sizeof(struct LGNode) * L->numV); // 邻接表初始化
for (i = 0; i < L->numV; i++)
{
L->list[i].v = i;
L->list[i].dis = -1;
L->list[i].next = NULL;
}
// 构建邻接表
for (i = 0; i < L->numV; i++)
{
for (j = 0; j < L->numV; j++)
{
if (graph->dis[i][j] != -1) // 边存在
{
// 头插法
LGNode newNode = (LGNode)malloc(sizeof(struct LGNode));
newNode->v = j;
newNode->dis = graph->dis[i][j];
newNode->next = L->list[i].next;
L->list[i].next = newNode;
}
}
}
return L;
}3.2 邻接表转邻接矩阵
/* 邻接表转邻接矩阵 */
MGraph AdjListToMGraph(AdjList L)
{
int i, j;
// 初始化邻接矩阵
MGraph graph = (MGraph)malloc(sizeof(struct MGraph));
graph->numV = L->numV;
graph->numE = L->numE;
for (i = 0; i < graph->numV; i++) // 顶点的名字
graph->nameV[i] = L->nameV[i];
for (i = 0; i < graph->numV; i++) // 邻接矩阵置为-1
for (j = 0; j < graph->numV; j++)
graph->dis[i][j] = -1;
// 构建邻接矩阵
LGNode pMove = NULL;
for (i = 0; i < L->numV; i++)
{
pMove = &(L->list[i]);
while (pMove)
{
graph->dis[i][pMove->v] = pMove->dis;
pMove = pMove->next;
}
}
return graph;
}到了这里，关于【图】（一）图的建立 - 邻接矩阵与邻接表 - C语言的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
