图论算法总结(一)——图的遍历

图论算法总结(一)——图的遍历
强烈推介IDEA2021.1.3破解激活,IntelliJ IDEA 注册码,2021.1.3IDEA 激活码  

大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说图论算法总结(一)——图的遍历,希望能够帮助大家进步!!!

图论算法总结

一、前言

关于数据结构,主要是有关树和图是最终的难点和痛点,关于算法,记住名字很简单,记住原理要花一点时间,如何内化为自己本身的知识,以及,在脑中有思路,随拿随用,这个需要特定的记忆方式。如果不能即拿即用,并不能说自己了解这个算法。建议大家,以自己的思维为中心,记住该思维的逻辑的同时,也记住该思路的代码,把算法内化为自己的修养。

参考博文:https://liuchuo.net/archives/tag/dfs(与原博文有一定差异,建议大家也按照自己思路进行书写代码,每个人思维方式不一样

二、图的遍历

2.1.深度优先dfs遍历图

按照深度优先方式访问未访问的节点

2.1.1.伪代码
dfs(u){
    vis[u]=true;
    for(从u出发能到达的所有顶点v)
        if(vis[v]==false)
            dfs(v);
}
dfsTrave(G){
    for(G的所有节点u)
        if(vis[u]==false)
            dfs(u)
}
2.1.2.C语言代码(邻接矩阵)
//邻接矩阵
void dfs(int u){
    vis[u]=1;
    printf("%d",u);
    for(int i=0;i<vertxNum;i++)
        if(vis[i]==0&&path[u][i]==1) dfs(i);
}
void dfsTrave(){
    for(int i=0;i<vertxNum;i++)
        if(vis[i]==false) dfs(i);
}
2.1.3.C语言代码(邻接表)
void dfs(int u){
    vis[u]=1;
    printf("%d",n[u].val);
    for(int i=0;i<n[u].next.size();i++)
        if(vis[n[u].next[i]->val]==0) dfs(n[u].next[i]->val);
}
void dfsTrave(){
    for(int i=0;i<vertxNum;i++){
        if(vis[i]==0) dfs(i);
    }
}
2.1.4.0.测试用例(C++)

2.1.4.1.邻接矩阵

#include <iostream>
#define vertxNum 4

using namespace std;

int vetx[vertxNum]={0,1,2,3};
int path[vertxNum][vertxNum]={0};
bool vis[vertxNum]={0};

