返回分类：全部文章 >> 基础知识
本文将介绍图的基础知识，并用C++实现它。
它包含两部分：
编程基础 - 图 I (Graph I) ：存储结构
编程基础 - 图 II (Graph II) ：实现完整的邻接矩阵并遍历（本文）
在查看本文之前，需要一些数据结构和程序语言的基础。
尤其是“二维数组”、“矩阵”、“矩阵的压缩(matrix)”。一些遍历和应用的内容还需要“栈(stack)”，“队列(queue)”，“二叉树(binary tree)”等的知识。
前接 编程基础 - 图 I (Graph I)
我们有了邻接矩阵的结构，但在四个结构中，只有它的顶点没有使用结构。我们为了保持一致，也为它建立一个结构。
template<typename T> class AMVertexNode { public: T element; AMVertexNode(const T& e) { element = e; } };然后这四种结构，虽然结构不同，但方法的作用全部都是一样的，所以建立一个抽象类（Abstract Class）是一个非常棒的想法。即
// 图接口 template<typename TValue, template<typename TValue> class TVertex> class IGraph { public: static constexpr double INFINITE_WEIGHT = std::numeric_limits<double>::max(); // 权值无穷符号 protected: // Fields bool m_Oriented; // 有向图标识 double m_DefaultWeight; // 不连通的权重，即0或无穷 std::vector<TVertex<TValue>*> m_Vertexes; // 顶点列表 protected: // Constructors IGraph(bool oriented); // 构造函数 virtual ~IGraph(); // 析构函数 protected: // Properties virtual TVertex<TValue>* GetVertexNode(int index); // 获取顶点 virtual bool PutVertexNode(int index, TVertex<TValue>* vertex); // 设置顶点 virtual bool InsertVertexNode(TVertex<TValue>* vertex); // 插入顶点 virtual bool InsertVertexNode(int index, TVertex<TValue>* vertex); // 插入顶点 public: // Properties bool IsOriented(); // 是否是有向图 double GetDefaultWeight(); // 获取不连通的权重 void PutDefaultWeight(double defaultWeight); // 设置不连通的权重 virtual void ResetDefaultWeight(); // 重置不连通的权重 bool IsEmpty(); // 是否空 virtual int GetVertexCount(); // 获取顶点数量 // 省略，其它相同属性 public: // Methods // 省略，其它相同方法 } 其中的基本属性操作就不再阐述。在邻接矩阵中，我们继承它：
// 邻接矩阵 template<typename T> class AdjacencyMatrix : virtual public IGraph<T, AMVertexNode> { protected: std::vector<std::vector<double>> m_Weights; // 边的关系，邻接矩阵 // 省略内容 }初始化包含初始化顶点，和初始化边。
在初始化顶点时，就已经确定了边的长度，即邻接矩阵的长宽都是顶点的数量。
初始化顶点：
// Author: https://blog.csdn.net/DarkRabbit // Graph -> Adjacency Matrix // 初始化顶点 // params: // vertexElements: 顶点的值 // return: // bool: 是否初始化成功 template<typename T> bool AdjacencyMatrix<T>::InitializeVertexes(const std::vector<T>& vertexElements) { if (!this->IsEmpty()) { this->DestroyAllVertexNodes(); } int size = vertexElements.size(); this->m_Vertexes = std::vector<AMVertexNode<T>*>(size, 0); for (int i = 0; i < size; i++) { AMVertexNode<T>* vertex = new AMVertexNode<T>(vertexElements[i]); this->PutVertexNode(i, vertex); } // 初始化边长宽，并全部赋值成 0或无穷 m_Weights = std::vector<std::vector<double>>(size, std::vector<double>(size, this->GetDefaultWeight())); return true; }而在初始化边时，我们要确保路径和权值的长度是相等的，即每两个顶点的路径都有权值。
初始化边：
// Author: https://blog.csdn.net/DarkRabbit // Graph -> Adjacency Matrix // 初始化边 // params: // paths: 起始到结束的路径 // weights: 权重 // return: // bool: 是否初始化成功 template<typename T> bool AdjacencyMatrix<T>::InitializeWeights(const std::vector<std::pair<int, int>> paths, const std::vector<double>& weights) { if (paths.size() != weights.size()) { return false; } bool oriented = this->IsOriented(); // 是否有向图 for (int i = 0; i < paths.size(); i++) { this->TryPutWeight(paths[i].first, paths[i].second, weights[i]); if (!oriented) { this->TryPutWeight(paths[i].second, paths[i].first, weights[i]); } } return true; } // 用同一个权重初始化边 // params: // paths: 起始到结束的路径 // return: // bool: 是否初始化成功 template<typename T> bool AdjacencyMatrix<T>::InitializeUndirectedWeights(const std::vector<std::pair<int, int>> paths, double weight) { bool oriented = this->IsOriented(); for (int i = 0; i < paths.size(); i++) { this->TryPutWeight(paths[i].first, paths[i].second, weight); if (!oriented) { this->TryPutWeight(paths[i].second, paths[i].first, weight); } } return true; }我们只需要遍历邻接矩阵对应的行，取其中不为0或无穷的顶点。
其代码为：
// Author: https://blog.csdn.net/DarkRabbit // Graph -> Adjacency Matrix // 查找第一条边连接的顶点 // params: // index; 顶点下标 // return: // int: 找到的邻接顶点下标，没有找到返回-1 template<typename T> int AdjacencyMatrix<T>::FirstNeighbor(int index) { int size = this->GetVertexCount(); if (index < 0 || index >= size) { return -1; } int find = -1; for (int i = 0; i < size; i++) { if (m_Weights[index][i] != this->GetDefaultWeight()) { find = i; break; } } return find; }我们同样搜索行，只是起点不是0，而是邻接顶点的下标，来搜索它之后的下标。
其代码为：
// Author: https://blog.csdn.net/DarkRabbit // Graph -> Adjacency Matrix // 查找下一条边连接的顶点 // params: // index; 顶点下标 // neighborIndex: 邻接顶点下标 // return: // int: 找到的邻接的邻接顶点下标，没有找到返回-1 template<typename T> int AdjacencyMatrix<T>::NextNeighbor(int index, int neighborIndex) { int size = this->GetVertexCount(); if (index < 0 || index >= size || neighborIndex < 0 || neighborIndex >= size) { return -1; } int find = -1; for (int i = neighborIndex + 1; i < size; i++) { if (m_Weights[index][i] != this->GetDefaultWeight()) { find = i; break; } } return find; }图的遍历，主要是指在连通图中的遍历，从一顶点出发，沿着路径访问图中所有的顶点，且每个顶点只被访问一次。
由于图中可能会有回路，所以在回到访问过的顶点时，需要加以判断，这就需要我们为每个顶点添加一个标识变量。
图的遍历的分类：
深度优先（Depth First Search，DFS）
广度优先（Breadth First Search， BFS）
深度优先搜索基本思路：
（1）由某一起始点出发，沿某一条路径访问第一个邻接顶点；
（2）再从此邻接顶点出发，访问没有访问过的此顶点的邻接顶点；
（3）如果周围邻接顶点都访问过或没有顶点，则退回一步查找周围邻接顶点；
（4）循环过程，直到全部顶点访问。
深度优先遍历 类似于二叉树的先序遍历 ，非递归算法通常使用栈 。
其C++代码为：
// Author: https://blog.csdn.net/DarkRabbit // Abstract Graph // 深度优先遍历，内部递归 // params: // index: 当前访问顶点 // isVisited: 访问标识 // pVisit: 访问方法 template<typename TValue, template<typename TValue> class TVertex> void IGraph<TValue, TVertex>::DepthFirstSearchRecursion(int index, std::vector<bool>& isVisited, void(*pVisit)(TVertex<TValue>&)) { TVertex<TValue>* vertex = this->GetVertexNode(index); // 取顶点 (*pVisit)(*vertex); // 访问顶点 isVisited[index] = true; // 设置标记，访问过了 // 从第一个邻接顶点开始搜索邻接 for (int neighbor = this->FirstNeighbor(index); neighbor != -1; neighbor = this->NextNeighbor(index, neighbor)) { if (!isVisited[neighbor]) { this->DepthFirstSearchRecursion(neighbor, isVisited, pVisit); } } } // 深度优先遍历 // params: // pVisit: 访问方法 template<typename TValue, template<typename TValue> class TVertex> void IGraph<TValue, TVertex>::DepthFirstSearch(void(*pVisit)(TVertex<TValue>&)) { if (this->IsEmpty() || 0 == pVisit) { return; } int size = this->GetVertexCount(); std::vector<bool> isVisited = std::vector<bool>(size, false); // 访问标记 this->DepthFirstSearchRecursion(0, isVisited, pVisit); }广度优先搜索基本思路：
（1）由某一起始点出发，访问所有邻接顶点；
（2）再从其中一个邻接顶点出发，访问其所有邻接结点；
（3）循环过程，直到全部顶点访问。
广度优先遍历 类似于二叉树的层序遍历 ，非递归算法通常使用队列 。
其C++代码为：
// 广度优先遍历 // params: // pVisit: 访问方法 template<typename TValue, template<typename TValue> class TVertex> void IGraph<TValue, TVertex>::BreadthFirstSearch(void(*pVisit)(TVertex<TValue>&)) { if (this->IsEmpty() || 0 == pVisit) { return; } int size = this->GetVertexCount(); std::vector<bool> isVisited = std::vector<bool>(size, false); // 访问标记 (*pVisit)(*(this->GetVertexNode(0))); // 访问第一个顶点 isVisited[0] = true; // 第一个顶点访问过了 std::queue<int> vertexQueue; // 定义队列，储存访问过的顶点 vertexQueue.push(0); // 加入第一个顶点 int index; // 要访问谁的邻接 while (!vertexQueue.empty()) { index = vertexQueue.front(); vertexQueue.pop(); // 从第一个邻接顶点开始访问邻接 for (int neighbor = this->FirstNeighbor(index); neighbor != -1; neighbor = this->NextNeighbor(index, neighbor)) { if (!isVisited[neighbor]) { (*pVisit)(*(this->GetVertexNode(neighbor))); // 访问邻接顶点 isVisited[neighbor] = true; // 访问过了 vertexQueue.push(neighbor); // 入队 } } } }当无向图是非连通图时，从图中任意一点触发，利用遍历算法不可能遍历到所有的点，只能访问到该顶点所在子图的所有顶点，此子图为最大连通子图，也称连通分量。
求连通分量：
对图中每一个顶点进行遍历； 若顶点访问过，则此顶点所在子图已经求过连通分量，继续下一个顶点；若未被访问过，则通过遍历求连通分量。对非连通的无向图，所有连通分量的生成树，能组成非连通图的生成森林。
对于有向图，从不同的顶点出发，通过遍历可以得到不同的生成树。
主要测试遍历，采用邻接矩阵来计算。
其它存储格式同理。
实例，如果有补充将会在这里更新链接。
最小生成树 (Minimum Spanning Tree) ：主要应用在交通规划，电力系统规划，通信领域等需要铺设网络的方向。
克鲁斯卡尔算法 (Kruskal)普利姆算法 (Prim)最短路径 (Shortest Path) ：这个不用说了，非常常用；
迪杰斯特拉算法 (Dijkstra)弗洛伊德算法 (Floyed)A星算法 (A Star)贝尔曼-福特算法的队列优化形式 (Bellman-Ford using queue optimization)活动网络 (Activity Network)
AOV网络 (Activity On Vertex network)，拓扑排序 (Topological-Sort) 常用来表示各种优先级关系；AOE网络 (Activity On Edge Network)，关键路径 (Critical Path) 常用来描述和分析一项工程的计划和实施过程。