按照连接两个顶点的边的不同，可以把图分为以下两种：
无向图：边仅仅连接两个顶点，没有其他含义；
有向图：边不仅连接两个顶点，并且具有方向；
相邻顶点：
当两个顶点通过一条边相连时，我们称这两个顶点是相邻的，并且称这条边依附于这两个顶点。
度：
某个顶点的度就是依附于该顶点的边的个数
子图：
是一幅图的所有边的子集(包含这些边依附的顶点)组成的图；
路径：
是由边顺序连接的一系列的顶点组成
环：
是一条至少含有一条边且终点和起点相同的路径
连通图：
如果图中任意一个顶点都存在一条路径到达另外一个顶点，那么这幅图就称之为连通图
连通子图：
一个非连通图由若干连通的部分组成，每一个连通的部分都可以称为该图的连通子图
所谓邻接矩阵存储结构就是用一维数组存储图中顶点的信息，用矩阵表示图中各顶点之间的邻接关系。
邻接矩阵存储结构最大的优点就是简单直观，易于理解和实现。其适用范围广泛，有向图、无向图、混合图、带权图等都可以直接用邻接矩阵表示。另外，对于很多操作，比如获取顶点度数，判断某两点之间是否有连边等，都可以在常数时间内完成。
然而，它的缺点也是显而易见的：从以上的例子我们可以看出，对于一个有 n 个顶点的图，邻接矩阵总是需要
n
2
n^2
n2 的存储空间。当边数很少的时候，就会造成空间的浪费。
邻接矩阵是一个由 1 和 0 构成的矩阵。处于第 i 行、第 j 列上的元素 1 和 0 分别代表顶点 i 到 j 之间存在或不存在一条又向边。
显然在构造邻接矩阵的时候，我们需要实现一个整形的二维数组。由于当前的图还是空的，因此我们还要把这个二维数组中的每个元素都初始化为 0。
在构造好了一个图的结构后，我们需要把图中各边的情况对应在邻接矩阵上。实际上，这一步的实现非常简单，当从顶点 x 到 y 上存在边时，我们只要把二维数组对应的位置置为 1 就好了。
另外，我们还要学习如何把存储好的图的邻接矩阵输出出来。可能同学们已经想到了，我们只要用两层 for 循环把这个二维数组的所有元素输出就好了。当然，为了使输出是一个邻接矩阵的形状，我们需要在每一次内循环结束时输出一个换行，并在输出每一个元素之后再输出一个空格。
#include邻接表#include #include #define MAX_N 500 typedef struct Graph { int mat[MAX_N][MAX_N]; int n; } Graph; void init(Graph *g, int n) { g->n = n; memset(g->mat, 0, sizeof(g->mat)); } void insert(Graph *g, int x, int y) { if(x < 0 || x >= g->n || y < 0 || y>= g->n ) { return ; } g->mat[x][y] = 1; } void output(Graph *g) { for(int i = 0; i < g->n; ++i) { for(int j =0; j < g->n; ++j) { printf("%d ", g->mat[i][j]); } printf("n"); } } int main() { int n, m, x, y; scanf("%d %d", &n, &m); Graph *graph = (Graph *)malloc(sizeof(Graph)); init(graph, n); for (int i = 0; i < m; ++i) { scanf("%d %d", &x, &y); insert(graph, x, y); } output(graph); free(graph); return 0; }
邻接表的的结构更像是由几个链表构成的。
在构造邻接表时，我们的确会借助链表的结构。对图中每个顶点的信息，我们都会分别使用一个链表来进行存储。因此，我们需要初始化一个有 n 个元素的链表数组， n 为图中顶点数量。
我们要在邻接表中存储的图的信息，实际上就是顶点之间存在的有向边。当从顶点 a 到顶点 b 存在一条有向边时，我们只需要在头结点为 a 的链表后插入一个结点 b。值得注意的是，当一条边是从顶点 b 到顶点 a 时，我们同样需要在以 b 为头结点的链表后插入一个结点 a。
同样在输出邻接表的时候，我们也只需要把每个链表依次遍历输出就好了。链表插入和输出的方法在第二章链表里已经学习过了，在这里我们就不再重复，那么接下来我们就来学习怎么实现邻接表吧。
#include邻接表的使用#include #include #define MAX_N 10000 typedef struct Node { int vertex; struct Node *next; } Node, *LinkedList; LinkedList insert_node(LinkedList head, int index) { Node *node = (Node *)malloc(sizeof(Node)); node->vertex = index; node->next = head; head = node; return head; } typedef struct Graph { LinkedList edges[MAX_N]; int n; } Graph; // 请在下面实现初始化函数 void init(Graph *g, int n) { g->n = n; for(int i = 0; i < g->n; ++i) { g->edges[i] = NULL; } } // 请在下面实现函数 clear void clear(Graph *g) { for(int i = 0; i < g->n; ++i) { Node *head = g->edges[i]; while (head != NULL) { Node *delete_node = head; head = head->next; free(delete_node); } } free(g); } int main() { Graph *graph = (Graph *) malloc(sizeof(Graph)); init(graph, 100); clear(graph); return 0; }
#include#include #include #define MAX_N 10000 typedef struct Node { int vertex; struct Node *next; } Node, *LinkedList; LinkedList insert_node(LinkedList head, int index) { Node *node = (Node *)malloc(sizeof(Node)); node->vertex = index; node->next = head; head = node; return head; } typedef struct Graph { LinkedList edges[MAX_N]; int n; } Graph; void init(Graph *g, int n) { g->n = n; for (int i = 0; i < g->n; ++i) { g->edges[i] = NULL; } } void insert(Graph *g, int x, int y) { if (x <0 || x>= g->n || y < 0 || y >= g->n ) { return ; } g->edges[x] = insert_node(g->edges[x], y); } void output(Graph *g) { for(int i = 0; i < g->n; ++i) { printf("%d:", i); for(Node *j = g->edges[i]; j != NULL; j= j->next){ printf("%d ", j->vertex); } printf("n"); } } void clear(Graph *g) { for (int i = 0; i < g->n; ++i) { Node *head = g->edges[i]; while (head != NULL) { Node *delete_node = head; head = head->next; free(delete_node); } } free(g); } int main() { int n, m, x, y; scanf("%d %d", &n, &m); Graph *graph = (Graph *)malloc(sizeof(Graph)); init(graph, n); for (int i = 0; i < m; ++i) { scanf("%d %d", &x, &y); insert(graph, x, y); } output(graph); clear(graph); return 0; }
