DS复习提纲模版

数组的插入删除 

int SeqList::list_insert(int i, int item) { //插入if (i < 1 || i > size + 1 || size >= maxsize) {return 0;  // Invalid index or list is full}for (int j = size-1; j >= i-1; j--) {  // Shift elements to the rightlist[j+1] = list[j];}list[i - 1] = item;  // Insert the item at position i-1size++;  // Increase sizereturn 1;
}
int SeqList::list_del(int i) {  //删除if (i < 1 || i > size) {return 0;  // Invalid index}for (int j = i; j < size; j++) {  // Shift elements to the leftlist[j-1] = list[j];}size--;  // Decrease sizereturn 1;
}

链表操作 

#include <iostream>
using namespace std;
#define ok 0
#define error -1
//链表结点类定义
class ListNode {
public:int data;ListNode* next;ListNode() : data(0), next(NULL) {}
};
//带头结点的单链表定义
class LinkList {
public:ListNode* head;int len;LinkList() : head(new ListNode()), len(0) {}~LinkList();ListNode* LL_index(int i);int LL_get(int i);int LL_insert(int i, int item);int LL_del(int i);void LL_display();
};
LinkList::~LinkList() {ListNode* p, * q;p = head;while (p != NULL) {q = p;p = p->next;delete q;}len = 0;head = NULL;
}
void LinkList::LL_display() {ListNode* p = head->next;while (p) {cout << p->data << ' ';p = p->next;}cout << endl;
}
ListNode* LinkList::LL_index(int i) {int h = 0;ListNode* p = head;while (p && h < i) {p = p->next;h++;}return p;
}
int LinkList::LL_insert(int i, int item) {if (i < 0 || i > len)return error;ListNode* p = head;for (int h = 0; h < i; ++h) {p = p->next;}ListNode* s = new ListNode();s->data = item;s->next = p->next;p->next = s;++len;return ok;
}
int LinkList::LL_get(int i) {if (i < 1 || i > len)return error;ListNode* p = head->next;for (int h = 1; h < i; ++h) {p = p->next;}return p->data;
}
int LinkList::LL_del(int i) {if (i < 1 || i > len)return error;ListNode* p = head;for (int h = 0; h < i - 1; ++h) {p = p->next;}ListNode* s = p->next;p->next = s->next;//头尾相等 空delete s;--len;return ok;
}//两个节点交换位置  需要交换这两个节点的前驱跟后继指针来完成
void LinkList::swap(ListNode* p, ListNode* q) {// 找到p和q的前驱节点ListNode* prevP = head;while (prevP != NULL && prevP->next != p) {prevP = prevP->next;}ListNode* prevQ = head;while (prevQ != NULL && prevQ->next != q) {prevQ = prevQ->next;}// 如果p或q不在链表中，或者它们是头节点（没有前驱），则无法交换if (prevP == NULL || prevQ == NULL) {return;}if (p == NULL || q == NULL)return;//p q是相邻的if (p->next == q) {p->next = q->next;q->next = p;prevP->next = q;}else {// 交换prevP和prevQ的下一个节点的指针ListNode* temp = p->next;p->next = q->next;q->next = temp;// 交换p和q的指针temp = prevP->next;prevP->next = prevQ->next;prevQ->next = temp;}
}
//链表的合并
ListNode* LL_merge1(ListNode* p, ListNode* q) {ListNode* preHead = new ListNode();ListNode* prev = preHead;while (p && q) {if (p->data < q->data) {prev->next = p;p = p->next;}else if (p->data > q->data) {prev->next = q;q = q->next;}else {prev->next = q;p = p->next;q = q->next;}prev = prev->next;}prev->next = q ? q : p;//更长的那一段的剩余的直接截取接至新链表//pre->next = p ? p : q;return preHead->next;
}
//删除链表相同元素--与先存进来的元素互异后才可存入链表
#include<iostream>
using namespace std;
// 定义链表节点结构体LNode
typedef struct LNode {int data;             // 节点存储的数据struct LNode* next;   // 指向下一个节点的指针
} LNode, * Linklist;     // LNode为节点类型，Linklist为指向节点的指针类型
int main() {int t;cin >> t;             // 读取测试用例的数量while (t--) {         // 对每个测试用例进行处理int n;cin >> n;         // 读取链表长度Linklist L;L = new LNode;    // 创建头节点L->next = NULL;   // 初始化头节点的next指针为NULLLNode* r = L;     // r指针用于指向链表的最后一个节点// 循环读取n个数据，并插入到链表中for (int i = 0; i < n; i++) {int num;cin >> num;       // 读取一个数据LNode* tmp = L;   // tmp指针用于遍历链表  L是一整个链表bool dup = false; // 标记是否发现重复数据// 遍历链表，检查num是否已存在while (tmp) {if (tmp->data == num) {dup = true; // 发现重复数据break;      // 退出循环}tmp = tmp->next;}// 如果num已存在，则跳过插入操作if (dup) {continue;}else {// 创建新节点并插入到链表末尾r->next = new LNode;r->next->data = num; // 设置新节点的数据r = r->next;         // 更新r指针r->next = nullptr;   // 设置新节点的next指针为NULL}}// 计算链表长度int len = 0;LNode* p = L->next;  // p指针用于遍历链表LNode* q = L->next;  // q指针也用于遍历链表while (q != NULL) {  // 遍历链表计算长度q = q->next;len++;}// 这里删除q是错误的，因为q已经是NULL，不需要删除// delete q;// 输出链表长度和链表数据cout << len << ":";while (p != NULL) {  // 遍历链表并输出数据cout << " " << p->data;p = p->next;}// 这里删除p是错误的，因为p指向的是头节点的下一个节点// 应该遍历整个链表并删除每个节点// delete p;cout << endl;// 释放链表内存LNode* toDelete = L;while (toDelete != NULL) {LNode* next = toDelete->next;delete toDelete;toDelete = next;}}return 0;
}

