个人算法合集

同时发布在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;
    }
0 0 vote
Article Rating
Subscribe
提醒
0 评论
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x