图
图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G 表示一个图，V 是图 G 中顶点的集合，E 是图 G 中边的集合。
术语
无向图：每条边都是无方向的图
有向图：每条边都是有方向的图
完全图：任意两个点都有一条边相连的图
边：无向图中的边
弧：有向图中的边
稀疏图：有很少边或弧的图
稠密图：有较多边或弧的图
网：边/弧带权的图（带权的意思就是边/弧上有数值）
邻接：有边/弧相连的两个顶点间的关系称为邻接
顶点的度：与该顶点相连的边的数目
在有向图中，顶点的度等于该顶点的入度和出度之和
顶点的入度是以该顶点为终点的弧的条数
顶点的出度是以该顶点为起点的弧的条数
路径：连续的边所构成的顶点序列
路径长度：路径上边/弧的数目
回路（环）：第一个顶点和最后一个顶点相同的路径
简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径
简单回路（环）：除路径起点和终点相同外，其余顶点均不相同的路径
连通图：在无向图中，从任意一个顶点出发，可以到达其余任意顶点
强连通图：在有向图中，从任意一个顶点出发，可以到达其余任意顶点
权：图中边或弧所具有的相关树称为权，表明从一个顶点到另一个顶点的距离或耗费
网：带权的图称为网
存储结构
- 顺序存储结构
邻接矩阵（数组表示法）
- 链式存储结构
邻接表（链式表示法）
邻接矩阵
设图的顶点数量为 n，邻接矩阵使用一个 n * n 大小的矩阵（二维数组）来表示图，每一行（列）代表一个顶点，用1或0表示两个顶点之间是否存在边
建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）
无向图：
有向图：
有向图的邻接矩阵中，行号表示弧的起点，列号表示弧的终点
如果想要表示网，则将邻接矩阵中的0换成无穷大即可
表示
#define MAX_INT 2147483647
#define MAX_V_NUM 100
typedef struct AMGraph
{
char vexs[MAX_V_NUM];
int arcs[MAX_V_NUM][MAX_V_NUM];
int vex_num;
int arc_num;
}AMGraph;
MAX_INT：表示极大值，即无穷大，用在网中
MAX_V_NUM：表示最大顶点树
AMGraph：Adjacency Matrix Graph 邻接矩阵图
char vexs[MAX_V_NUM]：顶点表
int arcs[MAX_V_NUM][MAX_V_NUM]：邻接矩阵，表示顶点间的关系
int vex_num：图的顶点数
int arc_num：图的边数
创建无向图
思路：
- 输入图的顶点数和边数
- 将点的信息存入顶点表中
- 初始化邻接矩阵
- 构造邻接矩阵，将边的信息存入矩阵中
void create_UDG(AMGraph* G)
{
//输入图的顶点数和边数
printf("Enter vex num:");
scanf("%d", &G->vex_num);
printf("Enter arc num:");
scanf("%d", &G->arc_num);
//将点的信息存入顶点表中（所谓的点的信息，其实就是点的名字）
int i = 0;
int j = 0;
for (i = 0; i < G->vex_num; i++)
{
printf("Enter information for the %d-th vertex:", i + 1);
scanf(" %c", &G->vexs[i]);
}
//初始化邻接矩阵
for (i = 0; i < G->vex_num; i++)
{
for (j = 0; j < G->vex_num; j++)
{
G->arcs[i][j] = 0; //网：MAX_INT，图：0
}
}
//构造邻接矩阵
for (i = 0; i < G->arc_num; i++)
{
char v1 = 0;
char v2 = 0;
//int w = 0;
printf("Input two connected vertices：");
scanf(" %c %c", &v1, &v2);
//printf("Enter the starting point of the edge:");
//scanf(" %c", &v1);
//printf("Enter the endpoint of the edge:");
//scanf(" %c", &v2);
//printf("Input the weight of the edge:");
//scanf("%d", &w);
int i = locate_vex(G, v1);
int j = locate_vex(G, v2);
//G->arcs[i][j] = w;
G->arcs[i][j] = 1;
G->arcs[j][i] = G->arcs[i][j];
}
}
int locate_vex(AMGraph* G, char v)
{
int i = 0;
for (i = 0; i < G->vexs; i++)
{
if (v == G->vexs[i])
{
return i;
}
}
return -1;
}
以上代码，进行适当的修改，可以用来创建有向图、无向网、有向网
邻接表
邻接表（adjacency list）使用 n 个链表来表示图，链表结点表示顶点。链表中存储了该顶点的所有邻接顶点（与该顶点相连的顶点）
顶点表中的结点分为数据域和链域，数据域存储顶点信息，链域指向链表中的第一个结点
链表中的结点分为邻接点域、链域和数据域，邻接点域表示该顶点，存储顶点在顶点表中的位置，链域指向下一个相连的顶点，数据域存储与边有关的信息（权值）
在有向图中，链接的都是弧指向的顶点（如果反过来，那就是逆邻接表）
表示
#define MAX_INT 2147483647
#define MAX_V_NUM 100
//ArcNode 表示链表中的结点
typedef struct ArcNode
{
int adjvex; //该顶点在顶点表中的位置
struct ArcNode* nextarc;//指向下一个相连的顶点
int info; //存储与边有关的信息（权值）
}ArcNode;
//VNode 表示顶点表中的结点
typedef struct VNode
{
char data; //顶点信息
ArcNode* firstarc; //指向与该顶点第一个相连的顶点
}VNode, AdjList[MAX_V_NUM]; //AdjList 表示顶点表
//ALGraph 用邻接表表示的图
typedef struct ALGraph
{
AdjList vertices; //顶点表 verticse是vertex的复数
//相当于AdjList vertices[MAX_V_NUM]
int vex_num; //图的顶点数
int arc_num; //图的边数
}ALGraph;
创建无向图
思路：
- 输入顶点数和边数
- 建立顶点表（输入顶点信息，指针域置NULL）
- 创建邻接表
void create_UDG(ALGraph* G)
{
//输入图的顶点数和边数
printf("Enter vex num:");
scanf("%d", &G->vex_num);
printf("Enter arc num:");
scanf("%d", &G->arc_num);
//将点的信息存入顶点表中
int i = 0;
int j = 0;
for (i = 0; i < G->vex_num; i++)
{
printf("Enter information for the %d-th vertex:", i + 1);
scanf(" %c", &G->vertices[i].data);
G->vertices[i].firstarc = NULL;
}
//创建邻接表
for (i = 0; i < G->arc_num; i++)
{
char v1 = 0;
char v2 = 0;
printf("Input two connected vertices:");
scanf(" %c %c", &v1, &v2);
int i = locate_vex(G, v1);
int j = locate_vex(G, v2);
ArcNode* p1 = (ArcNode*)malloc(sizeof(ArcNode));
if (p1 == NULL)
{
exit(0);
}
ArcNode* p2 = (ArcNode*)malloc(sizeof(ArcNode));
if (p2 == NULL)
{
exit(0);
}
//p1结点是和顶点v1相连的结点，所以p1结点存的是顶点v2的信息
p1->adjvex = j;
//头插法建立链表，因此，最后的输出的次序和输入的次序是相反的（DFS、BFS）
p1->nextarc = G->vertices[i].firstarc;
G->vertices[i].firstarc = p1;
p2->adjvex = i;
p2->nextarc = G->vertices[j].firstarc;
G->vertices[j].firstarc = p2;
}
}
int locate_vex(ALGraph* G, char v)
{
int i = 0;
for (i = 0; i < G->vex_num; i++)
{
if (v == G->vertices[i].data)
{
return i;
}
}
return -1;
}
优缺点
邻接矩阵
- 优点
方便查找”邻接点“
方便计算顶点的”度“
- 缺点
不便于增加和删除顶点
浪费空间，如果是稀疏图，会有大量的空间浪费
邻接表
- 优点
方便查找”邻接点“
节约空间
- 缺点
不便于检查任意一对顶点间是否存在边
邻接矩阵多用于稠密图，邻接表多用于稀疏图
图的遍历
遍历：从已给出的连通图中的某一顶点出发，沿着一些边访遍图中的所有顶点，且每个顶点仅被访问一次
以下代码都是假设所要搜索的图是无向图
深度优先搜索
深度优先搜索（Depth First Search）（DFS）
思路：
构造一个辅助数组 visited[i]，用来标记每个被访问过的顶点
在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1
再从 w1 出发，访问与 w1 邻接但未被访问过的顶点 w2
再从 w2 出发，进行类似的访问
如此反复，直至到达所有的邻接顶点都被访问过的顶点 u 为止
接着，回退一步，退到前一次访问的顶点，看是否还有其他未被访问的邻接顶点
如果有，访问该顶点，再从该顶点出发，进行访问
如果没有，继续回退，重复之前步骤，直到图中所有的顶点都被访问过
例如：
对于该图的深度优先搜索，有如下访问次序：
v1、v2、v4、v8、v5、v3、v6、v7
v1、v3、v6、v7、v2、v4、v8、v5
......
基于邻接矩阵
void DFS(AMGraph* G, char v, int visited[MAX_V_NUM])
{
printf("%c ", v);
int i = locate_vex(G, v);
visited[i] = 1;
int j = 0;
for (j = 0; j < G->vex_num; j++)
{
if (G->arcs[i][j] != 0 && visited[j] != 1)
{
char next_v = G->vexs[j];
DFS(G, next_v, visited);
}
}
}
基于邻接表
void DFS(ALGraph* G, char v, int visited[MAX_V_NUM])
{
int i = locate_vex(G, v);
visited[i] = 1;
printf("%c ", v);
ArcNode* p = G->vertices[i].firstarc;
while (p != NULL)
{
char next_v = G->vertices[p->adjvex].data;
i = locate_vex(G, next_v);
if (visited[i] == 0)
{
DFS(G, next_v, visited);
}
p = p->nextarc;
}
}
广度优先搜索
广度优先搜索（Breadth First Search）（BFS）
思路：
从图的某一顶点出发，首先依次访问该顶点的所有邻接点，再按访问这些邻接点的顺序，依次访问与它们相邻接的且未被访问过的顶点，重复此过程，直到所有顶点被访问为止
例如：
访问次序：
v1、v2、v3、v4、v5、v6、v7、v8
基于邻接矩阵
void BFS(AMGraph* G, char v, int visited[MAX_V_NUM])
{
printf("%c ", v);
int i = locate_vex(G, v);
visited[i] = 1;
Queue Q;
init(&Q);
in(&Q, v);
while (isEmpty(&Q) != 1) //队列不为空时，循环继续
{
char u = out(&Q); //队头出队
i = locate_vex(G, u);
int j = 0;
for (j = 0; j < G->vex_num; j++) //找出队顶点的邻接点
{
if (G->arcs[i][j] != 0 && visited[j] != 1)
{
//输出顶点信息，然后该顶点入队
char next_v = G->vexs[j];
printf("%c ", next_v);
visited[j] = 1;
in(&Q, next_v);
}
}
}
}
基于邻接表
void BFS(ALGraph* G, char v, int visited[MAX_V_NUM])
{
Queue Q;
init(&Q);
printf("%c ", v);
int i = locate_vex(G, v);
visited[i] = 1;
in(&Q, v);
while (isEmpty(&Q) != 1)
{
char u = out(&Q);
i = locate_vex(G, u);
ArcNode* p = G->vertices[i].firstarc;
while (p != NULL)
{
if (visited[p->adjvex] == 0)
{
char next_v = G->vertices[p->adjvex].data;
printf("%c ", next_v);
visited[p->adjvex] = 1;
in(&Q, next_v);
}
p = p->nextarc;
}
}
}