图- 数据结构(c语言)

图的分类

按照连接两个顶点的边的不同，可以把图分为以下两种：
无向图：边仅仅连接两个顶点，没有其他含义；
有向图：边不仅连接两个顶点，并且具有方向；

图的相关术语

相邻顶点：
当两个顶点通过一条边相连时，我们称这两个顶点是相邻的，并且称这条边依附于这两个顶点。
度：
某个顶点的度就是依附于该顶点的边的个数
子图：
是一幅图的所有边的子集(包含这些边依附的顶点)组成的图；
路径：
是由边顺序连接的一系列的顶点组成
环：
是一条至少含有一条边且终点和起点相同的路径

连通图：
如果图中任意一个顶点都存在一条路径到达另外一个顶点，那么这幅图就称之为连通图

连通子图：
一个非连通图由若干连通的部分组成，每一个连通的部分都可以称为该图的连通子图

邻接矩阵

所谓邻接矩阵存储结构就是用一维数组存储图中顶点的信息，用矩阵表示图中各顶点之间的邻接关系。

邻接矩阵存储结构最大的优点就是简单直观，易于理解和实现。其适用范围广泛，有向图、无向图、混合图、带权图等都可以直接用邻接矩阵表示。另外，对于很多操作，比如获取顶点度数，判断某两点之间是否有连边等，都可以在常数时间内完成。
然而，它的缺点也是显而易见的：从以上的例子我们可以看出，对于一个有 n 个顶点的图，邻接矩阵总是需要

n

2

n^2

n2 的存储空间。当边数很少的时候，就会造成空间的浪费。

邻接矩阵的实现

邻接矩阵是一个由 1 和 0 构成的矩阵。处于第 i 行、第 j 列上的元素 1 和 0 分别代表顶点 i 到 j 之间存在或不存在一条又向边。
显然在构造邻接矩阵的时候，我们需要实现一个整形的二维数组。由于当前的图还是空的，因此我们还要把这个二维数组中的每个元素都初始化为 0。

在构造好了一个图的结构后，我们需要把图中各边的情况对应在邻接矩阵上。实际上，这一步的实现非常简单，当从顶点 x 到 y 上存在边时，我们只要把二维数组对应的位置置为 1 就好了。

另外，我们还要学习如何把存储好的图的邻接矩阵输出出来。可能同学们已经想到了，我们只要用两层 for 循环把这个二维数组的所有元素输出就好了。当然，为了使输出是一个邻接矩阵的形状，我们需要在每一次内循环结束时输出一个换行，并在输出每一个元素之后再输出一个空格。

邻接矩阵的实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#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 <stdio.h>
#include <stdlib.h>
#include <string.h>

#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 <stdio.h>
#include <stdlib.h>
#include <string.h>

#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;
}