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

好的，以下是您所需要的C语言代码实现： 1. 建立有向图的邻接表： ```c #include <stdio.h> #include <stdlib.h> #define MAX_VERTEX_NUM 20 //最多顶点数 #define INF 32767 //表示无穷大 //邻接表节点结构体 typedef struct ArcNode{ int adjvex; //该弧所指向的顶点的位置 struct ArcNode *nextarc; //指向下一条弧的指针 int weight; //弧的权值 }ArcNode; //顶点信息结构体 typedef struct VNode{ char data; //顶点信息 ArcNode *firstarc; //指向第一条依附该顶点的弧的指针 }VNode, AdjList[MAX_VERTEX_NUM]; //邻接表结构体 typedef struct{ AdjList vertices; //邻接表 int vexnum, arcnum; //图的当前顶点数和弧数 }ALGraph; //创建有向图的邻接表 void CreateGraph(ALGraph *G) { printf("请输入有向图的顶点数和弧数：\n"); scanf("%d%d", &G->vexnum, &G->arcnum); getchar(); printf("请输入有向图的顶点信息：\n"); for(int i = 0; i < G->vexnum; i++){ printf("第%d个顶点：", i+1); scanf("%c", &G->vertices[i].data); getchar(); G->vertices[i].firstarc = NULL; //将指向第一条弧的指针初始化为NULL } printf("请输入每条弧的起点和终点（用空格隔开）：\n"); int i, j, w; ArcNode *p; for(int k = 0; k < G->arcnum; k++){ scanf("%d%d%d", &i, &j, &w); p = (ArcNode*)malloc(sizeof(ArcNode)); //创建一个节点 p->adjvex = j-1; p->weight = w; p->nextarc = G->vertices[i-1].firstarc; //将该节点插入到起点的链表头部 G->vertices[i-1].firstarc = p; } } ``` 2. 输出邻接表 ```c //输出有向图的邻接表 void PrintGraph(ALGraph G) { printf("该有向图的邻接表如下：\n"); for(int i = 0; i < G.vexnum; i++){ printf("%c -> ", G.vertices[i].data); ArcNode *p = G.vertices[i].firstarc; while(p != NULL){ printf("%c(%d) ", G.vertices[p->adjvex].data, p->weight); p = p->nextarc; } printf("\n"); } } ``` 3. 计算各顶点的度并输出 ```c //计算各顶点的度并输出 void PrintDegree(ALGraph G) { printf("该有向图各顶点的度如下：\n"); int inDegree[G.vexnum], outDegree[G.vexnum]; //初始化各顶点的度数 for(int i = 0; i < G.vexnum; i++){ inDegree[i] = 0; outDegree[i] = 0; } //遍历邻接表，计算各顶点的度数 for(int i = 0; i < G.vexnum; i++){ ArcNode *p = G.vertices[i].firstarc; while(p != NULL){ outDegree[i]++; //计算出度 inDegree[p->adjvex]++; //计算入度 p = p->nextarc; } } //输出各顶点的度数 for(int i = 0; i < G.vexnum; i++){ printf("%c的入度为%d，出度为%d\n", G.vertices[i].data, inDegree[i], outDegree[i]); } } ``` 4. 实现拓扑排序 ```c //拓扑排序 int TopologicalSort(ALGraph G, int *t) { int *inDegree = (int*)malloc(G.vexnum*sizeof(int)); //定义数组存储各顶点的入度 for(int i = 0; i < G.vexnum; i++){ inDegree[i] = 0; //初始化各顶点的入度为0 } //遍历邻接表，计算各顶点的入度 for(int i = 0; i < G.vexnum; i++){ ArcNode *p = G.vertices[i].firstarc; while(p != NULL){ inDegree[p->adjvex]++; //计算各顶点的入度 p = p->nextarc; } } int stack[MAX_VERTEX_NUM], top = -1; //定义栈 //将所有入度为0的顶点入栈 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--]; //取出栈顶元素 t[count++] = i; //将该顶点加入拓扑序列中 ArcNode *p = G.vertices[i].firstarc; while(p != NULL){ //将该顶点的所有邻接点的入度减1 if(--inDegree[p->adjvex] == 0){ stack[++top] = p->adjvex; } p = p->nextarc; } } free(inDegree); if(count < G.vexnum){ //图中存在环 return -1; } else{ //拓扑排序成功 return 0; } } ``` 5. 输出单源点到其它顶点的最短路径（采用邻接矩阵存储） ```c #include <stdio.h> #include <stdlib.h> #define MAX_VERTEX_NUM 20 //最多顶点数 #define INF 32767 //表示无穷大 //邻接矩阵结构体 typedef struct{ char vexs[MAX_VERTEX_NUM]; //顶点信息 int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵 int vexnum, arcnum; //图的当前顶点数和弧数 }AMGraph; //创建有向图的邻接矩阵 void CreateGraph(AMGraph *G) { printf("请输入有向图的顶点数和弧数：\n"); scanf("%d%d", &G->vexnum, &G->arcnum); getchar(); printf("请输入有向图的顶点信息：\n"); for(int i = 0; i < G->vexnum; i++){ printf("第%d个顶点：", i+1); scanf("%c", &G->vexs[i]); getchar(); } //初始化邻接矩阵 for(int i = 0; i < G->vexnum; i++){ for(int j = 0; j < G->vexnum; j++){ G->arcs[i][j] = INF; } } printf("请输入每条弧的起点、终点和权值（用空格隔开）：\n"); int i, j, w; for(int k = 0; k < G->arcnum; k++){ scanf("%d%d%d", &i, &j, &w); G->arcs[i-1][j-1] = w; } } //Dijkstra算法求单源点到其它顶点的最短路径 void ShortestPath_Dijkstra(AMGraph G, int v, int *dist) { int visited[MAX_VERTEX_NUM]; //标记各顶点是否已经求得最短路径 for(int i = 0; i < G.vexnum; i++){ dist[i] = G.arcs[v][i]; //初始化距离数组 visited[i] = 0; //标记数组初始化 } dist[v] = 0; //源点到自己的距离为0 visited[v] = 1; //源点已经求得最短路径 for(int i = 1; i < G.vexnum; i++){ //执行n-1次循环 int minDist = INF, u; for(int j = 0; j < G.vexnum; j++){ //找到距离源点最近的顶点 if(!visited[j] && dist[j] < minDist){ minDist = dist[j]; u = j; } } visited[u] = 1; //将距离源点最近的顶点标记为已经求得最短路径 for(int k = 0; k < G.vexnum; k++){ //更新各顶点的最短路径 if(!visited[k] && G.arcs[u][k] < INF && dist[u] + G.arcs[u][k] < dist[k]){ dist[k] = dist[u] + G.arcs[u][k]; } } } } //输出单源点到其它顶点的最短路径 void PrintShortestPath(AMGraph G, int v, int *dist) { printf("从%c出发，到各顶点的最短路径如下：\n", G.vexs[v]); for(int i = 0; i < G.vexnum; i++){ if(dist[i] == INF){ printf("从%c到%c不存在路径\n", G.vexs[v], G.vexs[i]); } else{ printf("从%c到%c的最短路径长度为%d\n", G.vexs[v], G.vexs[i], dist[i]); } } } ```