图的创建和遍历

作者: 骑猪满天飞 | 来源:发表于2021-01-02 21:51 被阅读0次

图的定义

数据结构中，图由顶点和边构成如下：

图1

上图中数字代表顶点（Vertex）,连接顶点的是边（Edge），通过边表示顶点之间的逻辑关系。

无向图

定义：若表示顶点关系的边没有方向（无向边），则此图为无向图，如图1。顶点Vi到Vj之间的边表示为(Vi,Vj)，代表Vi，Vj邻接。
顶点的度：

与某个顶点有关的边的数量，代表此顶点的度。如图1，顶点1的度为2。
完全无向图

无向图中，如果每个顶点都存在到其他顶点的边，则此图为完全无向图：

UnGraph.png

完全无向图有n(n-1)/2条边，n为顶点数。

有向图

定义

当顶点之间的边有方向时，图为有向图。如下：

directed.png

并使用有序对<Vi，Vj>来表示顶点Vi，Vj之间的边，称为弧。Vi称为弧尾，Vj为弧头。例如，上图顶点A、D之间的边表示为：<A,D>表明方向A->D

出度、入度

以顶点Vi为弧尾的弧数量，表示Vi的出度，以顶点Vi为弧头的数量，表示Vi的入度。
完全有向图

任意顶点存在互为相反方向的边，称为完全有向图

网

图中的边或弧，存在对应的数字，这样的图称为网，边或弧对应的数字称为权。

network.png

上图的权值表示距离。

连通性

连通图

在无向图G中，存在从Vi到Vj的路径，则称Vi和Vj是连通的。如果G中任意两个顶点都是连通的，则称G为连通图。

connected.png

无向图中的极大连通子图称为连通分量，连通分量条件：

子图
子图要是连通的
连通子图含有极大顶点数

强连通图

在有向图G中，对于任意Vi,Vj,存在Vi->Vj 和Vj->Vi的路径，则称G是强连通图。

有向图的极大强连通子图称为强连通分量

图的存储结构

邻接矩阵

使用两个数组来表示图。

一个一维数组Vertex表示顶点
一个二维数组edge表示边。

edge[i][j]= W       //表示权值
            0       //i=j
            Infinty // 表示边(i,j)不存在

Adjcency Matrix.png

邻接表

邻接表与邻接矩阵相比，使用链表代替二维数组。对于边数比顶点数少的情况，邻接矩阵存在着巨大的浪费，而使用链式结构可以很好的避免浪费。

使用一个一维数组表示顶点
使用单链表来表示每个顶点的邻接顶点

Adjcency List.png

其他结构

十字链表、多重邻接表

十字链表作用于有向图、多重邻接表作用于无向图，都是邻接表的进阶版本，不做详细介绍

邻接表代码实现

边节点结构：

typedef struct EdgeNode{                            //边节点
        int adjVertex;
        Tweight weight;                             //权重
        EdgeNode* next;c++
}EdgeNode;

顶点节点结构：

typedef struct VertexNode {                     //顶点节点
        Tvertex vertex;                             //顶点值
        EdgeNode* firstEdge;                        //指向的边
}VertexNode;

类声明：

template<typename Tvertex, typename Tweight>
class UndirectedGraph                               //邻接表实现无向图
{
private:
    typedef struct EdgeNode{                        //边节点
        int adjVertex;
        Tweight weight;                             //权重
        EdgeNode* next;
    }EdgeNode;

    typedef struct VertexNode {                     //顶点节点
        Tvertex vertex;                             //顶点值
        EdgeNode* firstEdge;                        //指向的边
    }VertexNode;

    std::vector<VertexNode> graph;                  //保存顶点的数组
    int verxNums;                                   //顶点数量
    int edgeNums;                                   //边数量
public:
    UndirectedGraph(int vn = 0,int en = 0):verxNums(vn),edgeNums(en){}
    void CreateGraph();
    void CreateGraph(std::vector<Tvertex> vertex, 
        std::pair<std::vector<int>, Tweight> edgeWeight[]);
    
};

图创建函数：

