投稿
  1. 首页
  2. 随笔

图论（一）：图结构与图的遍历

v27 • 2022-10-21 • 随笔 • 阅读 6

图论（一）：图结构与图的遍历,第1张

图论（一）：图结构与图的遍历

目录

一 图的结构

二 图的广度优先遍历

2.1 原理

2.2 具体实现：

 2.3 复杂度分析：

三 图的深度优先遍历

3.1 原理：

3.2 具体实现：

3.3 复杂度分析

四 测试样例

一 图的结构

        一般我们用 G(V,E)这个集合表示一个图，V代表图中所有顶点的集合，E代表图中所有顶点的边集合。

        在计算机中，我们可用两种数据结构来表示图，这两种数据结构各有优劣：

  • 邻接链表：

        邻接链表用包含|V|条链表的数组Adj构成，每个节点有一条链表，对于每个节点  ，邻接链表Adj[u]包含所有与节点u相连的节点。保存权重只需在节点内加个权重值即可。

        当图是一个稀疏图时，临界链表占据的空间小，|V|个顶点与2|E|条边，总空间复杂度为 ，因此是稀疏图时我们选择用邻接链表表示图。缺点是找到某两个节点是否相邻较慢。

  • 邻接矩阵：

        邻接矩阵使用一个二维数组保存。抽象为矩阵A，矩阵内元素 有：

         

         有权图时可将1换为权值。邻接矩阵所消耗的空间为 ，在稠密的图（|E|很大）时我们更多选择邻接矩阵，同时邻接矩阵判断两个节点是否是邻居只需要常数时间，这也是它的优势

二 图的广度优先遍历 2.1 原理

        给定一个图G(V,E)和一个源节点s，广度优先搜索可以发现从源节点s到达的所有节点。广度优先搜索的核心思想是：发现所有距离源节点s为k的所有节点后才会发现距离源节点s为k+1的节点。在遍历的过程中，我们可以获得以下信息并保存下来：

  • 源节点s到每个可到达节点的距离（最少的边数）
  • 每个节点在此遍历下的前一个遍历到的节点
  • 一棵广度优先搜索树

        我们用队列来存储遍历到的节点，为了控制算法，每个节点都有三种颜色状态，用color[]数组表示：

  • 白色：该节点未被找到
  • 灰色：该节点被找到但还在队列中
  • 黑色：该节点被找到且其邻居都被遍历到队列中

伪代码如下：

2.2 具体实现 
#include 
#include 
#include 
using namespace std;

typedef enum {WHITE,GRAY,BLACK} color;//白色代表未被发现；灰色代表该节点已被发现但是该节点没有寻找完；黑色代表已经处理完

typedef struct {
    int vertex = 0;
    vector* adjacency[20]{};
}Graph;


void BFS(Graph g,int start,int d[],int p[],int c[]){
    //init
    for(int i=1;i<=g.vertex;i++){
        p[i] = 0;//没有前驱节点
        if(i != start){//不是起始节点
            c[i] = WHITE;
            d[i] = INT_MAX;
        } else{
            c[i] = GRAY;
            d[i] = 0;
        }
    }
    queue queue;
    queue.push(start);//将起始节点放入栈中
    while(!queue.empty()){
        int front = queue.front();//取队列首节点
        queue.pop();
        for(int adjacency_vertex_seq:*(g.adjacency[front])){//对该节点的邻接节点遍历
            if(c[adjacency_vertex_seq] == WHITE){
                c[adjacency_vertex_seq] = GRAY;//该节点已被遍历
                d[adjacency_vertex_seq] = d[front]+1;
                p[adjacency_vertex_seq] = front;
                queue.push(adjacency_vertex_seq);//进队列
            }
        }
        c[front] = BLACK;//队首节点的邻居已经全部遍历完成
    }
}
 2.3 复杂度分析

        该算法花费时间T(n)主要有以下几个部分组成：

  • 初始化 *** 作：
  • 每个节点入队与出队的 *** 作：
  • 每个节点出队时扫描该节点的邻接链表，所有邻接链表的长度为，用于扫描邻接链表的总时间为

        因此广度优先搜索的时间复杂度为：

        空间复杂度主要在邻接链表的花费与队列的空间。

三 图的深度优先遍历 3.1 原理

        深度优先搜索所使用的策略是：只要可能，就在图中“深入”。如果一个节点 v 有邻居节点，那就遍历 v 的邻居节点，当 v 所有子节点都被遍历完成后，搜索则回溯到 v 的前驱节点。

        我们使用递归来实现一直深入的形式，每个节点同样有三种颜色，与BFS类似：

  • 白色：该节点未被找到
  • 灰色：该节点被找到但还在遍历它的子节点
  • 黑色：该节点的子节点都被遍历，回溯到该节点

        通过一次DFS遍历，我们能捕捉以下信息：

  • 一个节点被发现的时间，用d[]存储
  • 一个节点变成黑色的时间，用f[]存储
  • 节点的前驱节点，用p[]存储

伪代码如下：

3.2 具体实现 
#include 
#include 
#include 
using namespace std;

typedef enum {WHITE,GRAY,BLACK} color;//白色代表未被发现；灰色代表该节点已被发现但是该节点没有寻找完；黑色代表已经处理完

typedef struct {
    int vertex = 0;
    vector* adjacency[20]{};
}Graph;

int time;//DFS的全局时间


