C說話完成圖的遍歷之深度優先搜刮實例。本站提示廣大學習愛好者:(C說話完成圖的遍歷之深度優先搜刮實例)文章只能為提供參考,不一定能成為您想要的結果。以下是C說話完成圖的遍歷之深度優先搜刮實例正文
DFS(Depth-First-Search)深度優先搜刮算法是圖的遍歷算法中異常罕見的一類算法。分享給年夜家供年夜家參考。詳細辦法以下:
#include <iostream> #include <algorithm> #include <iterator> using namespace std; #define MAX_VERTEX_NUM 10 struct Node { int adjvex; struct Node *next; int info; }; typedef struct VNode { char data; Node *first; }VNode, AdjList[MAX_VERTEX_NUM]; struct Graph { AdjList vertices; int vexnum, arcnum; }; int visited[MAX_VERTEX_NUM]; int locateVex(Graph G, char u) { int i; for (i = 0; i < G.vexnum; i++) { if (u == G.vertices[i].data) return i; } if (i == G.vexnum) { printf("Error u!\n"); exit(1); } return 0; } void createGraph(Graph &G) { int i, j, k, w; char v1, v2, enter; Node *p; printf("input vexnum & arcnum:\n"); scanf("%d", &G.vexnum); scanf("%d", &G.arcnum); printf("input vertices:\n"); for (i = 0; i < G.vexnum; i++) { scanf("%c%c", &enter, &G.vertices[i].data); G.vertices[i].first = NULL; } printf("input Arcs(v1, v2, w):\n"); for (k = 0; k < G.arcnum; k++) { scanf("%c%c", &enter, &v1); scanf("%c%c", &enter, &v2); scanf("%d", &w); i = locateVex(G, v1); j = locateVex(G, v2); p = (Node *)malloc(sizeof(Node)); p->adjvex = j; p->info = w; p->next = G.vertices[i].first; G.vertices[i].first = p; } } void DFS(Graph &G, int v) { Node *p; printf("%c", G.vertices[v].data); visited[v] = 1; p = G.vertices[v].first; while (p) { if (!visited[p->adjvex]) DFS(G, p->adjvex); p = p->next; } } void DFSTranverse(Graph &G) { for (int v = 0; v < G.vexnum; v++) visited[v] = 0; for (int v = 0; v < G.vexnum; v++) { if (!visited[v]) DFS(G, v); } } int main() { Graph G; createGraph(G); DFSTranverse(G); }
再換一種方法來寫DFS。詳細代碼以下:
#include <iostream> #include <string> using namespace std; #define MAXLEN 10 struct Node { int data; Node *next; }; struct Link { int count; string name; Node *head; }; struct Graph { Link link[MAXLEN]; int vexnum; int arcnum; }; int findIndex(Graph &G, string name) { int index = -1; for (int i = 0; i < G.vexnum; i++) { if (G.link[i].name == name) { index = i; break; } } if (index == -1) cout << "error" << endl; return index; } void constructGraph(Graph &G) { cout << "construct graph yooo" << endl; cout << "enter vexnum" << endl; cin >> G.vexnum; string array[] = {"v1", "v2", "v3", "v4", "v5", "v6", "v7", "v8"}; const int size = sizeof array / sizeof *array; for (int i = 0; i < G.vexnum; i++) { G.link[i].name = array[i]; G.link[i].head = NULL; } string leftName; string rightName; cout << "enter a pair" << endl; cin >> leftName >> rightName; while (leftName != "end" && rightName != "end") { int leftIndex = findIndex(G, leftName); int rightIndex = findIndex(G, rightName); Node *node = new Node; node->data = rightIndex; node->next = NULL; node->next = G.link[leftIndex].head; G.link[leftIndex].head = node; cout << "enter a pair" << endl; cin >> leftName >> rightName; } } bool flag[MAXLEN]; void DFSTranverse(Graph &G, int num) { cout << G.link[num].name << " "; flag[num] = true; Node *head = G.link[num].head; while (head != NULL) { int index = head->data; if (!flag[index]) DFSTranverse(G, index); head = head->next; } } void main() { Graph G; constructGraph(G); for (int i = 0; i < MAXLEN; i++) flag[i] = false; DFSTranverse(G, 0); }
DFS的迭代遍歷算法以下:
void DFS(Graph &G) { stack<int> istack; istack.push(0); cout << G.link[0].name << " "; flag[0] = true; while (!istack.empty()) { int index = istack.top(); Node *head = G.link[index].head; while (head != NULL && flag[head->data] == true) head = head->next; if (head != NULL) { index = head->data; if (!flag[index]) { cout << G.link[index].name << " "; flag[index] = true; istack.push(index); } } else istack.pop(); } }
理性的同伙可以測試運轉一下本文實例代碼以加深印象,信任本文所述對年夜家C法式算法設計的有必定的自創價值。