数据结构与算法——图的建立，深度优先搜索，广度优先搜索

图的表示方法

图的常用存储方法有两种：

邻接矩阵邻接表

邻接矩阵采用二维对称矩阵表示无向图，非对称矩阵表示有有向图； 邻接表使用数组+链表的形式保存图。

邻接表中有两种结点，头结点和表结点每个头结点存储一个顶点信息，一般头结点都存放在一个数组中对于某个顶点，与之相连的其他顶点被存放在一个单链表中，这个单链表就是邻接表每个头结点后面都连接其对应的邻接表 示例代码 /*表结点*/ struct Node { int ID; Node *next; }; /*头结点*/ struct HeadNode { char name; Node *first;//表结点指针 };

建立一个图的类，包含图的建立方法，以及深度优先算法与广度优先算法对图进行遍历。

class CMap { private: const int length; HeadNode *H;//邻接表 int *v; // 记录是否被访问 public: CMap(int n = 7); /*创建新图*/ void creatMap(); /*创建默认的图*/ void AutocreatMap(); /*深度优先搜索，实现图的遍历*/ void DeepSearch(int k); /*广度优先搜索，实现图的遍历*/ void WideSearch(int k); };

源代码

#include"mapNode.h" #include<string> #include<iostream> #include<queue> using namespace std; CMap::CMap(int n):length(n) { H = new HeadNode[length]; v = new int[length]; memset(v, 0, sizeof(v)*length); //creatMap(); AutocreatMap(); } void CMap::AutocreatMap() { string str1[7]= { "143","402","1","04","01563","64","45" }; for (int i = 0; i < length; i++) { H[i].name = 'A' + i; string str = str1[i]; int n = str.length(); if (n > 0) H[i].first = new Node; else H[i].first = NULL; Node* p = H[i].first; for (int j = 0; j < n; j++) { p->ID = str[j] - '0'; if (j == n - 1) p->next = NULL; else p->next = new Node; p = p->next; } } } void CMap::creatMap() { //string *str1 = new string[length]; //str1= { "143","402","1","04","01563","64","45" }; for (int i = 0; i < length; i++) { H[i].name = 'A' + i; string str;// = str1[i]; cin >> str; int n = str.length(); if (n > 0) H[i].first = new Node; else H[i].first = NULL; Node* p = H[i].first; for (int j = 0; j < n; j++) { p->ID = str[j] - '0'; if (j == n - 1) p->next = NULL; else p->next = new Node; p = p->next; } } } void CMap::DeepSearch(int k) { if (k > length - 1) { cout << "-----------------超过图的最大节点数-------------------" << endl; cout << "请重新输入！" << endl; } v[k] = 1; Node *p = H[k].first; cout << H[k].name; while (p != NULL)//&& v[p->ID] == 0) { if (v[p->ID] == 0) DeepSearch(p->ID); p = p->next; } } void CMap::WideSearch(int k) { if (k > length - 1) { cout << "-----------------超过图的最大节点数-------------------" << endl; cout << "请重新输入！" << endl; } v[k] = 1; queue<HeadNode> que; que.push(H[k]); cout << H[k].name << endl; HeadNode hp; while (!que.empty()) { hp = que.front(); que.pop(); Node *np = hp.first; while (np) { if (v[np->ID] == 0) { v[np->ID] = 1; que.push(H[np->ID]); cout << H[np->ID].name << endl; } np = np->next; } } }

测试代码

int main() { CMap map1; map1.WideSearch(5); system("pause"); return 0; }