|
為了測(cè)試圖的搜索算法、拓?fù)渑判?/a>、關(guān)鍵路徑、最小生成樹、最短路徑等算法，特意寫了圖的生成算法，包括以鄰接表和鄰接矩陣兩種存儲(chǔ)結(jié)構(gòu)的圖的生成算法。 1. 存儲(chǔ)結(jié)構(gòu)定義 /* headfiles/graph.h */#ifndef GRAPH_H_INCLUDED#define GRAPH_H_INCLUDED#include 設(shè)圖有n個(gè)節(jié)點(diǎn)，則圖的各個(gè)節(jié)點(diǎn)編號(hào)為V1, V2, ..., Vn， 節(jié)點(diǎn)為i（1<= i=""><=> 2. 圖的以鄰接表為存儲(chǔ)結(jié)構(gòu)的生成算法 首先輸入圖的節(jié)點(diǎn)個(gè)數(shù)，然后依次輸入連通的兩節(jié)點(diǎn)的編號(hào)及其代價(jià)，如： V1和V3（V1->V3）連通，其代價(jià)為10，則輸入為：1 3 10 以0 0 0 結(jié)束輸入。 算法如下： /*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*/ 測(cè)試結(jié)果：
3. 圖的以鄰接矩陣為存儲(chǔ)結(jié)構(gòu)的生成算法 算法如下： /* 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*/ 輸入規(guī)則同2. |
|
|
