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程序算法设计的有一定的借鉴价值。
【C语言实现图的遍历之深度优先搜索实例】相关文章：
★ 利用C语言实践OOP,以及new,delete的深入分析