图算法——Hamilton Path

    下面代码是求图中Hamilton path的算法。

graph.h

 

typedef struct
{
        int v;
        int w;
}Edge;

Edge EDGE(int, int);

typedef struct graph *Graph;

Graph graphinit(int);

int graphinserte(Graph, Edge);

void graphremovee(Graph, Edge);

Graph graphcopy(Graph);

void graphdestroy(Graph);

void graphshow(Graph);


graph.c

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

struct graph
{
        int v;
        int e;
        int **adj;
};

Edge EDGE(int v, int w)
{
        Edge e;
        e.v = v;
        e.w = w;

        return e;
}

int **matrixint(int r, int c, int val)
{
        int i, j;

        int **t = (int**)malloc(r * sizeof(int*));
        if (t == NULL)
                return NULL;
        for (i = 0; i < r; i++)
        {
                t[i] = (int*)malloc(c * sizeof(int));
                if (t[i] == NULL)
                {
                        while (--i >= 0)
                                free(t[i]);
                        return NULL;
                }
        }

        for (i = 0; i < r; i++)
                for (j = 0; j < c; j++)
                        t[i][j] = val;
        return t;
}

Graph graphinit(int v)
{
        Graph g;

        g = (Graph)malloc(sizeof(*g));
        g->v = v;
        g->e = 0;
        g->adj = matrixint(v, v, 0);

        return g;
}

int graphinserte(Graph g, Edge e)
{
        int v = e.v;
        int w = e.w;

        if (g->adj[v][w] == 0)
                g->e++;
        g->adj[v][w] = 1;
        g->adj[w][v] = 1;
        return 0;
}

void graphremovee(Graph g, Edge e)
{
        int v = e.v;
        int w = e.w;

        if (g->adj[v][w] == 1)
                g->e--;
        g->adj[v][w] = 0;
        g->adj[w][v] = 0;
}

void graphshow(Graph g)
{
        int i, j;
        printf("%d vertices, %d edges\n", g->v, g->e);

        for (i = 0; i < g->v; i++)
        {
                printf("%2d: ", i);
                for (j = 0; j < g->v; j++)
                        if (g->adj[i][j] == 1)
                                printf(" %2d", j);
                printf("\n");
        }
}

void graphdestroy(Graph g)
{
        int i;

        for (i = 0; i < g->v; i++)
                free(g->adj[i]);
        free(g->adj);
}



hamilton.c

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

struct graph
{
        int v;
        int e;
        int **adj;
};

int pathH(Graph g, int v, int w, int d, int *visited)
{
        int t;
        if (v == w)
        {
                if (d == 0)
                        return 1;
                else
                        return 0;
        }
        visited[v] = 1;
        for (t = 0; t < g->v; t++)
                if (g->adj[v][t] == 1)
                        if (visited[t] == 0)
                                if (pathH(g, t, w, d-1, visited))
                                {
                                        printf(" %d - %d ", t, v);
                                        return 1;
                                }
        visited[v] = 0;
        return 0;
}

int graphpathh(Graph g, int v, int w)
{
        int t;
        int i, j;
        int *visited;

        visited = (int*)malloc(sizeof(int) * g->v);
        for (t = 0; t < g->v; t++)
                visited[t] = 0;

        if (v != w)
                return pathH(g, v, w, g->v - 1, visited);
        else
        {
                for (t = 0; t < g->v; t++)
                        if (g->adj[v][t] == 1)
                                if (pathH(g, t, v, g->v - 1, visited))
                                        return 1;
                return 0;
        }
}


main.c

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

int main()
{
        Graph g;
        int i, j;
        int ver = 7;
        int v1, v2;

        Edge e1[] = {{0, 1},{0, 2}, {0, 5}, {0, 6}, {1, 2}, {2, 3}, {2, 4}, {3, 4}, {4, 5}, {4, 6}};
        Edge e2[] = {{1, 3}, {3, 5}, {0, 1},{0, 2}, {0, 5}, {0, 6}, {1, 2}, {2, 3}, {2, 4}, {3, 4}, {4, 5}, {4, 6}};
        j = sizeof(e1) / sizeof(e1[0]);

        g = graphinit(ver);
        if (g == NULL)
        {
                printf("init graph error\n");
                exit(1);
        }


        for (i = 0; i < j; i++)
                if (graphinserte(g, e1[i]) < 0)
                {
                        printf("insert error\n");
                        break;
                }

        graphshow(g);

        scanf("%d %d", &v1, &v2);
        if (graphpathh(g, v1, v2))
        {
                printf("\n%d-%d has path\n", v1, v2);
        }
        else
        {
                printf("%d-%d has no path\n", v1, v2);
        }

        graphdestroy(g);

        j = sizeof(e2) / sizeof(e2[0]);

        g = graphinit(ver);
        if (g == NULL)
        {
                printf("init graph error\n");
                exit(1);
        }


        for (i = 0; i < j; i++)
                if (graphinserte(g, e2[i]) < 0)
                {
                        printf("insert error\n");
                        break;
                }

        graphshow(g);

        scanf("%d %d", &v1, &v2);
        if (graphpathh(g, v1, v2))
        {
                printf("\n%d-%d has path\n", v1, v2);
        }
        else
        {
                printf("%d-%d has no path\n", v1, v2);
        }

        graphdestroy(g);

        return 0;
}


 

gcc -Wall main.c graph.c hamilton.c -o main

./main