圖的定義

數(shù)據(jù)結(jié)構(gòu)中，圖由頂點(diǎn)和邊構(gòu)成如下：

圖1

上圖中數(shù)字代表頂點(diǎn)（Vertex）,連接頂點(diǎn)的是邊（Edge），通過邊表示頂點(diǎn)之間的邏輯關(guān)系。

無向圖

定義：若表示頂點(diǎn)關(guān)系的邊沒有方向（無向邊），則此圖為無向圖，如圖1。頂點(diǎn)Vi到Vj之間的邊表示為(Vi,Vj)，代表Vi，Vj鄰接。
頂點(diǎn)的度：

與某個(gè)頂點(diǎn)有關(guān)的邊的數(shù)量，代表此頂點(diǎn)的度。如圖1，頂點(diǎn)1的度為2。
完全無向圖

無向圖中，如果每個(gè)頂點(diǎn)都存在到其他頂點(diǎn)的邊，則此圖為完全無向圖：

UnGraph.png

? 完全無向圖有n(n-1)/2條邊，n為頂點(diǎn)數(shù)。

有向圖

定義

當(dāng)頂點(diǎn)之間的邊有方向時(shí)，圖為有向圖。如下：

directed.png

? 并使用有序?qū)?lt;Vi，Vj>來表示頂點(diǎn)Vi，Vj之間的邊，稱為弧。Vi稱為弧尾，Vj為弧頭。例如，上圖頂點(diǎn)A、D之間的邊表示為：<A,D>表明方向A->D

出度、入度

以頂點(diǎn)Vi為弧尾的弧數(shù)量，表示Vi的出度，以頂點(diǎn)Vi為弧頭的數(shù)量，表示Vi的入度。
完全有向圖

任意頂點(diǎn)存在互為相反方向的邊，稱為完全有向圖

網(wǎng)

圖中的邊或弧，存在對應(yīng)的數(shù)字，這樣的圖稱為網(wǎng)，邊或弧對應(yīng)的數(shù)字稱為權(quán)。

network.png

上圖的權(quán)值表示距離。

連通性

連通圖

在無向圖G中，存在從Vi到Vj的路徑，則稱Vi和Vj是連通的。如果G中任意兩個(gè)頂點(diǎn)都是連通的，則稱G為連通圖。

connected.png

無向圖中的極大連通子圖稱為連通分量，連通分量條件：

子圖
子圖要是連通的
連通子圖含有極大頂點(diǎn)數(shù)

強(qiáng)連通圖

在有向圖G中，對于任意Vi,Vj,存在Vi->Vj 和Vj->Vi的路徑，則稱G是強(qiáng)連通圖。

有向圖的極大強(qiáng)連通子圖稱為強(qiáng)連通分量

圖的存儲(chǔ)結(jié)構(gòu)

鄰接矩陣

使用兩個(gè)數(shù)組來表示圖。

一個(gè)一維數(shù)組Vertex表示頂點(diǎn)
一個(gè)二維數(shù)組edge表示邊。

edge[i][j]= W       //表示權(quán)值
            0       //i=j
            Infinty // 表示邊(i,j)不存在

Adjcency Matrix.png

鄰接表

鄰接表與鄰接矩陣相比，使用鏈表代替二維數(shù)組。對于邊數(shù)比頂點(diǎn)數(shù)少的情況，鄰接矩陣存在著巨大的浪費(fèi)，而使用鏈?zhǔn)浇Y(jié)構(gòu)可以很好的避免浪費(fèi)。

使用一個(gè)一維數(shù)組表示頂點(diǎn)
使用單鏈表來表示每個(gè)頂點(diǎn)的鄰接頂點(diǎn)

Adjcency List.png

其他結(jié)構(gòu)

十字鏈表、多重鄰接表

十字鏈表作用于有向圖、多重鄰接表作用于無向圖，都是鄰接表的進(jìn)階版本，不做詳細(xì)介紹

鄰接表代碼實(shí)現(xiàn)

邊節(jié)點(diǎn)結(jié)構(gòu)：

typedef struct EdgeNode{                            //邊節(jié)點(diǎn)
        int adjVertex;
        Tweight weight;                             //權(quán)重
        EdgeNode* next;
}EdgeNode;

頂點(diǎn)節(jié)點(diǎn)結(jié)構(gòu)：

typedef struct VertexNode {                     //頂點(diǎn)節(jié)點(diǎn)
        Tvertex vertex;                             //頂點(diǎn)值
        EdgeNode* firstEdge;                        //指向的邊
}VertexNode;

類聲明：

template<typename Tvertex, typename Tweight>
class UndirectedGraph                               //鄰接表實(shí)現(xiàn)無向圖
{
private:
    typedef struct EdgeNode{                        //邊節(jié)點(diǎn)
        int adjVertex;
        Tweight weight;                             //權(quán)重
        EdgeNode* next;
    }EdgeNode;

    typedef struct VertexNode {                     //頂點(diǎn)節(jié)點(diǎn)
        Tvertex vertex;                             //頂點(diǎn)值
        EdgeNode* firstEdge;                        //指向的邊
    }VertexNode;

    std::vector<VertexNode> graph;                  //保存頂點(diǎn)的數(shù)組
    int verxNums;                                   //頂點(diǎn)數(shù)量
    int edgeNums;                                   //邊數(shù)量
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[]);
    
};

圖創(chuàng)建函數(shù)：

