图
顶点（Vertex）： 图中的基本元素，通常表示为一个节点。在数学中，顶点也被称为节点。
边（Edge）： 顶点之间的连接，表示节点之间的关系。边可以是有向的（有箭头的，表示方向）或无向的（没有箭头，表示双向关系）。
邻接： 两个顶点之间存在边时，它们被称为邻接的。
路径（Path）： 顶点序列，其中每两个相邻的顶点都通过边相连。
无环图和有环图： 如果图中不存在环（即不存在从某个节点出发经过若干边回到该节点的路径），则称该图为无环图；否则称为有环图。
连通图和非连通图： 如果图中任意两个顶点之间都存在路径，则称该图为连通图；否则称为非连通图。
权重（Weight）： 与边关联的数值，表示边的权重或成本。图中的边可以带有权重，这种图称为带权图。
度（Degree）： 一个顶点的度是与其相邻的边的数量。在有向图中，分为入度和出度。
图可以分为有向图和无向图，带权图和无权图等不同类型。图的表示方法有邻接矩阵和邻接表两种常见方式。
邻接矩阵： 使用二维数组表示图中的顶点之间的关系，matrix[i][j]表示顶点i到顶点j是否有边。
邻接表： 使用链表或数组的数组表示，每个顶点的邻接点都存储在与该顶点相关联的列表中。
图的创建
邻接矩阵
#include <stdio.h>
// 定义图的最大顶点数
#define MAX_VERTICES 10
// 无向图邻接矩阵表示
void createUndirectedGraph(int graph[MAX_VERTICES][MAX_VERTICES], int edges) {
int i, j, u, v;
// 初始化邻接矩阵
for (i = 0; i < MAX_VERTICES; i++) {
for (j = 0; j < MAX_VERTICES; j++) {
graph[i][j] = 0;
}
}
// 输入边的信息，构建邻接矩阵
for (i = 0; i < edges; i++) {
scanf("%d %d", &u, &v);
graph[u][v] = graph[v][u] = 1;
}
}
// 有向图邻接矩阵表示
void createDirectedGraph(int graph[MAX_VERTICES][MAX_VERTICES], int edges) {
int i, j, u, v;
// 初始化邻接矩阵
for (i = 0; i < MAX_VERTICES; i++) {
for (j = 0; j < MAX_VERTICES; j++) {
graph[i][j] = 0;
}
}
// 输入边的信息，构建邻接矩阵
for (i = 0; i < edges; i++) {
scanf("%d %d", &u, &v);
graph[u][v] = 1;
}
}
// 打印邻接矩阵
void printGraph(int graph[MAX_VERTICES][MAX_VERTICES], int vertices) {
int i, j;
printf("Graph Adjacency Matrix:\n");
for (i = 0; i < vertices; i++) {
for (j = 0; j < vertices; j++) {
printf("%d ", graph[i][j]);
}
printf("\n");
}
}```
** 当定点数和边数不确定时 **
```c
#include <stdio.h>
#include <malloc.h>
typedef struct {
int vertices;
int edge;
int** adjacencyMatrix;
}Graph;
Graph* CreateGraph(int vertices, int edge) {
Graph* graph;
graph = (Graph*)malloc(sizeof(Graph));
graph->vertices = vertices;
graph->edge = edge;
// 动态分配内存给邻接矩阵
graph->adjacencyMatrix = (int**)malloc(vertices * sizeof(int*));//乘以 vertices 表示我们需要为每一行分配内存
for (int i = 0; i < vertices; i++) {
graph->adjacencyMatrix[i] = (int*)malloc(vertices * sizeof(int));
if (graph->adjacencyMatrix[i] == NULL) {
printf("Memory allocation failed\n");
}
// 初始化邻接矩阵
for (int j = 0; j < vertices; j++) {
graph->adjacencyMatrix[i][j] = 0;
}
}
return graph;
}
// 释放图的内存
void freeGraph(Graph* graph) {
for (int i = 0; i < graph->vertices; i++) {
free(graph->adjacencyMatrix[i]);
}
free(graph->adjacencyMatrix);
free(graph);
}
// 无向图邻接矩阵表示
void createUndirectedGraph(Graph* graph) {
int u, v;
// 输入边的信息，构建邻接矩阵
for (int i = 0; i < graph->edge; i++) {
scanf("%d %d", &u, &v);
graph->adjacencyMatrix[u][v] = graph->adjacencyMatrix[v][u] = 1;
}
}
// 有向图邻接矩阵表示
void createDirectedGraph(Graph* graph) {
int u, v;
// 输入边的信息，构建邻接矩阵
for (int i = 0; i < graph->edge; i++) {
scanf("%d %d", &u, &v);
graph->adjacencyMatrix[u][v] = 1;
}
}
// 打印邻接矩阵
void printGraph(Graph* graph) {
printf("Graph Adjacency Matrix:\n");
for (int i = 0; i < graph->vertices; i++) {
for (int j = 0; j < graph->vertices; j++) {
printf("%d ", graph->adjacencyMatrix[i][j]);
}
printf("\n");
}
}
int main() {
int vertices, edges;
// 输入顶点数和边数
scanf("%d %d", &vertices, &edges);
// 创建无向图并初始化邻接矩阵
Graph* undirectedGraph = CreateGraph(vertices, edges);
createUndirectedGraph(undirectedGraph);
// 创建有向图并初始化邻接矩阵
Graph* directedGraph = CreateGraph(vertices, edges);
createDirectedGraph(directedGraph);
// 打印邻接矩阵
printGraph(undirectedGraph);
printf("\n");
printGraph(directedGraph);
// 释放内存
freeGraph(undirectedGraph);
freeGraph(directedGraph);
return 0;
}
