数据结构：图的存储与遍历

目录

一、基本概念和一般结论

二、图的存储结构

2.1、邻接矩阵

2.2、邻接表

2.3、链式前向星

2.4、vector简洁存储

三、图的遍历

3.1、深度优先遍历DFS

3.2、广度优先遍历

3.3、多源BFS

四、应用

4.1、判断无向图是否连通及连通分量数目

4.2、判断图中顶点u到v是否存在路径

4.3、给定n个顶点的有向无环图，输出顶点0到顶点n-1的所有路径

4.4、判断无向图中是否有环

4.5、判断有向图中是否有环

4.5.1、三色标记法

4.5.2、拓扑排序

---

        图（Graph）是一种较线性表和树更为复杂的非线性结构。在图结构中，对结点（图中常称为顶点）的前驱和后继个数不加限制， 即结点之间的关系是任意的。

一、基本概念和一般结论

因为一条边关联两个顶点，而且使得这两个顶点的度数 分别增加1。因此顶点的度数之和就是边的两倍。

---

关于连通图：

无向图：连通图，连通子图，极大连通子图（连通分量，即一个图中最大的某个连通子图，即无法增加顶点以及边 使其构成更大的连通图）。无向图的连通关系是等价关系，具有传递性，自反性以及对称性。

有向图：强连通图，强连通子图，强连通分量。

连通分量不一定唯一。

二、图的存储结构

2.1、邻接矩阵

邻接矩阵可以方便求出图中顶点的度：

对于邻接矩阵的第i行，如果其第j列有一个1（或者一个权值），则说明有一条边从vi指向vj。如果是有向图，则表示存在一条边<vi,vj>，通过行可以看出出度，通过列可以看出入度。

---

2.2、邻接表

        总的来说就是，顺序存储图中的所有顶点信息，每个顶点信息包括顶点编号（也可以不用，因为顺序存储用数组标识的话，数组位置就是顶点编号），以及顶点的边链表头结点指针。一个顶点的边链表是将 以该顶点为起始的 连向的其他顶点信息。

       有向图的邻接表，边链表结点个数等于有向边的条数。（因为每条有向边有且仅有一个起始和一个终止）

        无向图的邻接表，边链表结点个数等于无向边的条数*2。（无向边是双向的）

struct Edge{//边链表结点
    int VerName;//顶点编号
    int cost;//边权值
    Edge *next;//指向下一个边链表结点
}
struct Vertex{//顶点表结点
    int VerName;//顶点编号
    Edge * adjacent;//边链表指针
}

2.3、链式前向星

        实际上就是使用静态链表实现的邻接表。数据结构：静态链表（编程技巧）-CSDN博客

这样做的好处是，不需要使用指针，也不需要使用指针访问，直接通过数组下标即可访问，速度更快，内存更少。

插入表尾：

vector<int> head(n,-1);//n个顶点，head[i]指向边链表，初始都没有
vector<int> VerName;//边链表，adjacent[i]存的是边链表顶点信息
vector<int> next;//边链表的指针信息
vector<int> cost;//边的权值
/*可以理解为：
struct head{
    Edge* head[i];//head[i]表示的是第i个顶点的边链表表头。这里实际上是一个下标
}
struct Edge{//他们仨 下标是一样的
    int VerName;
    Edge* next;
    int cost;
};
*/
int Vertex;
int edge;
int cos;
 
while(cin>>Vertex>>edge>>cos){//假定输入都是正确的，没有重边
    //为了复杂化，我们先找到边链表的最后一个结点
    int adj=head[Vertex];
    if(adj!=-1)
        while(next[adj]!=-1){
            adj=next[adj];
        }
    /*创建一个新结点 其之后无指向即next=-1*/
    VerName.push_back(edge);
    next.push_back(-1);
    cost.push_back(cos);
    /*-adj为Vertex边链表的最后一个元素-*/
    if(adj!=-1)
        next[adj]=next.size()-1;//VerName.size()-1、cost.size()-1均可 就是指向最后一个嘛。
    if(adj==-1){//只可能是顶点还没有边
        head[Vertex]=next.size()-1;
    }
}
 
