c语言求有向图中任意两个节点的所有简单路径

对于有向图中任意两个节点的所有简单路径，可以使用深度优先搜索算法（DFS）来实现。具体步骤如下：

1. 定义一个二维数组path，用于存储所有从起点到终点的简单路径；
2. 定义一个栈stack，用于存储当前路径上的节点；
3. 定义一个visited数组，用于存储节点是否已经被访问过；
4. 对于起点和终点，将visited数组中对应的位置标记为已访问；
5. 对于起点，将其入栈；
6. 对于栈顶元素，遍历其所有未访问的邻居节点，如果邻居节点是终点，则将当前路径保存到path数组中，否则将邻居节点入栈，并将visited数组中对应位置标记为已访问；
7. 当栈为空时，搜索结束，返回path数组。

下面是代码实现：

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

#define MAX_VERTEX_NUM 100

typedef struct ArcNode {
    int adjvex;             // 邻接点在顶点数组中的下标
    struct ArcNode *nextarc;    // 指向下一个邻接点的指针
} ArcNode;

typedef struct VNode {
    int data;               // 顶点数据
    ArcNode *firstarc;          // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;           // 图的顶点数组
    int vexnum, arcnum;         // 顶点数和弧数
} ALGraph;

void CreateGraph(ALGraph *G) {
    int i, j, k;
    ArcNode *p;
    printf("请输入顶点数和弧数:\n");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    printf("请依次输入各个顶点的数据:\n");
    for (i = 0; i < G->vexnum; i++) {
        scanf("%d", &G->vertices[i].data);
        G->vertices[i].firstarc = NULL;
    }
    printf("请依次输入各个弧的起点和终点:\n");
    for (k = 0; k < G->arcnum; k++) {
        scanf("%d%d", &i, &j);
        p = (ArcNode *) malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->nextarc = G->vertices[i].firstarc;
        G->vertices[i].firstarc = p;
    }
}

void DFS(ALGraph *G, int start, int end, int *visited, int *stack, int top, int **path, int *count) {
    int i;
    visited[start] = 1;
    stack[++top] = start;
    if (start == end) {
        for (i = 0; i <= top; i++) {
            path[*count][i] = stack[i];
        }
        (*count)++;
    } else {
        ArcNode *p = G->vertices[start].firstarc;
        while (p != NULL) {
            if (!visited[p->adjvex]) {
                DFS(G, p->adjvex, end, visited, stack, top, path, count);
            }
            p = p->nextarc;
        }
    }
    visited[start] = 0;
    top--;
}

int **AllPaths(ALGraph *G, int start, int end, int *pathCount) {
    int i, *visited, *stack, **path, count = 0;
    visited = (int *) calloc(G->vexnum, sizeof(int));
    stack = (int *) malloc(G->vexnum * sizeof(int));
    path = (int **) malloc(G->vexnum * G->vexnum * sizeof(int *));
    for (i = 0; i < G->vexnum * G->vexnum; i++) {
        path[i] = (int *) malloc(G->vexnum * sizeof(int));
    }
    DFS(G, start, end, visited, stack, -1, path, &count);
    *pathCount = count;
    free(visited);
    free(stack);
    return path;
}

int main() {
    int i, j, **path, pathCount;
    ALGraph G;
    CreateGraph(&G);
    path = AllPaths(&G, 0, 4, &pathCount);
    for (i = 0; i < pathCount; i++) {
        for (j = 0; j < G.vexnum; j++) {
            if (path[i][j] != -1) {
                printf("%d ", path[i][j]);
            }
        }
        printf("\n");
    }
    return 0;
}

注意，上述代码中的path数组中，每一行保存的是一条从起点到终点的简单路径，如果某一行中第i个元素为-1，则表示该行只包含i个有效元素，后面的元素均为无效元素。例如，path[0]={0,1,3,4,-1,-1,-1,-1,...}表示从结点0到结点4的一条简单路径，路径上依次经过结点0、1、3、4。