c - 有向图：具有最大权重的（非简单）路径

Question

有向加权图通过其边列表保存在文件中，格式如下：v1 val v2，其中表示与权重（int > 0）的边v1相连。这是输入文件的示例v2val

fF 1 123
A0 2 fF
A0 5 h9
h9 3 123
123 2 F2
123 4 d1
F2 3 Dd
F2 4 d1
d1 2 Dd
d1 4 xd
d1 1 h9
Dd 5 xd
xd 4 A0
F2 3 fF

我必须编写一个 C 程序：

1. 读取文件并将图形保存在适当的数据结构中
2. 在接收到两个顶点v1和v2两个整数k和p(k<=p) 后，打印开始v1和结束的路径，v2其中尊重以下约束
   • 是最大的权重总和
   • 重新交叉至少 k 个顶点
   • 再交叉的合数至少为 p
   • 路径在到达目标顶点时结束

我解决了第一点，但我不知道第二点。这是我写的所有代码：

主程序

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

void main() {
    int k = 1, p = 1;
    char v1[21], v2[21];
    graph_t G = GRAPHread("file.txt");
    printf("Insert 2 vertex");
    scanf("%s %s", v1, v2);
    GRAPHfindPath(G, k, p, v1, v2);
}

边缘.h

#ifndef EDGE_H
#define EDGE_H

typedef struct edge_s { int v; int w; int wt; } edge_t;

edge_t EDGEcreate(int v, int w, int wt);

#endif

边缘.c

#include "edge.h"

edge_t EDGEcreate(int v, int w, int wt) {
    edge_t e;
    e.v = v;
    e.w = w;
    e.wt = wt;
    return e;
}

ST.h

#ifndef ST_H
#define ST_H

typedef struct symbletable_s *st_t;

int STinsert(st_t st, char *key);
int STsearch(st_t st, char *k);
st_t STinit(int maxN);

#endif

ST.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "ST.h"

struct symbletable_s { char **a; int M; };

st_t STinit(int maxN) {
    int i;
    st_t st = malloc(sizeof(*st));
    st->M = maxN;
    st->a = malloc(sizeof(char *)*st->M);
    return st;
}

int hash(char *k, int M) {
    int h = 0, base = 127;
    for (; *k != '\0'; k++) h = (base*h + *k) % M;
    return h;
}

int full(st_t st, int i) {
    if (st->a[i] == NULL) return 1;
    return 0;
}

int STinsert(st_t st, char *key) {
    int i = hash(key, st->M);
    while (full(st,i))
        i = (i + 1) % st->M;
    st->a[i] = malloc(sizeof(char)*(strlen(key) + 1));
    memcpy(st->a[i], key, strlen(key) + 1);
    return i;
}

int STsearch(st_t st, char *k) {
    int i = hash(k, st->M);
    while (full(st, i)) {
        if (strcmp(k, st->a[i]) == 0) return i;
        else i = (i + 1) % st->M;
    }
    return -1;
}

图.h

#ifndef GRAPH_H
#define GRAPH_H

typedef struct graph_s *graph_t;

graph_t GRAPHread(char *s);
void GRAPHfindPath(graph_t G, int k, int p, char *v1, char *v2);


#endif

图.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "graph.h"
#include "ST.h"
#include "edge.h"

#define MAX 21

typedef struct node_s *link;
struct node_s { int v; int wt; link next; };

struct graph_s {
    int V;
    int E;
    link *adj_l;
    link z;
    st_t tab;
};

link NEW(int v, int wt, link next) {
    link x = malloc(sizeof *x);
    x->v = v;
    x->next = next;
    x->wt = wt;
    return x;
}

graph_t GRAPHinit(int V) {
    int v;
    graph_t G = malloc(sizeof *G);
    G->V = V; G->E = 0; G->z = NEW(-1, -1, NULL);
    G->adj_l = malloc(G->V*sizeof(link));
    for (v = 0; v < G->V; v++)
        G->adj_l[v] = G->z;
    G->tab = STinit(V);
    return G;
}

void insertE(graph_t G, edge_t e) {
    int v = e.v, w = e.w, wt = e.wt;
    G->adj_l[v] = NEW(w, wt, G->adj_l[v]);
    G->adj_l[w] = NEW(v, wt, G->adj_l[w]);
    G->E++;
}

graph_t GRAPHread(char *s) {
    graph_t G;
    char src[MAX], dst[MAX];
    char v1[MAX], v2[MAX];
    int nE = 0, i, i1, i2, wt;
    FILE *fp = fopen(s, "r");
    while (fscanf(fp, "%*s %*d %*s") != EOF)
        nE++;
    rewind(fp);
    G = GRAPHinit(nE * 2);
    for (i = 0; i < nE; i++) {
        fscanf(fp, "%s %d %s", src, &wt, dst);
        i1 = STinsert(G->tab, src);
        i2 = STinsert(G->tab, dst);
        insertE(G, EDGEcreate(i1, i2, wt));
    }
    fclose(fp);
    return G;
}

void GRAPHfindPath(graph_t G, int k, int p, char *v1, char *v2) {

}

标签： cgraphgraph-algorithm