template<typename Tvertex, typename Tweight>
void UndirectedGraph<Tvertex, Tweight>::CreateGraph() {
     //初始化顶点数组
    for (int i = 0; i < verxNums; i++) {
        VertexNode* v = new VertexNode;
        std::cout << "Input vertex "<< i <<" value:" << std::endl;
        std::cin >> v->vertex;
        v->firstEdge = nullptr;
        graph.push_back(*v);
    }
    
    //为顶点添加相关的边信息
    for (int nums = 0; nums < edgeNums; nums++) {
        int i, j;
        Tweight weight;
        std::cout << "Input the i,j of (vi,vj): ";
        std::cin >> i >> j;
        std::cout << "Input the weight of (vi,vj): ";
        std::cin >> weight;

        EdgeNode* e = new EdgeNode;                 //添加(vi,vj)
        e->adjVertex = j;
        e->weight = weight;
        e->next = graph[i].firstEdge;               //插入边节点
        graph[i].firstEdge = e;

        e = new EdgeNode;                           //无向图还需要添加(vj,vi)
        e->adjVertex = i;                           
        e->weight = weight;
        e->next = graph[j].firstEdge;
        graph[j].firstEdge = e;
    }
}

为方便测试，编写了一个静态生成图的函数,内容基本一样，该函数从一个节点数组std::vector<Tvertex> vertex读入节点信息，一个pair结构数组std::pair<std::vector<int>, Tweight> edgeWeight[]表示边和权值：

template<typename Tvertex, typename Tweight>
void UndirectedGraph<Tvertex, Tweight>::CreateGraph(std::vector<Tvertex> vertex, 
    std::pair<std::vector<int>, Tweight> edgeWeight[]) {
    for (int i = 0; i < verxNums; i++) {
        VertexNode* v = new VertexNode;
        v->vertex = vertex[i];
        v->firstEdge = nullptr;
        graph.push_back(*v);
    }
    for (int nums = 0; nums < edgeNums; nums++) {

        int i, j;
        Tweight weight;
        i = edgeWeight[nums].first[0];
        j = edgeWeight[nums].first[1];
        weight = edgeWeight[nums].second;

        EdgeNode* e = new EdgeNode;                 //添加(vi,vj)
        e->adjVertex = j;
        e->weight = weight;

        e->next = graph[i].firstEdge;
        graph[i].firstEdge = e;

        e = new EdgeNode;
        e->adjVertex = i;                           //添加(vj,vi)
        e->weight = weight;

        e->next = graph[j].firstEdge;
        graph[j].firstEdge = e;
    }

    //显示相关信息
    for (auto v : graph) {
        std::cout << "Vertex: " << v.vertex << std::endl;
        std::cout << "Edges: ";
        for (auto p = v.firstEdge; p != nullptr;p = p->next) {
            std::cout << p->adjVertex << " ";
        }

        std::cout << std::endl;
        std::cout << std::endl;
    }
}

图的遍历

深度优先（Depth First Search）

与树的中根遍历模式一样类似

DFS.png

如上图是按照搜索右边的节点规则，进行深度优先遍历，从A开始不断深入搜索A->B->C->D->E->F->G->H,搜索完H发现没有未遍历的邻接点，开始回退，退回到D，然后访问I，完成所有节点的遍历。

深度优先遍历实现：

与二叉树的遍历一样使用递归
使用一个长度为顶点数的数组来标记顶点是否被访问

代码实现：

//声明
template<typename Tvertex, typename Tweight>
class UndirectedGraph                               //邻接表实现无向图
{
private:
    ...
    void DFS(std::vector<bool>& isVisted, int i);   //深度优先遍历递归调用函数，外部无需访问该方法申明为私有
    
public:
    ...         
    void DFSTraverse();
    ...
};

//定义
template<typename Tvertex, typename Tweight>
void UndirectedGraph<Tvertex, Tweight>::DFS(std::vector<bool>& isVisted,int i) {

    isVisted[i] = true;
    std::cout << graph[i].vertex << " ";
    for (auto p = graph[i].firstEdge; p != nullptr; p = p->next){   //遍历链表
        if (!isVisted[p->adjVertex]) {
            DFS(isVisted, p->adjVertex);                            //对链表元素继续DFS
        }
    }
    
}

template<typename Tvertex, typename Tweight>
void UndirectedGraph<Tvertex, Tweight>::DFSTraverse() {
    std::vector<bool> isVisted(verxNums,false);             //访问标识数组，初始化为false

    for (int i = 0; i < verxNums; i++) {                    //防止存在子图的情况，未遍历子图
        if (!isVisted[i]) {
            DFS(isVisted,i);
        }
    }
    std::cout << std::endl;
}

