大師兄的數(shù)據(jù)結構學習筆記(八）: 哈夫曼樹與哈夫曼編碼
大師兄的數(shù)據(jù)結構學習筆記(十）: 伸展樹

一、什么是圖(Graph)

• 圖表示多對多的關系。
• 線性結構和樹都可以看成是圖的特殊情況。

1. 關于頂點

• 圖包含一組頂點。
• 通常用V(Vertex)表示頂點集合。

2. 關于邊

• 圖包含一組邊。
• 通常用E(Edge)表示邊的集合。
• 邊表示的是頂點和頂點之間的某種關系:

1) 無向邊

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

2) 有向邊

• 。

• 表示從v指向w的邊(單行線)。

  
  

• 在圖中，不考慮重邊和自回路。

3. 抽象數(shù)據(jù)類型

• 類型名稱：圖（Graph）
• 數(shù)據(jù)額對象集：G(V,E)由一個非空的有限頂點集合V和一個有限邊集合E組成。
• 常見操作集：對于任意圖

4. 常見術語

• 無向圖(undirected edge): 圖中所有的邊都是無方向的。
• 有向圖(directed edge): 圖中的邊可能是有向邊或無向邊，但方向是有意義的。
• 帶權網(wǎng)絡(weighted network): 圖中的邊是帶權重的,用來表示頂點之間關系的細節(jié)。
• 鄰接點(adjacent node): 有邊直接相連的頂點。
• 度(degree): 在無向圖中，與頂點v關聯(lián)的邊數(shù)，成為v的度數(shù)，記作deg(v)。
• 出度: 從該點出發(fā)的邊數(shù)。
• 入度: 指向該點的邊數(shù)。
• 簡單圖(simple graph): 不含任何自環(huán)(self-loop)的圖。
• 通路(path): 由個頂點與條邊交替而成的序列。
• 環(huán)路(cycle): 對于長度
• 稀疏圖(sparse graph): 點很多而邊很少。
• 完全圖(complete graph): 任意兩個頂點間，都有一條邊。

二、在程序中表示圖

1. 鄰接矩陣(adjacency matrix)

• 是圖最基本的實現(xiàn)方式。
• 使用方陣G[N][N]表示由N個頂點構成的圖,其中每個單元各自負責描述一對頂點之間可能存在的鄰接關系。
• 
• 
  

#ifndef NODE_H_
#define NODE_H_

class Node
{
public:
    Node(char data = 0); // 構造結點
    char m_cData; // 數(shù)據(jù)
    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); //構造函數(shù)
    ~Graph();           //析構函數(shù)
    void resetNode(); //重置節(jié)點
    bool InsertVertex(Node* pNode); // 插入節(jié)點
    void DFS(int nodeIndex); //深度優(yōu)先遍歷
    void BFS(int nodeIndex); //寬度優(yōu)先遍歷
    void setValueToMatrixForDirectedGraph(int row, int col, int val = 1); //給有向圖的鄰接矩陣元素設置值
    void setValueToMatrixForUndirectedGraph(int row, int col, int val = 1);//給無向圖的鄰接矩陣的元素設置值
    void printMatrix(); //打印鄰接矩陣
private:
    int m_iCapacity; // 節(jié)點容量
    int m_iNodeCount; //當前節(jié)點數(shù)量
    Node* m_pNodeArray; //指向第一個節(jié)點的指針
    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;

//構造函數(shù)
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
}

//析構函數(shù)
Graph::~Graph()
{
    delete[]m_pNodeArray; // 釋放節(jié)點
    delete[]m_pMatrix;    //釋放矩陣
}

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

// 插入節(jié)點
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);
        }
    }
}

//深度優(yōu)先遍歷
void Graph::DFS(int nodeIndex)
{
    int value = 0;
    cout << m_pNodeArray[nodeIndex].m_cData << " ";  // 打印值
    m_pNodeArray[nodeIndex].m_bIsVisted = true; // 修改狀態(tài)

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

//寬度優(yōu)先遍歷
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]為指針數(shù)組，對應矩陣每行一個鏈表，只存非0元素。

#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() {};                // 析構函數(shù)
    void DFS(int v);            // 深度優(yōu)先搜索
    void BFS(int v);            // 廣度優(yōu)先搜索
private:
    VertexNode adjlist[MaxSize];// 圖中的頂點
    int vertexNum;              // 圖中的頂點數(shù)
    int arcNum;                 // 圖中的邊數(shù)
};

#endif

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

template<class T>
// 構造函數(shù)
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>
// 深度優(yōu)先
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>
// 廣度優(yōu)先
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;
        }
    }
}