• 博客访问： 532782
• 博文数量： 54
• 博客积分： 3812
• 博客等级： 上校
• 技术积分： 992
• 用 户 组： 普通用户
• 注册时间： 2007-04-16 20:53

2010年（10）

2009年（24）

2008年（20）

2009-03-24 16:39:50

下面代码是求图中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 #include #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 #include #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 #include #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