广度优先遍历

与树的层次遍历相似，一层一层往下遍历，对每一层做最大范围遍历。并且与树的层次遍历实现相同，使用队列保存未遍历元素

BFS.png

代码实现：

//声明
template<typename Tvertex, typename Tweight>
class UndirectedGraph                               //邻接表实现无向图
{
public:
    ...
    void BFSTraverse();
};

//定义
template<typename Tvertex, typename Tweight>
void UndirectedGraph<Tvertex, Tweight>::BFSTraverse() {
    std::vector<bool> isVisted(verxNums, false);
    std::queue<VertexNode> Q;
    VertexNode v;

    for (int i = 0; i < verxNums; i++) {        //防止存在子图的情况，未遍历子图
        if (!isVisted[i]) {
            Q.push(graph[i]);           
            isVisted[i] = true;
        }
        while (!Q.empty()) {
            v = Q.front();                      //去队头元素
            std::cout << v.vertex << " ";
            for (auto p = v.firstEdge; p != nullptr; p = p->next) {
                if (!isVisted[p->adjVertex]) {
                    Q.push(graph[p->adjVertex]);
                    isVisted[p->adjVertex] = true;
                }
            }
            Q.pop();        
            
        }
    }
    std::cout << std::endl; 
}

完整代码和测试

#pragma once
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <algorithm>


/********************************************
* 时间：2021/1/2
* 作者：tanghf
* 类简介：使用邻接表实现无向图
********************************************/
template<typename Tvertex, typename Tweight>
class UndirectedGraph                               //邻接表实现无向图
{
private:
    typedef struct EdgeNode{                        //边节点
        int adjVertex;
        Tweight weight;                             //权重
        EdgeNode* next;
    }EdgeNode;

    typedef struct VertexNode {                     //顶点节点
        Tvertex vertex;                             //顶点值
        EdgeNode* firstEdge;                        //指向的边
    }VertexNode;

    std::vector<VertexNode> graph;
    int verxNums;                                   //顶点数量
    int edgeNums;                                   //边数量

    void DFS(std::vector<bool>& isVisted, int i);   //深度优先遍历递归调用函数
public:
    UndirectedGraph(int vn = 0,int en = 0):verxNums(vn),edgeNums(en){}
    void CreateGraph(std::vector<Tvertex> vertex,       
        std::pair<std::vector<int>, Tweight> edgeWeight[]); //静态创建无向图
    void CreateGraph();                                     //动态输入创建无向图
    void DFSTraverse();
    void BFSTraverse();
};
    
    
template<typename Tvertex, typename Tweight>
void UndirectedGraph<Tvertex, Tweight>::CreateGraph(std::vector<Tvertex> vertex, 
    std::pair<std::vector<int>, Tweight> edgeWeight[]) {

    for (int i = 0; i < verxNums; i++) {
        VertexNode* v = new VertexNode;
        v->vertex = vertex[i];
        v->firstEdge = nullptr;
        graph.push_back(*v);
    }
    for (int nums = 0; nums < edgeNums; nums++) {

        int i, j;
        Tweight weight;
        i = edgeWeight[nums].first[0];
        j = edgeWeight[nums].first[1];
        weight = edgeWeight[nums].second;

        EdgeNode* e = new EdgeNode;                 //添加(vi,vj)
        e->adjVertex = j;
        e->weight = weight;

        e->next = graph[i].firstEdge;
        graph[i].firstEdge = e;

        e = new EdgeNode;
        e->adjVertex = i;                           //添加(vj,vi)
        e->weight = weight;

        e->next = graph[j].firstEdge;
        graph[j].firstEdge = e;
    }

    
    for (auto v : graph) {
        std::cout << "Vertex: " << v.vertex << std::endl;
        std::cout << "Edges: ";
        for (auto p = v.firstEdge; p != nullptr;p = p->next) {
            int adjVxIndex = p->adjVertex;
            std::cout << "(" << v.vertex << "," 
                << graph[adjVxIndex].vertex << "),weight = "<< p->weight<<" ";
        }

        std::cout << std::endl;
        std::cout << std::endl;
    }
}


