C语言实现图的遍历之深度优先搜索实例

#include <iostream>#include <algorithm>#include <iterator>using namespace std;  #define MAX_VERTEX_NUM 10struct 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);}

#include <iostream>#include <string>using namespace std;#define MAXLEN 10struct 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);}

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(); }}