数据结构有向图c语言

数据结构中的有向图可以使用C语言来表示和处理。其中，Dijkstra算法和Floyd-Warshall算法是解决有向图上最短路径问题的常用方法。Dijkstra算法适用于求解带权重的有向图上的单源最短路径问题，要求图中所有边的权重非负。通过Dijkstra算法，可以找到给定起点到终点的最短路径。而Floyd-Warshall算法则是用于解决多源最短路径问题的，可以找到任意两个顶点之间的最短路径。

在C语言中，可以使用二维数组来表示有向图的邻接矩阵，并使用相应的算法来计算最短路径。通过遍历图中的顶点和边，可以根据算法的要求计算出最短路径，并将结果存储在相应的数据结构中。

相关问题

数据结构有向图的实现c语言

有向图可以用邻接表或邻接矩阵来实现。下面是邻接表的实现：

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

#define MAX_VERTEX_NUM 100    // 最大顶点数

// 边表结点
typedef struct EdgeNode {
    int adjvex;               // 邻接点下标
    struct EdgeNode *next;    // 指向下一个邻接点
} EdgeNode;

// 顶点表结点
typedef struct VertexNode {
    int data;                 // 顶点数据
    EdgeNode *firstedge;      // 指向第一个邻接点
} VertexNode;

// 邻接表
typedef struct {
    VertexNode adjlist[MAX_VERTEX_NUM];    // 顶点表
    int vertex_num;                        // 顶点数
    int edge_num;                          // 边数
} Graph;

// 初始化有向图
void InitGraph(Graph *G) {
    G->vertex_num = G->edge_num = 0;
    for (int i = 0; i < MAX_VERTEX_NUM; i++) {
        G->adjlist[i].firstedge = NULL;
    }
}

// 查找顶点位置
int LocateVex(Graph *G, int v) {
    for (int i = 0; i < G->vertex_num; i++) {
        if (G->adjlist[i].data == v) {
            return i;
        }
    }
    return -1;
}

// 添加顶点
void AddVertex(Graph *G, int v) {
    if (G->vertex_num == MAX_VERTEX_NUM) {
        printf("Error: Exceed the max vertex number!\n");
        return;
    }
    int pos = LocateVex(G, v);
    if (pos != -1) {
        printf("Vertex %d already exists!\n", v);
        return;
    }
    G->adjlist[G->vertex_num].data = v;
    G->adjlist[G->vertex_num].firstedge = NULL;
    G->vertex_num++;
}

// 添加边
void AddEdge(Graph *G, int v1, int v2) {
    int pos1 = LocateVex(G, v1);
    int pos2 = LocateVex(G, v2);
    if (pos1 == -1 || pos2 == -1) {
        printf("Error: Vertex does not exist!\n");
        return;
    }
    EdgeNode *p = G->adjlist[pos1].firstedge;
    while (p) {
        if (p->adjvex == pos2) {
            printf("Edge already exists!\n");
            return;
        }
        p = p->next;
    }
    EdgeNode *edge = (EdgeNode *)malloc(sizeof(EdgeNode));
    edge->adjvex = pos2;
    edge->next = G->adjlist[pos1].firstedge;
    G->adjlist[pos1].firstedge = edge;
    G->edge_num++;
}

// 输出有向图
void PrintGraph(Graph *G) {
    printf("Vertex number: %d\n", G->vertex_num);
    printf("Edge number: %d\n", G->edge_num);
    for (int i = 0; i < G->vertex_num; i++) {
        printf("%d: ", G->adjlist[i].data);
        EdgeNode *p = G->adjlist[i].firstedge;
        while (p) {
            printf("%d ", G->adjlist[p->adjvex].data);    // 打印邻接点数据
            p = p->next;
        }
        printf("\n");
    }
}

int main() {
    Graph G;
    InitGraph(&G);
    AddVertex(&G, 1);
    AddVertex(&G, 2);
    AddVertex(&G, 3);
    AddVertex(&G, 4);
    AddVertex(&G, 5);
    AddEdge(&G, 1, 2);
    AddEdge(&G, 1, 3);
    AddEdge(&G, 2, 4);
    AddEdge(&G, 3, 4);
    AddEdge(&G, 4, 5);
    PrintGraph(&G);
    return 0;
}

以上代码实现了有向图的基本操作：初始化图、添加顶点、添加边、输出图。你可以自己定义顶点数据类型和相应的操作函数，以满足不同的需求。

数据结构建立图c语言程序

以下是使用邻接矩阵和邻接表建立图的C语言示例程序：

1. 邻接矩阵实现：

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

#define MAXN 100
int matrix[MAXN][MAXN]; // 邻接矩阵
int n, m; // n为顶点数，m为边数

int main() {
    memset(matrix, 0, sizeof(matrix)); // 初始化邻接矩阵
    scanf("%d%d", &n, &m); // 输入顶点数和边数
    for (int i = 1; i <= m; ++i) {
        int u, v, w; // u和v为边的两个端点，w为边的权值
        scanf("%d%d%d", &u, &v, &w);
        matrix[u][v] = w; // 无向图的邻接矩阵是对称的，因此需要将两个方向都连上
        matrix[v][u] = w;
    }
    return 0;
}

2. 邻接表实现：

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

#define MAXN 100
struct Edge {
    int to, weight; // to为边的终点，weight为边的权值
    int next; // 下一条边的编号
} edges[MAXN * 2]; // 最多有n*(n-1)条边
int head[MAXN]; // head[i]表示以i为起点的第一条边的编号
int cnt = 0; // 记录边的数量
int n, m; // n为顶点数，m为边数

int main() {
    memset(head, -1, sizeof(head)); // 初始化邻接表
    scanf("%d%d", &n, &m); // 输入顶点数和边数
    for (int i = 1; i <= m; ++i) {
        int u, v, w; // u和v为边的两个端点，w为边的权值
        scanf("%d%d%d", &u, &v, &w);
        edges[cnt].to = v;
        edges[cnt].weight = w;
        edges[cnt].next = head[u];
        head[u] = cnt++;
        edges[cnt].to = u;
        edges[cnt].weight = w;
        edges[cnt].next = head[v];
        head[v] = cnt++;
    }
    return 0;
}

注意，上述代码只是用于演示如何使用邻接矩阵和邻接表建立图，实际应用中需要根据具体情况进行修改和优化。