void DFS_VISIT(int node,Graph g,int d[],int f[],int p[],int c[]){
    c[node] = GRAY;//正在DFS
    d[node] = time++;//全局时间+1
    for(int adjacency_vertex_seq:*(g.adjacency[node])){//遍历所有邻居节点
        if(c[adjacency_vertex_seq] == WHITE){
            p[adjacency_vertex_seq] = node;//设置子节点的前驱结点
            DFS_VISIT(adjacency_vertex_seq,g,d,f,p,c);
        }
    }
    c[node] = BLACK;//该节点结束遍历
    f[node] = time++;
}


void DFS(Graph g,int d[],int f[],int p[],int c[]){
    //init
    for(int i=1;i<=g.vertex;i++){
        c[i] = WHITE;//所有节点未被发现
        p[i] = 0;//没有前驱节点
    }
    time = 1;
    //开始遍历
    for(int i=1;i<=g.vertex;i++){
        if(c[i] == WHITE){
            DFS_VISIT(i,g,d,f,p,c);
        }
    }
}
3.3 复杂度分析

        先不考察DFS_VISIT()，该算法花费时间T(n)主要有以下几个部分组成：

  • 初始化 *** 作：
  • 设置每个节点颜色为白色：

        对于每个节点，DFS_VISIT()恰好能调用一次，伪代码第4-7行执行次数为 |Adj[v]| 。而 ，因此深度优先搜索的时间复杂度为

四 测试样例
  • BFS

        

  • DFS

        

 测试代码：

#include 
#include 
#include 
using namespace std;

typedef enum {WHITE,GRAY,BLACK} color;//白色代表未被发现；灰色代表该节点已被发现但是该节点没有寻找完；黑色代表已经处理完

typedef struct {
    int vertex = 0;
    vector* adjacency[20]{};
}Graph;

int time;//DFS的全局时间


void BFS(Graph g,int start,int d[],int p[],int c[]){
    //init
    for(int i=1;i<=g.vertex;i++){
        p[i] = 0;//没有前驱节点
        if(i != start){//不是起始节点
            c[i] = WHITE;
            d[i] = INT_MAX;
        } else{
            c[i] = GRAY;
            d[i] = 0;
        }
    }
    queue queue;
    queue.push(start);//将起始节点放入栈中
    while(!queue.empty()){
        int front = queue.front();//取队列首节点
        queue.pop();
        for(int adjacency_vertex_seq:*(g.adjacency[front])){//对该节点的邻接节点遍历
            if(c[adjacency_vertex_seq] == WHITE){
                c[adjacency_vertex_seq] = GRAY;//该节点已被遍历
                d[adjacency_vertex_seq] = d[front]+1;
                p[adjacency_vertex_seq] = front;
                queue.push(adjacency_vertex_seq);//进队列
            }
        }
        c[front] = BLACK;//队首节点的邻居已经全部遍历完成
    }
}

void DFS_VISIT(int node,Graph g,int d[],int f[],int p[],int c[]){
    c[node] = GRAY;//正在DFS
    d[node] = time++;//全局时间+1
    for(int adjacency_vertex_seq:*(g.adjacency[node])){//遍历所有邻居节点
        if(c[adjacency_vertex_seq] == WHITE){
            p[adjacency_vertex_seq] = node;//设置子节点的前驱结点
            DFS_VISIT(adjacency_vertex_seq,g,d,f,p,c);
        }
    }
    c[node] = BLACK;//该节点结束遍历
    f[node] = time++;
}


void DFS(Graph g,int d[],int f[],int p[],int c[]){
    //init
    for(int i=1;i<=g.vertex;i++){
        c[i] = WHITE;//所有节点未被发现
        p[i] = 0;//没有前驱节点
    }
    time = 1;
    //开始遍历
    for(int i=1;i<=g.vertex;i++){
        if(c[i] == WHITE){
            DFS_VISIT(i,g,d,f,p,c);
        }
    }

}



int main(){
    //第一个图
    Graph graph;
    graph.vertex = 7;
    vector a = {2,5};
    vector b = {1,3,6,7};
    vector c = {2,4};
    vector d = {3,5};
    vector e = {1,4,6,7};
    vector f = {2,5};
    vector s = {2,5};//起始节点 7号
    graph.adjacency[1] = &a;
    graph.adjacency[2] = &b;
    graph.adjacency[3] = &c;
    graph.adjacency[4] = &d;
    graph.adjacency[5] = &e;
    graph.adjacency[6] = &f;
    graph.adjacency[7] = &s;

    //第二个图
    Graph graph2;
    graph2.vertex = 7;
    vector a2 = {2,5};
    vector b2 = {1,5,6};
    vector c2 = {4};
    vector d2 = {3,7};
    vector e2 = {1,2,6};
    vector f2 = {2,5};
    vector g2 = {4};//起始节点 7号
    graph2.adjacency[1] = &a2;
    graph2.adjacency[2] = &b2;
    graph2.adjacency[3] = &c2;
    graph2.adjacency[4] = &d2;
    graph2.adjacency[5] = &e2;
    graph2.adjacency[6] = &f2;
    graph2.adjacency[7] = &g2;

    int distance1[graph.vertex+1],distance2[graph.vertex+1];
    int finish2[graph.vertex+1];
    int predecessor1[graph.vertex+1],predecessor2[graph.vertex+1];
    int color1[graph.vertex+1],color2[graph.vertex+1];
    BFS(graph,7,distance1,predecessor1,color1);
    DFS(graph2,distance2,finish2,predecessor2,color2);

    cout<<"BFS"< 

 测试结果：
 

 

 

 

 

 

					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/3971490.html
赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
v27 v27 一级用户组
0 0
上一篇 2022-10-21
下一篇 2022-10-21

发表评论

登录后才能评论

评论列表（0条）

保存