1．键盘输入数据，建立一个有向图的邻接表。 2．输出该邻接表。 3．在有向图的邻接表的基础上计算各顶点的度，并输出。 4．以有向图的邻接表为基础实现输出它的拓扑排序序列。 5．采用邻接矩阵存储一个有向图，输出单源点到其它顶点的最短路径。

1. 建立有向图的邻接表

首先需要定义有向图的结构体，包括顶点和边的信息：

#define MAX_VERTEX_NUM 20    // 最多顶点个数
typedef struct ArcNode {     // 边结构体
    int adjvex;             // 邻接点
    struct ArcNode *next;   // 指向下一条边的指针
} ArcNode;
typedef struct VNode {       // 顶点结构体
    int data;               // 顶点信息
    ArcNode *first;         // 指向第一条边的指针
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {            // 邻接表结构体
    AdjList vertices;       // 顶点数组
    int vexnum, arcnum;     // 顶点数和边数
} ALGraph;

然后，根据用户输入的数据建立邻接表：

void CreateGraph(ALGraph *G) {
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    printf("请输入顶点信息：");
    for (int i = 0; i < G->vexnum; i++) {
        scanf("%d", &G->vertices[i].data);
        G->vertices[i].first = NULL;
    }
    printf("请输入每条边的起点和终点：");
    for (int i = 0; i < G->arcnum; i++) {
        int v1, v2;
        scanf("%d%d", &v1, &v2);
        ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = v2;
        p->next = G->vertices[v1].first;
        G->vertices[v1].first = p;
    }
}

2. 输出邻接表

void PrintGraph(ALGraph G) {
    printf("邻接表：\n");
    for (int i = 0; i < G.vexnum; i++) {
        printf("%d -> ", G.vertices[i].data);
        ArcNode *p = G.vertices[i].first;
        while (p != NULL) {
            printf("%d ", G.vertices[p->adjvex].data);
            p = p->next;
        }
        printf("\n");
    }
}

3. 计算各顶点的度并输出

void PrintDegree(ALGraph G) {
    int inDegree[MAX_VERTEX_NUM] = {0};     // 入度数组
    int outDegree[MAX_VERTEX_NUM] = {0};    // 出度数组
    for (int i = 0; i < G.vexnum; i++) {
        ArcNode *p = G.vertices[i].first;
        while (p != NULL) {
            outDegree[i]++;
            inDegree[p->adjvex]++;
            p = p->next;
        }
    }
    printf("各顶点的度：\n");
    for (int i = 0; i < G.vexnum; i++) {
        printf("%d号顶点的入度为%d，出度为%d\n", i, inDegree[i], outDegree[i]);
    }
}

4. 输出拓扑排序序列

拓扑排序是对有向无环图的所有顶点进行排序的一种算法。一般情况下，拓扑排序序列可以有多个，但是对于同一个有向无环图，它的拓扑排序序列是唯一的。

int TopologicalSort(ALGraph G, int *sorted) {
    int inDegree[MAX_VERTEX_NUM] = {0};     // 入度数组
    for (int i = 0; i < G.vexnum; i++) {
        ArcNode *p = G.vertices[i].first;
        while (p != NULL) {
            inDegree[p->adjvex]++;
            p = p->next;
        }
    }
    int stack[MAX_VERTEX_NUM];              // 栈
    int top = -1;                           // 栈顶指针
    for (int i = 0; i < G.vexnum; i++) {
        if (inDegree[i] == 0) {
            stack[++top] = i;
        }
    }
    int count = 0;                          // 统计输出的顶点数
    while (top != -1) {
        int i = stack[top--];
        sorted[count++] = i;
        ArcNode *p = G.vertices[i].first;
        while (p != NULL) {
            if (--inDegree[p->adjvex] == 0) {
                stack[++top] = p->adjvex;
            }
            p = p->next;
        }
    }
    if (count < G.vexnum) {
        return 0;                           // 存在环路，拓扑排序失败
    } else {
        return 1;                           // 拓扑排序成功
    }
}

5. 输出单源点到其它顶点的最短路径

采用邻接矩阵存储一个有向图，实现深度优先搜索算法：

void DFS(ALGraph G, int v, int *visited) {
    visited[v] = 1;
    printf("%d ", G.vertices[v].data);
    ArcNode *p = G.vertices[v].first;
    while (p != NULL) {
        if (visited[p->adjvex] == 0) {
            DFS(G, p->adjvex, visited);
        }
        p = p->next;
    }
}

void DFSTraverse(ALGraph G) {
    int visited[MAX_VERTEX_NUM] = {0};
    printf("深度优先搜索序列：");
    for (int i = 0; i < G.vexnum; i++) {
        if (visited[i] == 0) {
            DFS(G, i, visited);
        }
    }
    printf("\n");
}