图

有向图、无向图、加权有向图

度，连接一个节点的边数。有向图有入度和出度。

关于图的连通性，无向图任何两个点都可以到达称为连通图。如果图看起来有两个部分，即有两个节点到不了，为非连通图。

强连通图是有向图的概念，有向图中任意两个节点可以到达。

图的构造。即如何用代码来实现一个图。

• 邻接表、邻接矩阵

邻接矩阵用二维数组来表示图结构，有多少节点就申请多大的二维数组。如 grid[2][5] = 3 表示节点 2 和节点 5 连接，权值为 6。

这种表达方式（邻接矩阵） 在 边少，节点多的情况下，会导致申请过大的二维数组，造成空间浪费。

而且在寻找节点连接情况的时候，需要遍历整个矩阵，即 n * n 的时间复杂度，同样造成时间浪费。

邻接矩阵的优点

• 表达方式简单，易于理解

• 检查任意两个顶点间是否存在边的操作非常快

• 适合稠密图，在边数接近顶点数平方的图中，邻接矩阵是一种空间效率较高的表示方法。

邻接表使用数组+链表来表示。

图的遍历，dfs，bfs。

有向图的遍历

图连接关系的表示

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

int **result;
int result_len; /* 结果的数量 */

int *single_out;
int single_len; /* 单个结果，路径长度 */

int *result_col_len; /* 存放每个路径长度的数组 */

int node_total_num;

int *node_connect_nums;

void dfs(int **graph, int start_node)
{
    // 当前节点已经是最后一个节点了
    if (start_node == node_total_num - 1)
    {
        //保存

        for (int i=0; i<single_len; i++)
        {
            result[result_len][i] = single_out[i];
        }

        result_col_len[result_len] = single_len;
        result_len++;

        return;
    }

    // 本层节点，
    for (int i=0; i<node_connect_nums[start_node]; i++)
    {
        int next = graph[start_node][i];  /* 检查空 */

        single_out[single_len] = next;
        single_len++;

        dfs(graph, next);

        single_len--;
    }
}

int** allPathsSourceTarget(int** graph, int graphSize, int* graphColSize, int* returnSize, int** returnColumnSizes) {

    /* 结果内存分配 */
    result = (int **)malloc(7000 * sizeof(int *));    /* result[i] 为一个指针，咨询函一个int型数组，为结果预留 50 个空间 */

    for (int i=0; i<7000; i++)
    {
        result[i] = (int *)malloc(15 * sizeof(int));     /* result[i] 指向一个长度等于节点数的内存 */
    }

    single_out = (int *)malloc(15 * sizeof(int));        /* 保存单次输出的结构 */

    result_col_len = (int *)malloc(7000 * sizeof(int));           /* 存放单次输出的结果的长度 */

    result_len = 0;
    single_len = 0;
    node_total_num = graphSize;
    node_connect_nums = graphColSize;

    single_out[single_len] = 0;
    single_len++;

    dfs(graph, 0);

    *returnSize = result_len;
    *returnColumnSizes = result_col_len;

    return result;
}

#include <stdio.h>

int *result; int result_len; / 结果的数量 */

int single_out; int single_len; / 单个结果，路径长度 */

int result_col_len; / 存放每个路径长度的数组 */

int node_total_num;

int *node_connect_nums;

void dfs(int **graph, int start_node) { // 当前节点已经是最后一个节点了 if (start_node == node_total_num) { //保存

    for (int i=0; i<single_len; i++)
    {
        result[result_len][i] = single_out[i];
    }

    result_col_len[result_len] = single_len;
    result_len++;

    return;
}

// 本层节点，
for (int i=0; i<node_connect_nums[start_node]; i++)
{
    int next = graph[start_node][i];  /* 检查空 */

    single_out[single_len] = next;
    single_len++;

    dfs(graph, next);

    single_len--;
}

}

int** allPathsSourceTarget(int** graph, int graphSize, int* graphColSize, int* returnSize, int** returnColumnSizes) {

/* 结果内存分配 */
result = (int **)malloc(7000 * sizeof(int *));    /* result[i] 为一个指针，咨询函一个int型数组，为结果预留 50 个空间 */

for (int i=0; i<7000; i++)
{
    result[i] = (int *)malloc(15 * sizeof(int));     /* result[i] 指向一个长度等于节点数的内存 */
}

single_out = (int *)malloc(15 * sizeof(int));        /* 保存单次输出的结构 */

result_col_len = (int *)malloc(7000 * sizeof(int));           /* 存放单次输出的结果的长度 */

result_len = 0;
single_len = 0;
node_total_num = graphSize;
node_connect_nums = graphColSize;

single_out[single_len] = 1;
single_len++;

dfs(graph, 1);

*returnSize = result_len;
*returnColumnSizes = result_col_len;

return result;

}

int main() { int node_nums, route_nums; scanf("%d %d", &node_nums, &route_nums);

// printf("%d %d\n",node_nums, route_nums);


int graph_size = node_nums;

int graph_col_size[node_nums];
for (int i=0; i<node_nums; i++)
    graph_col_size[i] = 0;


int graph[node_nums][node_nums];

for (int i=0; i<route_nums; i++)
{
    int a,b;
    scanf("%d %d", &a, &b);
    
    graph[a][graph_col_size[a]] = b;
    graph_col_size[a]++;
}


int **ret;
int return_size;
int *return_col_size;

ret = allPathsSourceTarget(graph, graph_size, graph_col_size, &return_size, &return_col_size);


/* 调试图的存储 */
for (int i=0; i<return_size; i++)
{
    for(int j=0; j<return_col_size[i]; j++)
    {
        printf("%d ", ret[i][j]);
    }
    printf("\n");    
}

/* 调试图的存储 */
for (int i=0; i<node_nums; i++)
{
    for(int j=0; j<graph_col_size[i]; j++)
    {
        printf("%d ", graph[i][j]);
    }
    printf("\n");
}

}