template<typename Tvertex, typename Tweight>
void UndirectedGraph<Tvertex, Tweight>::CreateGraph() {
     //初始化頂點(diǎn)數(shù)組
    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);
    }
    
    //為頂點(diǎn)添加相關(guān)的邊信息
    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;               //插入邊節(jié)點(diǎn)
        graph[i].firstEdge = e;

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

為方便測試，編寫了一個(gè)靜態(tài)生成圖的函數(shù),內(nèi)容基本一樣，該函數(shù)從一個(gè)節(jié)點(diǎn)數(shù)組std::vector<Tvertex> vertex讀入節(jié)點(diǎn)信息，一個(gè)pair結(jié)構(gòu)數(shù)組std::pair<std::vector<int>, Tweight> edgeWeight[]表示邊和權(quán)值：

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;
    }

    //顯示相關(guān)信息
    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;
    }
}

圖的遍歷

深度優(yōu)先（Depth First Search）

與樹的中根遍歷模式一樣類似

DFS.png

如上圖是按照搜索右邊的節(jié)點(diǎn)規(guī)則，進(jìn)行深度優(yōu)先遍歷，從A開始不斷深入搜索A->B->C->D->E->F->G->H,搜索完H發(fā)現(xiàn)沒有未遍歷的鄰接點(diǎn)，開始回退，退回到D，然后訪問I，完成所有節(jié)點(diǎn)的遍歷。

深度優(yōu)先遍歷實(shí)現(xiàn)：

與二叉樹的遍歷一樣使用遞歸
使用一個(gè)長度為頂點(diǎn)數(shù)的數(shù)組來標(biāo)記頂點(diǎn)是否被訪問

代碼實(shí)現(xiàn)：

//聲明
template<typename Tvertex, typename Tweight>
class UndirectedGraph                               //鄰接表實(shí)現(xiàn)無向圖
{
private:
    ...
    void DFS(std::vector<bool>& isVisted, int i);   //深度優(yōu)先遍歷遞歸調(diào)用函數(shù)，外部無需訪問該方法申明為私有
    
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);                            //對鏈表元素繼續(xù)DFS
        }
    }
    
}

template<typename Tvertex, typename Tweight>
void UndirectedGraph<Tvertex, Tweight>::DFSTraverse() {
    std::vector<bool> isVisted(verxNums,false);             //訪問標(biāo)識(shí)數(shù)組，初始化為false

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

廣度優(yōu)先遍歷

與樹的層次遍歷相似，一層一層往下遍歷，對每一層做最大范圍遍歷。并且與樹的層次遍歷實(shí)現(xiàn)相同，使用隊(duì)列保存未遍歷元素

BFS.png

代碼實(shí)現(xiàn)：

//聲明
template<typename Tvertex, typename Tweight>
class UndirectedGraph                               //鄰接表實(shí)現(xiàn)無向圖
{
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();                      //去隊(duì)頭元素
            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>


/********************************************
* 時(shí)間：2021/1/2
* 作者：tanghf
* 類簡介：使用鄰接表實(shí)現(xiàn)無向圖
********************************************/
template<typename Tvertex, typename Tweight>
class UndirectedGraph                               //鄰接表實(shí)現(xiàn)無向圖
{
private:
    typedef struct EdgeNode{                        //邊節(jié)點(diǎn)
        int adjVertex;
        Tweight weight;                             //權(quán)重
        EdgeNode* next;
    }EdgeNode;

    typedef struct VertexNode {                     //頂點(diǎn)節(jié)點(diǎn)
        Tvertex vertex;                             //頂點(diǎn)值
        EdgeNode* firstEdge;                        //指向的邊
    }VertexNode;

    std::vector<VertexNode> graph;
    int verxNums;                                   //頂點(diǎn)數(shù)量
    int edgeNums;                                   //邊數(shù)量

    void DFS(std::vector<bool>& isVisted, int i);   //深度優(yōu)先遍歷遞歸調(diào)用函數(shù)
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[]); //靜態(tài)創(chuàng)建無向圖
    void CreateGraph();                                     //動(dòng)態(tài)輸入創(chuàng)建無向圖
    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() {
    //初始化頂點(diǎn)數(shù)組
    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);
    }

    //為頂點(diǎn)添加相關(guān)的邊信息
    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;               //插入邊節(jié)點(diǎn)
        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; 
}

對如下圖進(jìn)行測試：

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

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

圖的創(chuàng)建和遍歷

圖的創(chuàng)建和遍歷

目錄

圖的定義

無向圖

有向圖

網(wǎng)

連通性

連通圖

強(qiáng)連通圖

圖的存儲(chǔ)結(jié)構(gòu)

鄰接矩陣

鄰接表

其他結(jié)構(gòu)

鄰接表代碼實(shí)現(xiàn)

圖的遍歷

深度優(yōu)先（Depth First Search）

廣度優(yōu)先遍歷

完整代碼和測試

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

圖的創(chuàng)建和遍歷

目錄

圖的定義

無向圖

有向圖

網(wǎng)

連通性

連通圖

強(qiáng)連通圖

圖的存儲(chǔ)結(jié)構(gòu)

鄰接矩陣

鄰接表

其他結(jié)構(gòu)

鄰接表代碼實(shí)現(xiàn)

圖的遍歷

深度優(yōu)先（Depth First Search）

廣度優(yōu)先遍歷

完整代碼和測試

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av