图的生成算法

为了测试图的搜索算法、拓扑排序、关键路径、最小生成树、最短路径等算法，特意写了图的生成算法，包括以邻接表和邻接矩阵两种存储结构的图的生成算法。

1. 存储结构定义

/* headfiles/graph.h */#ifndef GRAPH_H_INCLUDED#define GRAPH_H_INCLUDED#include #define NUM 20//matrix graphtypedef struct { //邻接矩阵 int vexs[NUM]; //vertex vector, stores data of every vertex int arcs[NUM][NUM]; //adjMatrix arcs; int vexnum, arcnum;}MGraph;//ALGraphtypedef struct ArcNode { //邻接表 int adjvex; //无权图时，两节点连通adjvex=1，否则adjvex=0 struct ArcNode *nextarc; int cost; //有权图的代价，如距离等}ArcNode;typedef struct VNode { int data; ArcNode *firstarc;}VNode, adjList[NUM];typedef struct { adjList vertices; int vexnum, arcnum;}ALGraph;//for the minimum cost spanningtypedef struct { int adjvex; int lowcost;}Closedge;#endif // GRAPH_H_INCLUDED

设图有n个节点，则图的各个节点编号为V1, V2, ..., Vn， 节点为i（1<= i=""><=>

2. 图的以邻接表为存储结构的生成算法

首先输入图的节点个数，然后依次输入连通的两节点的编号及其代价，如：

V1和V3（V1->V3）连通，其代价为10，则输入为：1 3 10

以0 0 0 结束输入。

算法如下：

/*sharedSource/createGraph.c */void createGraph(ALGraph *G){ ArcNode *p, *q; int i, v1, v2, cost, num; printf('the number of vertexes: '); scanf('%d', &num); G->vexnum = num; for (i = 0;i < g-="">vexnum;i++) { G->vertices[i].data = i + 1; G->vertices[i].firstarc = NULL; } printf('vi vj cost:\n'); while (scanf('%d%d%d', &v1, &v2, &cost) == 3) { if (v1 <= 0="" ||="" v2=""><= 0)="" break;="" p="q" =="" g-="">vertices[v1 - 1].firstarc; while (p && v2 - 1 > p->adjvex) { q = p; p = p->nextarc; } p = (ArcNode *)malloc(sizeof(ArcNode)); p->adjvex = v2 - 1; p->cost = cost; //p->nextarc = NULL; if (! q || q == p) { //not if (! q || q == G->vertices[v1 - 1].firstarc) p->nextarc = G->vertices[v1 - 1].firstarc; G->vertices[v1 - 1].firstarc = p; } else { p->nextarc = q->nextarc; q->nextarc = p; } } //while //for debugging /* printf('\nstoring structure of the graph:\n'); for (i = 0;i < g-="">vexnum;i++) { q = G->vertices[i].firstarc; printf('V%d->: ', i + 1); while (q) { printf('V%d ', q->adjvex + 1); q = q->nextarc; } printf('\n'); } */}/**81 2 02 4 05 2 04 8 08 5 01 3 03 7 07 6 06 3 00 0 0*/

测试结果：

3. 图的以邻接矩阵为存储结构的生成算法

算法如下：

/* sharedSource/createMGraph.c */void createMGraph(MGraph *G) { int i, j, num, v1, v2, cost; printf('input the number of vertexes: '); scanf('%d', &num); G->vexnum = num; for (i = 0;i < g-="">vexnum;i++) { G->vexs[i] = i + 1; for (j = 0;j < g-="">vexnum;j++) G->arcs[i][j] = INT_MAX; } printf('vi vj cost:\n '); while (scanf('%d%d%d', &v1, &v2, &cost) == 3) { if (v1 <=0 ||="" v2=""><= 0)="" break;="" g-="">arcs[v1 - 1][v2 - 1] = cost; //G->arcs[v2 - 1][v1 - 1] = cost; } /* for (i = 0;i < g-="">vexnum;i++) { for(j = 0;j < g-="">vexnum;j++) printf('V%d,V%d=%d ', i + 1, j + 1, G->arcs[i][j]); printf('\n'); } */}/**61 2 61 3 11 4 52 3 52 5 33 4 53 6 43 5 64 6 25 6 60 0 0*/

输入规则同2.