当前位置：首页 > news >正文

关于图论的知识

news 来源：原创 2025/6/19 2:49:39

如果一个无向图有 $n\times (n-1)\div 2$ 条边，称为**完全图**

如果一个完全图任意两个点都可以互相到达，称为**连通图**

一个包含 $dfs$ 与 $bfs$ 的图的遍历程序

程序可做到的：

1、每一行输出一个 **搜索树**

2、$dfs$ 与 $bfs$ 并存

```cpp
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n,m;//有n个节点，m条边
vector<int> a[1005];
bool vis[1005];

void dfs(int u)
{
   vis[u] = true;
   cout<<u<<' ';
   for(int i=0;i<a[u].size();i++)
   {
       int v = a[u][i];
       if(vis[v]==false)
       {
           dfs(v);
       }
   }
}

void bfs(int u)
{
   queue<int> q;
   q.push(u);
   vis[u] = true;

   while(q.size())
   {
       u = q.front();
       cout<<u<<' ';
       q.pop();
       for(int i=0;i<a[u].size();i++)
       {
           int v = a[u][i];
           if(vis[v]==false)
           {
               q.push(v);
               vis[v] = true;
           }
       }
   }
}

int main()
{
   cin>>n>>m;
   for(int i=1;i<=m;i++)
   {
       int u,v;
       cin>>u>>v;

       a[u].push_back(v);
       a[v].push_back(u);
   }

   for(int i=1;i<=n;i++)
   {
       if(vis[i]==false)
       {
           //dfs(i);
           bfs(i);
           cout<<endl;
       }
   }
   return 0;
}
```

实际上，也可以用 $list$ 链表，也就是前向星，它避免了缺点收集了优点

```cpp
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e4+5;
struct node
{
   int u;
   int v;
   int next;
}a[N];
int n,m;//m条边，节点的编号为1~n
int tot;
int head[N];
int vis[N];

void add(int u,int v)
{
   a[++tot].u = u;
   a[tot].v = v;
   a[tot].next = head[u];
   head[u] = tot;
}

void dfs(int u)
{
   cout<<u<<' ';
   vis[u] = true;

   for(int i=head[u];i!=-1;i=a[i].next)
   {
       int v = a[i].v;
       if(vis[v]==false)
       {
           dfs(v);
       }
   }
}

int main()
{
   memset(head,-1,sizeof(head));
   cin>>n>>m;
   for(int i=1;i<=m;i++)//m条边
   {
       int u,v;
       cin>>u>>v;

       add(u,v);
       add(v,u);
   }

   for(int i=1;i<=n;i++)
   {
       if(vis[i]) continue;
       dfs(i);
       cout<<endl;
   }
   return 0;
}
```

然后就是判环代码，实际上就是看当前 $u$ 节点是否被访问过即 $vis[u]==true$ ，但注意父节点不要误判为环了

```cpp
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n,m;//有n个节点，m条边
vector<int> a[1005];
bool vis[1005];

void dfs(int u,int f)
{
   vis[u] = true;
//   cout<<u<<' ';
   for(int i=0;i<a[u].size();i++)
   {
       int v = a[u][i];
       if(vis[v]==false) dfs(v,u);
       else if(v!=f)
       {
           cout<<"have circle";
           exit(0);
       }
   }
}

int main()
{
   cin>>n>>m;
   for(int i=1;i<=m;i++)
   {
       int u,v;
       cin>>u>>v;

       a[u].push_back(v);
       a[v].push_back(u);
   }

   for(int i=1;i<=n;i++)
   {
       if(vis[i]==false)
       {
           dfs(i,-1);
       }
   }
   cout<<"have no circle";
   return 0;
}

```

很明显，上面的代码是一个无向图的代码，所以我再编写一个有向图的

```cpp
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n,m;//有n个节点，m条边
vector<int> a[1005];
int vis[1005];
/*定义vis[i]为i节点的访问状态，0=未访问，1=正在访问，-1=访问过且已经结束*/

void dfs(int u)
{
   vis[u] = 1;
//   cout<<u<<' ';
   for(int i=0;i<a[u].size();i++)
   {
       int v = a[u][i];
       if(vis[v]==0) dfs(v);
       if(vis[v]==1)
       {
           cout<<"have circle";
           exit(0);
       }
   }
   vis[u] = -1;
}

int main()
{
   cin>>n>>m;
   for(int i=1;i<=m;i++)
   {
       int u,v;
       cin>>u>>v;

       a[u].push_back(v);//这是一个有向图
       //a[v].push_back(u);
   }

   for(int i=1;i<=n;i++)
   {
       if(vis[i]==0) dfs(i);
   }
   cout<<"have no circle";
   return 0;
}
```

相关文章：