同时发布在https://www.luogu.com.cn/paste/wks1sfde
DFS
递归:
void DFS_Search(ListNode* pRoot)
{
if(!pRoot) return;
visit(pRoot);
pRoot->visited = true;
foreach(ListNode* pChild in pRoot->adjacent)
if(!pChild->visited)
DFS_Seach(pChild);
}
非递归
#include <iostream>
#include <stack>
using namespace std;
#define MaxNode 20
#define MAX 2000
#define StartNode 1
int map[MaxNode+1][MaxNode+1];
void dfs_stack(int start, int n){
int visited[MaxNode],s_top;
for(int i = 0;i <= MaxNode; i++){
visited[i] = 0;
}
visited[start] = 1;
stack <int> s;
cout<<start<<" ";
for(int i = 1; i <= n; i++){
if(map[i][start] == 1 && !visited[i] ){
visited[i] = 1;
s.push(i);
}
}
while(!s.empty()){
s_top = s.top();
visited[s_top] = 1;
cout<<s_top<<" ";
s.pop();
for(int i = 1; i <= n; i++){
if(map[i][s_top] == 1 && !visited[i] ){
visited[i] = 1;
s.push(i);
}
}
}
}
int main(int argc, const char * argv[]) {
int num_edge,num_node;
int x,y;
cout<<"Input number of nodes and edges >"<<endl;
cin>>num_node>>num_edge;
for(int i =0;i<num_node;i++){
for(int j=0;j<num_node;j++){
map[i][j] = 0;
}
}
for(int i = 1; i <= num_edge; i++){
cin>>x>>y;
map[x][y] = map[y][x] = 1;
}
dfs_stack(StartNode, num_node);
return 0;
}
二分
递归:
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
非递归
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
Dijkstra
#include <iostream>
#include <vector>
const int maxdist = 9999;
using namespace std;
/*n是总的结点数,v是出发结点,dist是距离,pre前一个结点,d是结点间的权值*/
void Dijkstra(int n, int v, vector<int> &dist, vector<int> &pre, vector<vector<int>> &d)
{
vector<bool> s(n+1);
for (int i = 1; i <= n;i++)
{
dist[i] = d[v][i];
if (dist[i] < maxdist)
pre[i] = v;
else
pre[i] = 0;
}
dist[v] = 0;
s[v] = true;
for (int i = 2; i <= n;i++)//总的迭代次数
{
int best = v;
int temp = maxdist;
for (int j = 1; j <= n;j++)//找到最小的距离
{
if (!s[j]&&dist[j]<temp)
{
temp = dist[j];
best = j;
}
}
s[best] = true;
for (int j = 1; j <= n;j++)//更新dist和pre
{
if (!s[j] && d[best][j] != maxdist)
{
int newdist = dist[best] + d[best][j];
if (newdist<dist[j])
{
dist[j] = newdist;
pre[j] = best;
}
}
}
}
}
void printpath(vector<int> pre, int init, int fina)
{
int temp=fina;
vector<int> t;
while (temp != init)
{
t.push_back(temp);
temp = pre[fina];
fina = temp;
}
cout << init << "->";
for (int i = t.size(); i >1;i--)
{
cout << t[i-1] << "->";
}
cout << t[0];
t.clear();
}
int main()
{
int n, l;
cout << "请输入结点数和线数:";
cin >> n >> l;
vector<vector<int>> d(n+1, vector<int>(n+1));
for (int i = 1; i <= n;i++)
{
for (int j = 1; j <= n; j++)
d[i][j] = maxdist;
}
int p, q, len;
for (int i = 1; i <= l; ++i)
{
cin >> p >> q >> len;
if (len < d[p][q]) // 有重边
{
d[p][q] = len; // p指向q
d[q][p] = len; // q指向p,这样表示无向图
}
}
vector<int> dist(n+1),pre(n+1);
for (int i = 1; i <= n; ++i)
dist[i] = maxdist;
Dijkstra(n, 1, dist, pre, d);
cout << "点1到点n的最短路径长度: " << dist[n] << endl;
cout << "点1到点n的路径为: ";
printpath(pre, 1, n);
return 0;
}
Floyd
#include
int main()
{
int e[10][10],k,i,j,n,m,t1,t2,t3;
int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值
//读入n和m,n表示顶点个数,m表示边的条数
scanf("%d %d",&n,&m);
//初始化
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j) e[i][j]=0;
else e[i][j]=inf;
//读入边
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&t1,&t2,&t3);
e[t1][t2]=t3;
}
//Floyd-Warshall算法核心语句
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j] )
e[i][j]=e[i][k]+e[k][j];
//输出最终的结果
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%10d",e[i][j]);
}
printf("\n");
}
return 0;
}