template<typename Tvertex, typename Tweight>
void UndirectedGraph<Tvertex, Tweight>::CreateGraph() {
    //初始化顶点数组
    for (int i = 0; i < verxNums; i++) {
        VertexNode* v = new VertexNode;
        std::cout << "Input vertex " << i << " value:" << std::endl;
        std::cin >> v->vertex;
        v->firstEdge = nullptr;
        graph.push_back(*v);
    }

    //为顶点添加相关的边信息
    for (int nums = 0; nums < edgeNums; nums++) {
        int i, j;
        Tweight weight;
        std::cout << "Input the i,j of (vi,vj): ";
        std::cin >> i >> j;
        std::cout << "Input the weight of (vi,vj): ";
        std::cin >> weight;

        EdgeNode* e = new EdgeNode;                 //添加(vi,vj)
        e->adjVertex = j;
        e->weight = weight;
        e->next = graph[i].firstEdge;               //插入边节点
        graph[i].firstEdge = e;

        e = new EdgeNode;                           //无向图还需要添加(vj,vi)
        e->adjVertex = i;
        e->weight = weight;
        e->next = graph[j].firstEdge;
        graph[j].firstEdge = e;
    }

    //输出添加的信息
    for (auto v : graph) {
        std::cout << "Vertex: " << v.vertex << std::endl;
        std::cout << "Edges: ";
        for (auto p = v.firstEdge; p != nullptr; p = p->next) {
            std::cout << p->adjVertex << " ";
        }

        std::cout << std::endl;
        std::cout << std::endl;
    }
}

template<typename Tvertex, typename Tweight>
void UndirectedGraph<Tvertex, Tweight>::DFS(std::vector<bool>& isVisted,int i) {

    isVisted[i] = true;
    std::cout << graph[i].vertex << " ";
    for (auto p = graph[i].firstEdge; p != nullptr; p = p->next){
        if (!isVisted[p->adjVertex]) {
            DFS(isVisted, p->adjVertex);
        }
    }
    
}


template<typename Tvertex, typename Tweight>
void UndirectedGraph<Tvertex, Tweight>::DFSTraverse() {
    std::vector<bool> isVisted(verxNums,false);

    for (int i = 0; i < verxNums; i++) {
        if (!isVisted[i]) {
            DFS(isVisted,i);
        }
    }
    std::cout << std::endl;
}

template<typename Tvertex, typename Tweight>
void UndirectedGraph<Tvertex, Tweight>::BFSTraverse() {
    std::vector<bool> isVisted(verxNums, false);
    std::queue<VertexNode> Q;
    VertexNode v;

    for (int i = 0; i < verxNums; i++) {
        if (!isVisted[i]) {
            Q.push(graph[i]);
            isVisted[i] = true;
        }
        while (!Q.empty()) {
            v = Q.front();
        
            std::cout << v.vertex << " ";
            for (auto p = v.firstEdge; p != nullptr; p = p->next) {
                if (!isVisted[p->adjVertex]) {
                    Q.push(graph[p->adjVertex]);
                    isVisted[p->adjVertex] = true;
                }
            }
            Q.pop();
            
        }
    }
    std::cout << std::endl; 
}

对如下图进行测试：

minispantree.png

main:

int main() {
    UndirectedGraph<string,int> g(9,15);
    pair <vector<int>, int> edgeWeight[15] = {
        {{0,1},10},{{0,5},11},{{1,2},18},
        {{1,6},16},{{1,8},12},{{2,8},8},
        {{2,3},22},{{3,6},24},{{3,8},21},
        {{3,7},16},{{3,4},20},{{4,5},26},
        {{4,7},7},{{5,6},17},{{6,7},19},
    };
    vector<string> vertex = { "v0","v1","v2","v3","v4","v5","v6","v7","v8" };

    g.CreateGraph(vertex,edgeWeight);
    cout << "DFS:" << endl;
    g.DFSTraverse();
    cout << "BFS:" << endl;
    g.BFSTraverse();
    
}

result.png

图的创建和遍历

目录

图的定义

无向图

有向图

网

连通性

连通图

强连通图

图的存储结构

邻接矩阵

邻接表

其他结构

邻接表代码实现

图的遍历

深度优先（Depth First Search）

广度优先遍历

完整代码和测试

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

程序员