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

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

一、什么是图(Graph)

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

1. 关于顶点

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

2. 关于边

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

1) 无向边

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

2) 有向边

• 。

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

  
  

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

3. 抽象数据类型

• 类型名称：图（Graph）
• 数据额对象集：G(V,E)由一个非空的有限顶点集合V和一个有限边集合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): 由个顶点与条边交替而成的序列。
• 环路(cycle): 对于长度
• 稀疏图(sparse graph): 点很多而边很少。
• 完全图(complete graph): 任意两个顶点间，都有一条边。

二、在程序中表示图

1. 邻接矩阵(adjacency matrix)

• 是图最基本的实现方式。
• 使用方阵G[N][N]表示由N个顶点构成的图,其中每个单元各自负责描述一对顶点之间可能存在的邻接关系。
• 
• 
  

优点	缺点
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;
        }
    }
}