大师兄的数据结构学习笔记(八）: 哈夫曼树与哈夫曼编码
大师兄的数据结构学习笔记(十）: 伸展树
一、什么是图(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;
}
}
}
网友评论