//顺次输出边
for(int i=0;i<n;++i){
    int adj=head[i];
    while(adj!=-1){
        cout<<i<<"--->"<<VerName[adj]<<"  cost为:"<<cost[adj]<<endl;
        adj=next[adj];
    }
}
//我们会发现，将adj当做一个结构体指针Edge *，那么VerName[adj]相当于adj->VerName了

直接插入表头：

while(cin>>Vertex>>edge>>cos){/*直接创建点，插入在Vertex的边链表表头*/
    VerName.push_back(edge);
    next.push_back(head[Vertex]);
    cost.push_back(cos);
    head[Vertex]=next.size()-1;
}

2.4、vector简洁存储

由于STL中vector的引用，实际上vector也很像一个链表了，所以我们已经不需要写邻接表来存储。

vector<vector<pair<int,int> > > g(n);//使用pair<int,int> first存储顶点信息，second存储边权值
//如果包含更多信息可以自定义结构体。
while(cin>>Vertex>>edge>>cos){/*直接创建点，插入在Vertex的边链表表头*/
    g[Vertex].emplace_back(edge,cost);
}
 
//g[i] 是一个vector<pair<int,int> > 类型，存储的是顶点i的边链表
//g[i].size()==0 则没有出边

三、图的遍历

3.1、深度优先遍历DFS

#include<bits/stdc++.h>
using namespace std;
#define n 100
struct Edge {
    int VerName;
    int cost;
    Edge * next=nullptr;
};
struct Vertex{
    int VerName;
    Edge *edge=nullptr;
};
int vis[n];
Vertex Head[n];
void DFS(Vertex *Head,int v,int vis[]) {
    vis[v]=1;//遍历到则标记，也可以入栈时标记，DFS每次只走一条路，所以无所谓都一样。
    printf("%d ",v);
    for(Edge * edge=Head[v].edge;edge!=nullptr;edge=edge->next)
        if(!vis[edge->VerName])
            DFS(Head,edge->VerName,vis);
    return;
}
int main(void){
    for(int i=0;i<n;++i)//非连通图，需要从多个非连通分量开始遍历。
        if(vis[i]==0)
            DFS(Head,i,vis);
    return 0;
}

3.2、广度优先遍历

#include<bits/stdc++.h>
using namespace std;
#define n 100
struct Edge {
    int VerName;
    int cost;
    Edge * next=nullptr;
};
struct Vertex{
    int VerName;
    Edge *edge=nullptr;
};
int vis[n];
Vertex Head[n];
void BFS(Vertex *Head,int v,int vis[]) {
    queue<int> q;
    vis[v]=1;
    q.push(v);
    while(!q.empty()) {
        int cur=q.front();
        printf("%d ",cur);
        q.pop();
        for(Edge * edge=Head[cur].edge;edge!=nullptr;edge=edge->next) {
            if(!vis[edge->VerName]) {
                vis[edge->VerName]=1;//入队时标记，防止多次入队
                q.push(edge->VerName);
            }
        }
    }
    return;
}
int main(void){
    for(int i=0;i<n;++i)
        if(vis[i]==0)
            BFS(Head,i,vis);
    return 0;
}

3.3、多源BFS

        主要思路大概是初始时，多个点进入队列然后进行BFS。将某一等价集合视作同一个起始点（超级源点），先将此源点入队，再一层一层向外扩张。相当于这些初始出队的源点在整个问题中地位等价。另外还可以视作不同的起点同时进行BFS操作，而不需要依次作为起点依次BFS，有时写在一起更方便。

queue<int> q;
for(auto i:graph) 
    if(start(i)==true)//如果i是起点的话就入队
        q.push(i);
 
while(!q.empty()){//所有起点一起BFS
    //BFS
}

四、应用

4.1、判断无向图是否连通及连通分量数目

（1）图的遍历：每遍历一次会遍历图的一个连通分量，与该连通分量不连通的必须再次遍历。

int cnt=0;
for(int i=0;i<n;++i){
    if(!vis[i]){
        cnt++;
        DFS(Head,i,vis);//BFS(Head,i,vist);
    }
}

（2）并查集：将存在边的两个顶点放入一个并查集中，可以找到连通分量数目

4.2、判断图中顶点u到v是否存在路径

