图的逻辑结构如下:
源代码:
头文件ALGraph.h:
#ifndef ALGraph_H #define ALGraoh_H #include<stdlib.h> const int N = 10; int visited[N] {0}; struct Arcnode { int adjvex; Arcnode *next; }; template<class T> struct Vertexnode { T vertex; Arcnode *firstedge; }; template<typename T> class ALGraph { public: ALGraph(T a[],int num,int edge); ~ALGraph() { system("pause"); } void BFS(int v); void DFS(int v); private: Vertexnode<T> adjlist[N]; int vertexnum,arcnum; }; template<class T> ALGraph<T>::ALGraph(T a[],int edge) { Arcnode *s; int i,j,k; vertexnum = num; arcnum = edge; for (i = 0; i < vertexnum; i++) { adjlist[i].vertex = a[i]; adjlist[i].firstedge = NULL; } for (k = 0; k < arcnum; k++) { cout << "请输入两个相连顶点的编号:"; cin >> i; cin >> j; s = new Arcnode; s->adjvex = j; s->next = adjlist[i].firstedge; adjlist[i].firstedge = s; } } template<class T> void ALGraph<T>::BFS(int v) { Arcnode *p = nullptr; int Q[N]; int front,rear; front = -1; rear = -1; cout << adjlist[v].vertex; Q[++rear] = v; while (front!=rear) { v = Q[++front]; p = adjlist[v].firstedge; while (p != nullptr) { int j; j = p->adjvex; if (visited[j] == 0) { cout << adjlist[j].vertex; visited[j] = 1; Q[++rear] = j; } p = p->next; } } } template<class T> void ALGraph<T>::DFS(int v) { Arcnode *p = nullptr; int j; cout << adjlist[v].vertex; visited[v] = 1; p = adjlist[v].firstedge; while (p != nullptr) { j = p->adjvex; if (visited[j] == 0) DFS(j); p = p->next; } } template<class T> void showBFS(ALGraph<T> ALG) { cout << "广度优先遍历结果为:"; ALG.BFS(0); cout << endl; } template<class T> void showDFS(ALGraph<T> ALG_0) { cout << "深度优先遍历结果为:"; ALG_0.DFS(0); cout << endl; } #endif
源文件ALGraph_main.cpp:
#include<iostream> #include"ALGraph.h" using namespace std; int main() { char S[] {'A','B','C','D','E','F'}; int i; ALGraph<char> G(S,6,6); for (i = 0; i < N; i++) visited[i]=0; showBFS(G); for (i = 0; i < N; i++) visited[i] = 0; showDFS(G); cout << endl; return 0; }
运行截图: