图的存储遍历的方式

• 图的矩阵存储
  • 效率高：可以用O(1)时间复杂度的时间判断两点间是否有边。
  • 插入边和删除边的操作简单：O(1)。
  • 消耗空间大：达到 n^2 的大空间，空间浪费很多。

#include<iostream>
#include<queue>
using namespace std;
int n,m,u,v;
bool vis[1001],g[1001][1001];
void dfs(int u)
{
    cout<<u<<" ";
    vis[u]=1;
    for(int i=1;i<=n;i++)
        if(g[u][i]&&!vis[i])
            dfs(i);
}
void bfs(int s)
{
    queue<int>q;
    q.push(s);
    vis[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        cout<<u<<" "; 
        for(int i=1;i<=n;i++)
        {
            if(g[u][i]&&vis[i])
            {
                q.push(i);
                vis[i]=1;
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v;
        g[u][v]=g[v][u]=1; //无向图
//      g[u][v]=1;           有向图 
    }
    for(int i=1;i<=m;i++)
        if(!vis[i])
            dfs(i);
    
    return 0;
}

• 图的vector链表存储
  • 空间小：O(m)(m代表边数)
  • 访问快：O(1)
  • 不利于删边,路径跟踪不方便.

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct edge{
    int u,v;
//  int w;   权值
};
vector<int>g[1001];
int n,m,u,v,vis[1001];
bool flag;
void dfs(int u,int fa)
{
    cout<<u<<" ";
    vis[u]=1;
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        if(v==fa)continue;//不能往回走，不然【1】->【3】再从【3】->【1】时就会显示有环
        if(!vis[v])dfs(v,u);
        else flag=true;  //判环
    }
}
void bfs(int s)
{
    queue<int>q;
    q.push(s);
    vis[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        cout<<u<<" ";
        for(int i=0;i<g[u].size();i++)
        {
            int v=g[u][i];
            if(!vis[v])
            {
                q.push(v);
                vis[v]=1;
            }
            else flag=true;
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
        if(!vis[i])
            dfs(i,-1);
//          bfs(i);
    if(flag)cout<<"\nhave circle!\n";
    else cout<<"\nhave no circle!\n";
    return 0;
}

• 图的链式前向星存储
  • 效率高：由于是用数组模拟，效率比vector还快
  • 空间小
  • 可以比较方便的删除某一条边

#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
struct edge {
    int u,v,next;
}g[100001];
int head[1001],n,m,u,v,vis[1001],tot;
void addedge(int u,int v)
{
    g[++tot].u=u;
    g[tot].v=v;
    g[tot].next=head[u];
    head[u]=tot;
}
void dfs(int u)
{
    cout<<u<<" ";
    vis[u]=1;
    for(int i=head[u];i!=-1;i=g[i].next)
    {
        int v=g[i].v;
        if(!vis[v])dfs(v);
    }
}
void bfs(int s)
{
    queue<int>q;
    q.push(s);
    vis[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        cout<<u<<" "; 
        for(int i=head[u];i!=-1;i=g[i].next)
        {
            int v=g[u].v;
            if(!vis[v])
            {
                q.push(v);
                vis[v]=1;
            }
        }
    }
}
int main()
{
    memset(head,-1,sizeof(head));
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v;
        addedge(u,v);
        addedge(v,u);
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
//          dfs(i);
            bfs(i); 
        }
    }
    return 0;
}