图算法之图的最长路径

拼搏现实的明天。 2022-06-07 03:06 112阅读 0赞

来自UNSW的一个C语言大作业，滴滴滴滴滴滴

#include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    #include <assert.h>
    #include <stdbool.h>
    
    typedef struct GraphRep *Graph;
    
    // vertices are ints
    typedef int Vertex;
    
    // edges are pairs of vertices (end-points)
    typedef struct Edge {
        Vertex v;
        Vertex w;
    } Edge;
    
    typedef struct GraphRep {
        int  **edges;   // adjacency matrix
        int    nV;      // #vertices
        int    nE;      // #edges
    } GraphRep;
    
    bool found;
    
    Graph newGraph(int V) {
        assert(V >= 0);
        int i;
    
        Graph g = (Graph )malloc(sizeof(GraphRep));
    // Graph g = NULL;
        assert(g != NULL);
        g->nV = V;
        g->nE = 0;
    
        // allocate memory for each row
        g->edges =(int **) malloc(V * sizeof(int *));
        assert(g->edges != NULL);
        // allocate memory for each column and initialise with 0
        for (i = 0; i < V; i++) {
            g->edges[i] =(int *)calloc(V, sizeof(int));
            assert(g->edges[i] != NULL);
        }
    
        return g;
    }
    
    // check if vertex is valid in a graph
    bool validV(Graph g, Vertex v) {
        return (g != NULL && v >= 0 && v < g->nV);
    }
    
    void insertEdge(Graph g, Edge e) {
        assert(g != NULL && validV(g, e.v) && validV(g, e.w));
    
        if (!g->edges[e.v][e.w]) {  // edge e not in graph
            g->edges[e.v][e.w] = 1;
            // g->edges[e.w][e.v] = 1;
            g->nE++;
        }
    }
    
    
    void removeEdge(Graph g, Edge e) {
        assert(g != NULL && validV(g, e.v) && validV(g, e.w));
    
        if (g->edges[e.v][e.w]) {   // edge e in graph
            g->edges[e.v][e.w] = 0;
            g->edges[e.w][e.v] = 0;
            g->nE--;
        }
    }
    
    bool adjacent(Graph g, Vertex v, Vertex w) {
        assert(g != NULL && validV(g, v) && validV(g, w));
    
        return (g->edges[v][w] != 0);
    }
    
    void showGraph(Graph g, char** corpus) {
        assert(g != NULL);
        int i = 0, j = 0;
        for (i = 0; i < g->nV; i++){
            printf("%s: ", corpus[i]);
            for (j = 0; j < g->nV; j++){
                if (adjacent(g, i, j))
                    printf("%s ", corpus[j]);
            }
            printf("\n");
        }
        printf("\n");
    
    }
    
    void freeGraph(Graph g) {
        assert(g != NULL);
    
        int i;
        for (i = 0; i < g->nV; i++)
            free(g->edges[i]);
        free(g->edges);
        free(g);
    }
    
    
    
    void print_chain(Vertex v, Vertex const visited[], int size, char** corpus){
        //int print_arr[size];
        int print_arr[1000];
        int i = size - 1;
        while (v != visited[v]) {
            print_arr[i--] = v;
            v = visited[v];
        }
        print_arr[i] = v;
        printf("%s", corpus[print_arr[0]]);
        for (i = 1; i < size; i++)
            printf(" -> %s", corpus[print_arr[i]]);
        printf("\n");
    }
    
    void _longest_path(Graph g, Vertex prev, Vertex v, Vertex visited[], int current, int target, char** corpus){
        assert(visited[v] == -1);
        visited[v] = prev;
        if (current == target){
            if (!found) {
                found = true;
                printf("Maximum chain length: %d\n", target);
                printf("Maximal chains:\n");
            }
            print_chain(v, visited, current, corpus);
            return;
        }
        int w;
        for (w = 0; w < g->nV; w++)
        if (adjacent(g, v, w) && visited[w] == -1)
            _longest_path(g, v, w, visited, current + 1, target, corpus);
    
        visited[v] = -1;
    }
    
    void LongestPath(Graph g, char** corpus){
        found = false;
        //Vertex visited[g->nV];
        Vertex visited[1000];
        int i, v, max_dist;
        for (i = 0; i < g->nV; i++)
            visited[i] = -1;
    
        for (max_dist = g->nV; max_dist > 0; max_dist--) {
            if (found)
                return;
            for (v = 0; v < g->nV; v++)
            if (visited[v] == -1)
                _longest_path(g, v, v, visited, 1, max_dist, corpus);
        }
    
    }
    
    int CompareTwoWords(char word1[], char word2[]){
        int len1 = strlen(word1);
        int len2 = strlen(word2);
        if (abs((int)(len1-len2)) > 1){ //if more than two,prove false
            return 0;
        }
    
        //if equal
        if (len1 == len2){
            int pos = 0;
            int i;
            for (i = 0; i < len1; i++){
                if (word1[i] != word2[i]){
                    pos = i;
                    int j;
                    for (j = pos + 1; j < len1; j++){
                        if (word1[j] != word2[j]){
                            return 0;
                        }
                    }
                    break;
                }
            }
        }
    
        //if left for one char distance,for code length,deal with something
        else{
            char str_large[20], str_small[20];
            if (len1 > len2){
                strcpy(str_large, word1);
                strcpy(str_small, word2);
            }
            else if (len1 < len2){
                strcpy(str_large, word2);
                strcpy(str_small, word1);
            }
            int i;
            for (i = 0; i < strlen(str_small); i++){
                if (str_small[i] != str_large[i]){
                    int pos = i;
                    int j;
                    for (j = pos; j < strlen(str_small); j++){
                        if (str_small[j] != str_large[j + 1]){
                            return 0;
                        }
                    }
                    break;
                }
            }
        }
        return 1;
    }
    
    void init(){
        int n;
        char *s[1000];
        printf("Enter a num:");
        scanf("%d", &n);
        Graph Graph = newGraph(n);
        Edge e;
        getchar();
        int i;
        for (i = 0; i < n; i++){
            s[i] =(char *) malloc(sizeof(char)*20);
            printf("Enter word:");
            gets(s[i]);
        }
        int temp_count = 0;
        for (i = 0; i < n; i++){
            temp_count = i + 1;
            printf("%s: ", s[i]);
            while (temp_count != n){
                if (temp_count == i){
                    temp_count++;
                    continue;
                }
                if (CompareTwoWords(s[i], s[temp_count])){
                    printf("%s ", s[temp_count]);
                    //填充边
                    e.v = i;
                    e.w = temp_count;
                    insertEdge(Graph, e);
                }
                temp_count++;
            }
            printf("\n");
        }
        LongestPath(Graph, s);
    }
    
    int main()
    {
        init();
        system("pause");
        return 0;
    }