void dfs(int u){
    vis[u]=1;
    printf("%d",u);
    for(int i=0;i<vertxNum;i++)
        if(vis[i]==0&&path[u][i]==1) dfs(i);
}
void dfsTrave(){
    for(int i=0;i<vertxNum;i++)
        if(vis[i]==false) dfs(i);
}
int main()
{
    /**build graph*/
    path[0][2]=1;path[2][0]=1;
    path[2][3]=1;path[3][2]=1;
    path[1][3]=1;path[3][1]=1;
    path[2][1]=1;path[1][2]=1;
    dfsTrave();
    system("pause");
    return 0;
}
2.1.4.2.邻接表
#include <iostream>
#include <vector>
#define vertxNum 4
using namespace std;
struct node{
    int val;
    vector<node*> next;
};
node n[vertxNum];
bool vis[vertxNum]={0};
void dfs(int u){
    vis[u]=1;
    printf("%d",n[u].val);
    for(int i=0;i<n[u].next.size();i++)
        if(vis[n[u].next[i]->val]==0) dfs(n[u].next[i]->val);
}
void dfsTrave(){
    for(int i=0;i<vertxNum;i++){
        if(vis[i]==0) dfs(i);
    }
}
int main(){
    /**build graph*/
    n[0].val=0;n[1].val=1;n[2].val=2;n[3].val=3;
    n[0].next.push_back(&n[2]);n[2].next.push_back(&n[0]);
    n[1].next.push_back(&n[2]);n[2].next.push_back(&n[1]);
    n[1].next.push_back(&n[3]);n[3].next.push_back(&n[1]);
    n[2].next.push_back(&n[3]);n[3].next.push_back(&n[2]);
    dfsTrave();
    system("pause");
    return 0;
}
2.2.广度优先bfs遍历图
2.2.1伪代码
bfs(u) {
  queue q;
  将u入队
  inq[u] = true;
  while(q非空) {
    for(从u出发到可到达的所有定点v) {
      if(inq[v] == false)
        将v入队
        inq[v] = true;
    }
  }
}
bfsTrave(G) {
  for(G的所有顶点u) {
    if(inq[u] == false)
      bfs(u);
  }
}
2.2.2.C语言代码(邻接矩阵)
void bfs(int u){
    que.push(u);
    vis[u]=1;
    while(!que.empty()){
        u=que.front();
        printf("%d",u);
        que.pop();
        for(int i=0;i<vertxNum;i++)
            if(path[u][i]==1&&vis[i]==0){
                que.push(i);
                vis[i]=1;
            }
    }
}
void bfsTrave(){
    for(int i=0;i<vertxNum;i++)
        if(vetx[i]==0) bfs(i);
}
2.2.3.C语言代码(邻接表)
void bfs(int u){
    que.push(u);
    vis[u]=1;
    while(!que.empty()){
        u=que.front();
        printf("%d",u);
        que.pop();
        for(int i=0;i<n[u].next.size();i++){
            if(vis[n[u].next[i]->val]==0){
                que.push(n[u].next[i]->val);
                vis[n[u].next[i]->val]=1;
            }
        }
    }
}
void bfsTrave(){
    for(int i=0;i<vertxNum;i++)
        if(vis[i]==0) bfs(n[i].val);
}
2.2.4.0.测试用例(C++)
2.2.4.1.邻接矩阵
#include <iostream>
#include <queue>
#define vertxNum 4

using namespace std;
int vetx[vertxNum]={0,1,2,3};
int path[vertxNum][vertxNum]={0};
queue<int> que;
bool vis[vertxNum]={0};

void bfs(int u){
    que.push(u);
    vis[u]=1;
    while(!que.empty()){
        u=que.front();
        printf("%d",u);
        que.pop();
        for(int i=0;i<vertxNum;i++)
            if(path[u][i]==1&&vis[i]==0){
                que.push(i);
                vis[i]=1;
            }
    }
}
void bfsTrave(){
    for(int i=0;i<vertxNum;i++)
        if(vetx[i]==0) bfs(i);
}
int main()
{
    /**build graph*/
    path[0][2]=1;path[2][0]=1;
    path[0][3]=1;path[3][0]=1;
    path[1][3]=1;path[3][1]=1;
    path[2][1]=1;path[1][2]=1;
    bfsTrave();
    system("pause");
    return 0;
}
2.2.4.2.邻接表
#include <iostream>
#include <vector>
#include <queue>
#define vertxNum 4
using namespace std;
struct node{
    int val;
    vector<node*> next;
};
node n[vertxNum];
bool vis[vertxNum]={0};
queue<int> que;
void bfs(int u){
    que.push(u);
    vis[u]=1;
    while(!que.empty()){
        u=que.front();
        printf("%d",u);
        que.pop();
        for(int i=0;i<n[u].next.size();i++){
            if(vis[n[u].next[i]->val]==0){
                que.push(n[u].next[i]->val);
                vis[n[u].next[i]->val]=1;
            }
        }
    }
}
void bfsTrave(){
    for(int i=0;i<vertxNum;i++)
        if(vis[i]==0) bfs(n[i].val);
}
int main(){
    n[0].val=0;n[1].val=1;n[2].val=2;n[3].val=3;
    n[0].next.push_back(&n[2]);n[2].next.push_back(&n[0]);
    n[1].next.push_back(&n[2]);n[2].next.push_back(&n[1]);
    n[1].next.push_back(&n[3]);n[3].next.push_back(&n[1]);
    n[0].next.push_back(&n[3]);n[3].next.push_back(&n[0]);
    bfsTrave();
    system("pause");
    return 0;
}

转载于:https://www.cnblogs.com/littlepage/p/11546548.html

本文来源weixin_30595035,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/29260

发表评论