这里无向图有向图均可，所以实际上只需要从u开始遍历，能遍历到v则说明存在路径。

DFS(Head,u,vis);//BFS(Head,u,vis);
if(vis[v]==1) printf("u到v存在路径");
 
//修改DFS：
bool DFS(Vertex * Head,int u,int vis[]){
    if(u==v) return true;
    for(Edge * edge=Head[u].edge;edge!=nullptr;edge=edge->next){
        if(vis[edge->VerName]==0){
            vis[edge->VerName]=1;
            if(DFS(Head,edge->VerName,vis)) return true;
        }
    }
    return false;
}
main:
vis[u]=1;
if(DFS(Head,u,vis)) printf("u到v存在路径");

4.3、给定n个顶点的有向无环图，输出顶点0到顶点n-1的所有路径

        这里实际上是一个回溯问题，对于有向无环图，它不可能往回走，并且需要输出所有路径，我们甚至不用标记点（不标记点的两个原因：①有向无环图在递归遍历时不可能走重复路径②同一个点在不同路径上可以重复遍历）。

#define n 100
struct Edge {
    int VerName;
    int cost;
    Edge * next=nullptr;
};
struct Vertex{
    int VerName;
    Edge *edge=nullptr;
};
Vertex Head[n];
 
vector<vector<int>> Allpath;
vector<int> path;
 
void FindPath(Vertex *Head,int u){
    path.push_back(u);
    if(u==n-1){
        Allpath.push_back(path);
        path.pop_back();
        return;
    }
    for(Edge * edge=Head[u].edge;edge!=nullptr;edge=edge->next) {
        FindPath(Head,edge->VerName);
    }
    path.pop_back();
    return;
}
 
main:
FindPath(Head,0,n-1);

4.4、判断无向图中是否有环

（1）深度优先遍历：访问的过程中遇到非前驱并且被访问过的顶点，则有环。

这必然是可以找到的，如果存在环，进入该环的任意一个点开始遍历，一定可以通过若干步后回到该点。

（2）并查集：每次读入一条边(x,y)，先判断x和y是否具有连通性（并查集），如果具有连通性，那么说明原本x就可以走到y，现在加入边(x,y)就构成了环。

while(cin>>x>>y){
    if(Find(x)==Find(y)
        return true;
    else Union(x,y);
}

4.5、判断有向图中是否有环

4.5.1、三色标记法

        对于一个有向图，在DFS遍历的过程中访问到已经被遍历的顶点，这并不一定就是当前路径上的点。因此我们需要不同的标记：多标记法。DFS：O(n+e)

从未被遍历过vis[i]=0;

正在遍历的路径上vis[i]=1;

已经遍历完的路径上vis[i]=2;//可以想象二叉树的结果理解什么时候回变成vis[i]=2，根的左子树遍历时不会影响到右子树，左子树遍历完了 则有 左子树vis[i]=2

只有遍历到vis[i]=1的点，才构成环。

#include<bits/stdc++.h>
using namespace std;
#define n 100
struct Edge {
    int VerName;
    int cost;
    Edge * next=nullptr;
};
struct Vertex{
    int VerName;
    Edge *edge=nullptr;
};
int vis[n];
Vertex Head[n];
bool DFS(Vertex * Head,int u,int vis[]) {
    vis[u]=1;
    for(Edge * edge=Head[u].edge;edge!=nullptr;edge=edge->next) {
        if(vis[edge->VerName]==1) return true;//遍历到了！
        if(vis[edge->VerName]==0)//等于2的情况下 已经遍历完了的，不需要再遍历了
            if(DFS(Head,edge->VerName,vis)) return true;
    }
    vis[u]=2;//它的邻居遍历完了，它也没地方走了
    return false;
}
int main(void){
    for(int i=0;i<n;++i)
        if(vis[i]==0)
            if(DFS(Head,i,vis)) printf("存在环!\n");
    return 0;
}

（虽然无向图也不一定是当前路径但是 已经被遍历过的顶点v一定与当前顶点u是连通的（有路径可走，如v-->原点-->u），然后还有现在的一条边(v,u)，因此一定构成环）。

4.5.2、拓扑排序

O(n+e)

数据结构：图的拓扑排序与关键路径-CSDN博客