栈（先进后出）

// 行编辑
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {int t;cin >> t;while (t--) {string str;cin >> str;     // 把输入的字符串保存在变量str中int len = str.length();        // 获取输入字符串的长度stack<char> s;for (int m = 0; m < len; m++) {char ch = str[m]; // 读取当前字符if (ch != '#') {s.push(ch); // 如果不是 '#'，则压入栈 s}else if(ch=='#'&& !s.empty()){s.pop();}}if (s.empty()) {cout << "NULL" << endl;}while (!s.empty()) {cout << s.top();s.pop();}cout << endl;}return 0;
}

波兰式与逆波兰式

#include<iostream>
#include<string>
#include<stack>
using namespace std;
class Solution
{
private:stack<string> nums;		// 存储操作数, 实际上会存储操作符的stack<char> op;			// 存储操作符// 逆向遍历时判断操作符优先级bool opcmpRight(char op1, char op2){// + - 的时候，只需要判断栈顶是否同级，逆序，同级新的优先级更高if (op1 == '+' || op1 == '-'){return op2 == '+' || op2 == '-';}// * / 直接入栈return true;}// 正向遍历时判断操作符优先级bool opcmpLeft(char op1, char op2){// 正向的时候，同级新的优先级会低if (op1 == '*' || op1 == '/'){return op2 != '*' && op2 != '/';}return false;}
public:string poland(string s)// 求解波兰式{int len = s.length();for (int i = len - 1; i >= 0; --i){if (s[i] >= '0' && s[i] <= '9'){string num = "";num += s[i];while (i - 1 >= 0 && s[i - 1] >= '0' && s[i - 1] <= '9'){num = s[--i] + num;}nums.push(num);}else if (op.empty() || s[i] == ')' || op.top() == ')'){op.push(s[i]);}else if (s[i] == '('){while (!op.empty() && op.top() != ')'){string ops = "";ops += op.top();nums.push(ops);op.pop();}op.pop();}else if (opcmpRight(s[i], op.top())){op.push(s[i]);}else{while (!op.empty() && !opcmpRight(s[i], op.top())){string ops = "";ops += op.top();nums.push(ops);op.pop();}op.push(s[i]);}}while (!op.empty()){string ops = "";ops += op.top();nums.push(ops);op.pop();}string ans = "";while (!nums.empty()){ans += nums.top() + (nums.size() > 1 ? " " : "");nums.pop();}return ans;}string antiPoland(string s){int len = s.size();string ans = "";for (int i = 0; i < len; ++i){if (s[i] >= '0' && s[i] <= '9'){ans += s[i];while (i + 1 < len && s[i + 1] >= '0' && s[i + 1] <= '9'){ans += s[++i];}ans += " ";}else if (op.empty() || s[i] == '(' || op.top() == '('){op.push(s[i]);}else if (s[i] == ')'){while (!op.empty() && op.top() != '('){ans += op.top();ans += " ";op.pop();}op.pop();}else if (opcmpLeft(s[i], op.top())){op.push(s[i]);}else{while (!op.empty() && !opcmpLeft(s[i], op.top())){ans += op.top();ans += " ";op.pop();}op.push(s[i]);}}while (!op.empty()){ans += op.top();ans += op.size() > 1 ? " " : "";op.pop();}return ans;}
};
int main()
{int t;cin >> t;while (t--){Solution sol;string s;cin >> s;cout << sol.poland(s) << endl;cout << sol.antiPoland(s) << endl << endl;} return 0;
}

队列（先进先出）

#include<iostream>
#include<queue>
#include<utility>
#include<vector>
#include<iomanip>
#include<algorithm>
using namespace std;
int main()
{int n;cin >> n;// 用户队列queue<pair<int, int>> customer;for (int i = 0; i < n; i++){int time1, time2;cin >> time1 >> time2;customer.push({ time1, time2 });}int k;cin >> k;// 初始化窗口vector<int> windows(k, 0);// 总时间，完成时间，和最大等待时间int totalWaitTime = 0, finishTime = 0, maxWaitTime = 0;while (!customer.empty()){int arriveTime = customer.front().first;int takenTime = customer.front().second;// 默认最早空闲的窗口的最小下标int minIndex = 0;for (int i = 0; i < k; ++i){// 窗口在到达时间之前空闲if (windows[i] <= arriveTime){minIndex = i;break;}// 动态更新下标if (windows[i] < windows[minIndex]){minIndex = i;}}// 最早空闲的窗口先于到达时间if (windows[minIndex] <= arriveTime){windows[minIndex] = arriveTime + takenTime;}// 否则则需要等待else{int wait = windows[minIndex] - arriveTime;windows[minIndex] += takenTime;totalWaitTime += wait;maxWaitTime = max(maxWaitTime, wait);}// 完成时间取最大值finishTime = max(finishTime, windows[minIndex]);customer.pop();}cout << fixed << setprecision(1) << (double)(totalWaitTime * 1.0 / n)<< " " << maxWaitTime << " " << finishTime << endl;return 0;
}

 串

//真前后缀
#include <iostream>
#include <string>
using namespace std;
string matchedPrefixPostfix(string str) {int n = str.length();string result = "empty";if (n > 1) {for (int i = 0; i < n; ++i) {for (int j = 0; j <= n - i - 1; ++j) {string prefix = str.substr(0, i + 1);//提取子串 正向string postfix = str.substr(n - j - 1, j + 1);// 提取子串 逆向if (prefix == postfix) {result = prefix;}}}}return result;
}
int main() {int t;cin >> t;while (t--) {string str;cin >> str;cout << matchedPrefixPostfix(str) << endl;}return 0;
}

查找

//直接插入排序
void InsertSort(int array[], int length) {for (int i = 1; i < length; i++) {		//第1个数是有序的，所以从第2个数开始遍历，依次插入int j = i - 1;					//前i-1个数都是有序序列(由小到大)，只要a[j]比temp大，就将此数后移int temp = array[i];		//先将当前的数存储在temp后，以免后面移位被覆盖for (j = i - 1; j >= 0 && array[j] > temp; j--) {//a[j]小于 temp 时循环结束，结束后应将 temp 赋值给a[j+1]array[j + 1] = array[j];	//将 a[j] 后移一位 }array[j + 1] = temp;			//将 temp 赋值给a[j+1]Print(array, length);}
}//希尔排序
void find(int* a, int n) {int b = n / 2;while (b >= 1) {for (int i = b; i < n; i++) {int  tmp = a[i];int j = i;while (j >= b && a[j - b] < tmp) {a[j] = a[j - b];j -= b;}a[j] = tmp;}for (int i = 0; i < n-1; i++) {cout << a[i] << " ";}cout << a[n-1]<<endl;b = b / 2;}
}
//冒泡排序
void bubble_sort(int * arr, int len) 
{int i, j;int k = 0;for (i = 0; i < len - 1; i++)for (j = 0; j < len - 1 - i; j++)if (arr[j] > arr[j + 1]){swap(arr[j], arr[j + 1]);k++;}cout << k << endl;
}
//快速排序
int Partition(int * &array, int low, int high){int mid_key= array[low];//记录枢轴的值while(low< high){while(low< high&&array[high]>= mid_key )high--;array[low]= array[high];//大于枢轴的值前移while(low< high&&array[low]<= mid_key)low++;array[high]= array[low];  //小于枢轴的值后移    }array[low]= mid_key;//最后才将枢轴的值记录到位return low;  //返回枢轴的位置
}
void print(int * &array){//打印输出for(int i= 1; i<= n; i++){cout<<array[i];if(i!= n)cout<<' ';elsecout<<endl; }   
}
void Qsort(int* &array, int low, int high){//快速排序if(low< high){int mid= Partition(array, low, high);print(array);Qsort(array, low, mid- 1);//将数组分成[low,mid-1]和[mid,high]两个区间Qsort(array, mid+ 1, high);//}
}

树--叶子

//二叉树找父子节点
#include <iostream>
#include<queue>
using namespace std;
typedef struct BitNode {char data;BitNode* lchild, * rchild;
}BitNode, * BitTree;
void CreatTree(BitTree& T) {char ch;cin >> ch;if (ch == '/0') { return; }if (ch == '0') { T = NULL; }else {T = new BitNode;T->data = ch;/*先左后右保存数据**/CreatTree(T->lchild);CreatTree(T->rchild);}
}
int FindLeaf(BitTree& T, queue<char>& child, queue<char>& parent) {if (!T) { return 1; }int flag = 0;//统计叶子if (T) {int item = FindLeaf(T->lchild, child, parent);//记录左儿子是不是叶子if (item == 0) {parent.push(T->data);}else if (item == 1) {flag++;}item = FindLeaf(T->rchild, child, parent);if (item == 0) {parent.push(T->data);}else if (item == 1) {flag++;}}if (flag == 2) {child.push(T->data);return 0;}return -1;//未找到叶子
}
//统计左叶子
void LeftLeaf(BitTree& T,int & cnt,bool isleft) {//是否为空//是否为叶子//对左叶子进行布尔值改变//对右叶子不做布尔值变化if (!T) { return ; }  //空的标记return	if (!T->lchild&&!T->rchild) {if(isleft)cnt++;}LeftLeaf(T->lchild, cnt, true);LeftLeaf(T->rchild, cnt,false);
}

树的遍历

#include <iostream>
#include<queue>
using namespace std;
typedef struct BitNode {char data;BitNode* lchild, * rchild;
}BitNode, * BitTree;
void CreatTree(BitTree& T) {char ch;cin >> ch;if (ch == '/0') { return; }if (ch == '0') { T = NULL; }else {T = new BitNode;T->data = ch;/*先左后右保存数据**/CreatTree(T->lchild);CreatTree(T->rchild);}
}
// 层序遍历
void LevelOrder(BitTree t) {queue<BitNode*> q;//结点指针BitNode* p = t;	q.push(t);while (!q.empty()) {p = q.front();q.pop();cout << p->data << endl;if (p->lchild) {q.push(p->lchild);}if (p->rchild) {q.push(p->rchild);}}
}
//前序遍历
void PreOrder(BitNode* t) {if (t) {cout << t->data;PreOrder(t->lchild);PreOrder(t->rchild);}
}
//中序遍历
void InOrder(BitNode *t) {if (t) {InOrder(t->lchild);cout << t->data;InOrder(t->rchild);}
}
//后序遍历
void PostOrder(BitNode* t) {if (t) {PostOrder(t->lchild);PostOrder(t->rchild);cout << t->data;}
}
//获取树的高度
int getheight(BitNode *p){if(p==NULL)return 0;int left = getheight(p->lchild);int right = getheight(p->rchild);return max(left,right)+1;
}
//非递归后序遍历
void PostOrderTraverse()
{stack<Binary_tree_node*> s1; // 栈s1用于存储树节点stack<int> s2; // 栈s2用于标记节点是否已经被访问过（0表示未访问，1表示已访问）Binary_tree_node* p = root; // p指向树的根节点do{// 当p不为NULL时，遍历左子树while (p != NULL) {s1.push(p);        // 将当前节点压入s1栈s2.push(0);        // 在s2栈中压入0，表示该节点未访问过p = p->LeftChild;  // 移动到当前节点的左孩子if (s1.empty())    // 如果栈s1为空，表示树为空，跳出循环{break;}}// 如果p为NULL（意味着当前节点没有左孩子）时，开始处理节点if (!p == NULL)  // `!p`的条件使得该程序块在p为NULL时执行{if (s2.top() == 0)  // 如果s2栈顶为0，表示当前节点没有被访问过{s2.top() = 1;    // 将栈顶的0改为1，标记当前节点已访问过p = s1.top()->RightChild; // 转向当前节点的右孩子，准备遍历右子树}else if (s2.top() == 1)  // 如果s2栈顶为1，表示当前节点已访问过，且其左右子树都已处理{p = s1.top();    // 获取当前节点s1.pop();         // 从s1栈中弹出该节点s2.pop();         // 从s2栈中弹出对应的标记cout << p->data;  // 输出当前节点的值p = NULL;         // 将p置为NULL，表示当前节点已经处理完毕}}} while (!s1.empty()); // 当栈s1不为空时，继续遍历cout << endl; // 输出换行符
}

哈夫曼树编码与解码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<deque>
#define error -1
#define ok  1
using namespace std;
struct BitNode {BitNode* lchild;BitNode* rchild;int data;char ch;string str;
}*BitTree;
bool cmp(BitNode* a, BitNode* b) {return a->data < b->data;
}
//哈夫曼编码
void huffman(BitNode* t) {if (t->lchild) {t->lchild->str = t->str + '0';}if (t->rchild) {t->rchild->str = t->str + '1';}if (t->lchild)huffman(t->lchild);if (t->rchild)huffman(t->rchild);
}
//哈夫曼解码
int decode(string code, char txt[], BitNode* t) {int len = code.length();BitNode* curr = t;int index = 0;for (int i = 0; i < len; i++) {if (code[i] == '0') {curr = curr->lchild;}elsecurr = curr->rchild;if (!curr->lchild && !curr->rchild) {txt[index++] = curr->ch;curr = t;}}txt[index] = '\0'; // 确保字符串正确终止！！！if (curr != t)return error;else return ok;
}
int main() {int t;cin >> t;while (t--) {int n;cin >> n;deque<BitNode*>p;deque<BitNode*>q;for (int i = 0; i < n; i++) {BitNode* T = new BitNode();T->str = "";cin >> T->data;p.push_back(T);q.push_back(T);}for (int i = 0; i < n; i++) {cin >> p[i]->ch;}while (p.size()!=1) {sort(p.begin(), p.end(), cmp);BitNode* a = p.front(); p.pop_front();BitNode* b = p.front(); p.pop_front();BitNode* c = new BitNode();c->lchild = a;c->rchild = b;c->data = a->data + b->data;p.push_back(c);}BitNode* d = p.front();huffman(d);
//输出编码for (int i = 0; i < q.size(); i++) {cout << q[i]->data << "-" << q[i]->str << endl;}
//输出解码int m;cin >> m;while (m--) {string dcode;cin >> dcode;char txt[1000];decode(dcode, txt, d);if (decode(dcode, txt, d) == error)cout << "error" << endl;elsecout << txt << endl;}}return 0;
}

AVL平衡二叉树

#include <iostream>
using namespace std;
#define LH 1  // 左高
#define EH 0  // 等高
#define RH -1 // 右高
int max(int a, int b) {return a > b ? a : b;
}
class BiNode {
public:int key;      // 关键值int bf;       // 平衡因子BiNode* lChild, * rChild;BiNode(int kValue, int bValue = EH){key = kValue;bf = bValue;lChild = NULL;rChild = NULL;}
};
int getheight(BiNode* t) {if (t == NULL) {return 0;}return max(getheight(t->lChild), getheight(t->rChild)) + 1;
}
// 二叉排序树
class BST {
private:BiNode* root; // 根结点指针void rRotate(BiNode*& p);void lRotate(BiNode*& p);void leftBalance(BiNode*& t);void rightBalance(BiNode*& t);void insertAVL(BiNode*& t, int key); // 插入元素并做平衡处理void inOrder(BiNode* p);  // 中序遍历int countNodes(BiNode* p);  // 计算树中节点的数量
public:BST();void insertAVL(int key); // 二叉排序树插入元素~BST();void inOrder(); // 中序遍历void inOrderHelper(BiNode* p, int& currentNode, int totalNodes);
};
void BST::lRotate(BiNode*& p)//右旋 LL
{BiNode* q = p->lChild;p->lChild = q->rChild;q->rChild = p;p = q; // p变为新的根结点// 旋转后更新平衡因子p->bf = getheight(p->lChild) - getheight(p->rChild);p->rChild->bf = getheight(p->rChild->lChild) - getheight(p->rChild->rChild);
}
void BST::rRotate(BiNode*& p)//左旋 RR
{BiNode* q = p->rChild;p->rChild = q->lChild;q->lChild = p;p = q; // p变为新的根结点// 旋转后更新平衡因子p->bf = getheight(p->lChild) - getheight(p->rChild);p->lChild->bf = getheight(p->lChild->lChild) - getheight(p->lChild->rChild);
}
void BST::leftBalance(BiNode*& t)//左旋左孩子再右旋 LR
{rRotate(t->lChild);lRotate(t);
}
void BST::rightBalance(BiNode*& t)//右旋右孩子再左旋 RL
{lRotate(t->rChild);rRotate(t);
}
void BST::insertAVL(BiNode*& t, int key) {if (t == NULL) {t = new BiNode(key);return;}if (key < t->key) {insertAVL(t->lChild, key);if (getheight(t->lChild) - getheight(t->rChild) == 2) {if (key < t->lChild->key) {lRotate(t); // LL}else {leftBalance(t); // LR}}}else if (key > t->key) {insertAVL(t->rChild, key);if (getheight(t->rChild) - getheight(t->lChild) == 2) {if (key > t->rChild->key) {rRotate(t); // RR}else {rightBalance(t); // RL}}}// 更新平衡因子if (t != NULL) {t->bf = getheight(t->lChild) - getheight(t->rChild);}
}
// 中序遍历
void BST::inOrder(BiNode* p)
{if (p){inOrder(p->lChild);cout << p->key << ":" << p->bf;inOrder(p->rChild);}
}
int BST::countNodes(BiNode* p)
{if (p == NULL)return 0;return 1 + countNodes(p->lChild) + countNodes(p->rChild);
}
void BST::inOrder()
{int totalNodes = countNodes(root);  // 获取树中总节点数int currentNode = 0;  // 当前节点计数器// 中序遍历时判断是否为最后一个节点inOrderHelper(root, currentNode, totalNodes);cout << endl;  // 输出结束后换行
}
//消除最后一个节点及其平衡因子的空格
void BST::inOrderHelper(BiNode* p, int& currentNode, int totalNodes)
{if (p){inOrderHelper(p->lChild, currentNode, totalNodes);cout << p->key << ":" << p->bf;currentNode++;if (currentNode < totalNodes)cout << " ";  // 如果不是最后一个节点，输出空格inOrderHelper(p->rChild, currentNode, totalNodes);}
}
BST::BST()
{root = NULL;
}
BST::~BST()
{root = NULL;
}
void BST::insertAVL(int key)
{insertAVL(root, key);
}
int main(void)
{int t;cin >> t;while (t--){int n, elem;cin >> n;BST tree;while (n--){cin >> elem;tree.insertAVL(elem);}tree.inOrder();}return 0;
}

图的连通

#include <iostream>
using namespace std;void DFS(int** m, int n, int* visit, int temp)
{for (int j = 0; j < n; j++){if (m[temp][j] == 1 && visit[j] == 0){visit[j] = 1;DFS(m, n, visit, j);}}
}
void isconmected(int n)
{int** m;m = new int* [n];for (int i = 0; i < n; i++){m[i] = new int[n];for (int j = 0; j < n; j++)cin >> m[i][j];}int* visit = new int[n];for (int i = 0; i < n; i++)visit[i] = 0;int flag = 0;for (int i = 0; i < n; i++){visit[i] = 0;DFS(m, n, visit, i);        //对每个顶点都调用DFSfor (int j = 0; j < n; j++){if (visit[j] == 0)     //然后判断此顶点能否到达其它顶点，visit[j]=0代表不能到达{flag = 1;break;}elsevisit[j] = 0;}if (flag == 1)break;}if (flag == 0)cout << "Yes" << endl;elsecout << "No" << endl;delete[]m;
}
int main()
{int t;cin >> t;int n;while (t--){cin >> n;isconmected(n);}return 0;
}

图的广度遍历

#include <iostream>
#include <queue>
#include <cstring> // For memset
using namespace std;const int MAX = 20;class Map {
private:bool Visit[MAX];           // 访问标记数组int Matrix[MAX][MAX];      // 邻接矩阵int Vexnum;                // 顶点数void BFS(int v);           // 广度优先搜索public:void SetMatrix(int vnum, int mx[MAX][MAX]); // 设置邻接矩阵void BFSTraverse();       // 广度优先遍历图void ResetVisit();        // 重置访问标记数组
};// 设置邻接矩阵
void Map::SetMatrix(int vnum, int mx[MAX][MAX]) {Vexnum = vnum;// 清空矩阵memset(Matrix, 0, sizeof(Matrix));// 复制输入的邻接矩阵for (int i = 0; i < Vexnum; i++) {for (int j = 0; j < Vexnum; j++) {Matrix[i][j] = mx[i][j];}}
}// 广度优先遍历
void Map::BFSTraverse() {// 每次遍历前清空 Visit 数组ResetVisit();// 遍历所有未被访问的顶点for (int i = 0; i < Vexnum; i++) {if (!Visit[i]) {BFS(i);cout << endl;  // 每个 BFS 完成后换行}}
}// BFS 从顶点 v 开始进行广度优先搜索
void Map::BFS(int v) {queue<int> Q;         // 队列存储待访问的顶点Visit[v] = true;      // 标记当前顶点为已访问cout << v << " ";     // 打印当前顶点Q.push(v);            // 将当前顶点入队while (!Q.empty()) {int u = Q.front(); // 获取队头元素Q.pop();            // 出队// 遍历顶点 u 的所有邻接顶点for (int i = 0; i < Vexnum; i++) {if (Matrix[u][i] == 1 && !Visit[i]) {  // 如果 u 到 i 有边且 i 未被访问Visit[i] = true;                   // 标记 i 为已访问cout << i << " ";                  // 打印邻接点Q.push(i);                         // 将 i 入队}}}
}// 重置访问标记数组
void Map::ResetVisit() {memset(Visit, false, sizeof(Visit));  // 将 Visit 数组全部置为 false
}int main() {int t;cin >> t;  // 输入测试用例数量while (t--) {int n;cin >> n;  // 输入图的顶点数int ver[MAX][MAX];// 输入邻接矩阵for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {cin >> ver[i][j];}}Map a;a.SetMatrix(n, ver);  // 设置图的邻接矩阵a.BFSTraverse();      // 进行广度优先遍历}return 0;
}

图的深度遍历

#include<iostream>
using namespace std;
const int max_vertex_number = 20;
class Map {int vertex_number = 0;bool visited[max_vertex_number] = { false };int matrix[max_vertex_number][max_vertex_number];
public:Map() {cin >> vertex_number;for (int i = 0; i < vertex_number; i++)for (int j = 0; j < vertex_number; j++)cin >> matrix[i][j];}void DFS(int cur) {if (visited[cur])return;cout << cur << ' ';visited[cur] = true;for (int i = 0; i < vertex_number; i++)if (matrix[cur][i])DFS(i);}void Traverse() {for (int i = 0; i < vertex_number; i++)if (visited[i] == false)DFS(i);cout << endl;}
};
int main() {int t;cin >> t;while (t--) {Map test;test.Traverse();}return 0;
}