大师兄的数据结构学习笔记(九）: 图

大师兄的数据结构学习笔记(八）: 哈夫曼树与哈夫曼编码
 大师兄的数据结构学习笔记(十）: 伸展树

一、什么是图(Graph)

图表示多对多的关系。
线性结构和树都可以看成是图的特殊情况。

1. 关于顶点

图包含一组顶点。
通常用V(Vertex)表示顶点集合。

2. 关于边

图包含一组边。
通常用E(Edge)表示边的集合。
边表示的是顶点和顶点之间的某种关系:

1) 无向边

$(v,w) \in E,其中v,w \in V$ 。

如果可以从v到w, 也可以从w到v。

2) 有向边

$<v,w> \in E,其中v,w \in V$ 。

表示从v指向w的边(单行线)。

在图中，不考虑重边和自回路。

3. 抽象数据类型

类型名称：图（Graph）
数据额对象集：G(V,E)由一个非空的有限顶点集合V和一个有限边集合E组成。
常见操作集：对于任意图 $G\in Graph, 以及v \in V, e\in E$

操作集	说明
Graph Create()	建立并返回空图。
Graph InsertVertex(Graph G,Vertex v)	将v插入G。
Graph InsertEdge(Graph G,Edge e)	将e插入G。
void DFS(Graph G,Vertex v)	从顶点v出发深度优先遍历图G。
void BFS(Graph G,Vertex v)	从顶点v出发宽度优先遍历图G。
void ShortestPath(Graph G,Vertex v,int Dist[])	计算图G中顶点v到任意其他顶点的最短距离。
void MST(Graph G)	计算图G的最小生成树。

4. 常见术语

无向图(undirected edge): 图中所有的边都是无方向的。
有向图(directed edge): 图中的边可能是有向边或无向边，但方向是有意义的。
带权网络(weighted network): 图中的边是带权重的,用来表示顶点之间关系的细节。
邻接点(adjacent node): 有边直接相连的顶点。
度(degree): 在无向图中，与顶点v关联的边数，成为v的度数，记作deg(v)。
出度: 从该点出发的边数。
入度: 指向该点的边数。
简单图(simple graph): 不含任何自环(self-loop)的图。
通路(path): 由 $m+1$ 个顶点与 $m$ 条边交替而成的序列。
环路(cycle): 对于长度 $m\geq1的通路\pi,起止顶点相同(v_0=v_m)。$
稀疏图(sparse graph): 点很多而边很少。
完全图(complete graph): 任意两个顶点间，都有一条边。

二、在程序中表示图

1. 邻接矩阵(adjacency matrix)

是图最基本的实现方式。
使用方阵G[N][N]表示由N个顶点构成的图,其中每个单元各自负责描述一对顶点之间可能存在的邻接关系。
$若<V_i,V_j>是G中的边, G[i][j] = 1。$
$否则G[i][j] = 0。$

优点	缺点
1. 直观、简单、好理解。 2. 方便检查任意一对顶点间是否存在边。 3. 方便找任一顶点的所有邻接点。 4. 方便计算任一顶点的度。	1. 稀疏图浪费空间 - 存有大量无效元素(0)。 2. 稀疏图浪费时间 - 统计总边数需要遍历所有结点。

#ifndef NODE_H_
#define NODE_H_

class Node
{
public:
    Node(char data = 0); // 构造结点
    char m_cData; // 数据
    bool m_bIsVisted; // 是否被访问过
};
#endif // !NODE_H_

#include "node.h"

Node::Node(char data)
{
    m_cData = data;
    m_bIsVisted = false; //默认未访问
}

#ifndef GRAPH_H_
#define GRAPH_H_
#include <vector>
#include "node.h"
using namespace std;

class Graph
{
public:
    Graph(int capacity); //构造函数
    ~Graph();           //析构函数
    void resetNode(); //重置节点
    bool InsertVertex(Node* pNode); // 插入节点
    void DFS(int nodeIndex); //深度优先遍历
    void BFS(int nodeIndex); //宽度优先遍历
    void setValueToMatrixForDirectedGraph(int row, int col, int val = 1); //给有向图的邻接矩阵元素设置值
    void setValueToMatrixForUndirectedGraph(int row, int col, int val = 1);//给无向图的邻接矩阵的元素设置值
    void printMatrix(); //打印邻接矩阵
private:
    int m_iCapacity; // 节点容量
    int m_iNodeCount; //当前节点数量
    Node* m_pNodeArray; //指向第一个节点的指针
    int* m_pMatrix; // 指向邻接矩阵首元素的指针
    bool getValueFromMatrix(int row, int col, int& val); // 获取临街矩阵中元素的值
    void breadthFirstTraverseImpl(vector<int> preVec);
};

#endif // !GRAPH_H_

#include <iostream>
#include "graph.h"
using namespace std;

//构造函数
Graph::Graph(int capacity)
{
    m_iCapacity = capacity;
    m_iNodeCount = 0;
    m_pNodeArray = new Node[m_iCapacity];
    m_pMatrix = new int[m_iCapacity * m_iCapacity];
    memset(m_pMatrix, 0, m_iCapacity * m_iCapacity * sizeof(int)); // 初始化matrix
}

//析构函数
Graph::~Graph()
{
    delete[]m_pNodeArray; // 释放节点
    delete[]m_pMatrix;    //释放矩阵
}

//重置节点
void Graph::resetNode()
{
    for (int i = 0; i < m_iNodeCount; i++)
    {
        m_pNodeArray[i].m_bIsVisted = false;
    }
}

// 插入节点
bool Graph::InsertVertex(Node* pNode)
{
    if (pNode == nullptr) return false;
    m_pNodeArray[m_iNodeCount] = pNode->m_cData;
    m_iNodeCount++;
    return true;
}

// 获取临街矩阵中元素的值
bool Graph::getValueFromMatrix(int row, int col, int& val)
{
    if (row < 0 || row >= m_iCapacity)
    {
        return false;
    }

    if (col < 0 || col >= m_iCapacity)
    {
        return false;
    }
    val = m_pMatrix[row * m_iCapacity + col];
    return true;
}

void Graph::breadthFirstTraverseImpl(vector<int> preVec)
{
    int value = 0;
    vector<int> curVec;
    for (int j = 0; j < (int)preVec.size(); j++)
    {   
        for (int i = 0; i < m_iCapacity; i++) {
            getValueFromMatrix(preVec[j], i, value);
            if (value == 0) continue;
            if (m_pNodeArray[i].m_bIsVisted) continue;
            cout << m_pNodeArray[i].m_cData << " ";
            m_pNodeArray[i].m_bIsVisted = true;
            curVec.push_back(i);
        }
    }
}

//深度优先遍历
void Graph::DFS(int nodeIndex)
{
    int value = 0;
    cout << m_pNodeArray[nodeIndex].m_cData << " ";  // 打印值
    m_pNodeArray[nodeIndex].m_bIsVisted = true; // 修改状态

    for (int i = 0; i < m_iCapacity; i++)
    {
        getValueFromMatrix(nodeIndex, i, value);
        if (value == 0) continue;
        if (m_pNodeArray[i].m_bIsVisted) continue;
        DFS(i);
    }
}

//宽度优先遍历
void Graph::BFS(int nodeIndex)
{
    cout << m_pNodeArray[nodeIndex].m_cData << " ";
    m_pNodeArray[nodeIndex].m_bIsVisted = true;
    vector<int> curVec;
    curVec.push_back(nodeIndex);
    breadthFirstTraverseImpl(curVec);
}

//给有向图的邻接矩阵元素设置值
bool Graph::setValueToMatrixForDirectedGraph(int row, int col, int val)
{
    if (row < 0 || row >= m_iCapacity)
    {
        return false;
    }
    if (col < 0 || col >= m_iCapacity)
    {
        return false;
    }
    m_pMatrix[row * m_iCapacity + col] = val;
    return true;
}

//给无向图的邻接矩阵的元素设置值
bool Graph::setValueToMatrixForUndirectedGraph(int row, int col, int val)
{
    if (row < 0 || row >= m_iCapacity)
    {
        return false;
    }
    if (col < 0 || col >= m_iCapacity)
    {
        return false;
    }
    m_pMatrix[row * m_iCapacity + col] = val;
    m_pMatrix[col * m_iCapacity + row] = val;
    return true;
}

//打印邻接矩阵
void Graph::printMatrix()
{
    for (int i = 0; i < m_iCapacity; i++)
    {
        for (int k = 0; k < m_iCapacity; k++)
        {
            cout << m_pNodeArray[i*m_iCapacity+k].m_cData << " ";
        }
        cout << endl;
    }
}

2. 邻接表(adjacency list)

G[N]为指针数组，对应矩阵每行一个链表，只存非0元素。

优点	缺点
1. 方便找任一丁点的所有邻接点。 2. 节约稀疏图空间。 3. 方便计算无向图任一顶点的度。	1. 只能计算有向图的出度，计算入度需要构造逆邻接表。 2. 不方便检查任意一对顶点间是否存在边。

#ifndef QUEUE_H
#define QUEUE_H

const int queueSize = 100;

template<class T>
//表结构
class queue
{
public:
    T data[queueSize];
    int front, rear;
};

#endif

#ifndef GRAPH_H
#define GRAPH_H
#include "queue.h"

// 边表结点
struct ArcNode
{
    int adjvex; // 邻接点
    ArcNode* next; 
};


// 顶点表结点
struct VertexNode
{
    int vertex;
    ArcNode* firstedge;
};


const int MaxSize = 10;
int visited[MaxSize] = {0}; // 是否被访问

template<class T>
class Graph
{
public:
    Graph(T a[], int n, int e); //建立n个顶点,e条边的图
    ~Graph() {};                // 析构函数
    void DFS(int v);            // 深度优先搜索
    void BFS(int v);            // 广度优先搜索
private:
    VertexNode adjlist[MaxSize];// 图中的顶点
    int vertexNum;              // 图中的顶点数
    int arcNum;                 // 图中的边数
};

#endif

#include <iostream>
#include "graph.h"
using namespace std;

template<class T>
// 构造函数
Graph<T>::Graph(T a[], int n, int e)
{
    vertexNum = n;
    arcNum = e;
    // 初始化顶点
    for (int i = 0; i < vertexNum; i++)
    {
        adjlist[i].vertex = a[i];
        adjlist[i].firstedge = nullptr;
    }
    // 初始化边
    for (int i = 0; i < arcNum; i++)
    {
        int k, j;
        cin >> k >> j;
        ArcNode* s = new ArcNode;
        s->adjvex = j;
        s->next = adjlist[k].firstedge;
        adjlist[k].firstedge = s;
    }
}

template<class T>
// 深度优先
void Graph<T>::DFS(int v)
{
    cout << adjlist[v].vertex;
    visited[v] = 1;
    ArcNode* p = adjlist[v].firstedge;
    while (p != nullptr)
    {
        int j = p->adjvex;
        if (visited[j]==0)
        {
            DFS(j);
        }
        p = p ->next;
    }
}

template<class T>
// 广度优先
void Graph<T>::BFS(int v)
{
    int visited[MaxSize] = { 0 };
    queue<T> Q;
    Q.front = Q.rear = -1; // 初始化队列
    cout << adjlist[v].vertex;
    visited[v] = 1;
    Q.data[++Q.rear] = v;
    while (Q.front != Q.rear)
    {
        v = Q.data[++Q.front];
        ArcNode* p = adjlist[v].firstedge;
        while (p != nullptr)
        {
            int j = p->adjvex;
            if (visited[j] == 0)
            {
                cout << adjlist[j].vertex;
                visited[j] = 1;
                Q.data[++Q.rear] = j;
            }
            p = p->next;
        }
    }
}