# include <iostream> # include <vector> # include <queue> # include <limits> using namespace std; class GraphMatrix {
private : int numVertices; vector< vector< int >> adjMatrix; const static int INFINITY = numeric_limits < int > :: max ( ) ; public : GraphMatrix ( int vertices) : numVertices ( vertices) , adjMatrix ( vertices, vector < int > ( vertices, INFINITY) ) { } void addEdge ( int u, int v, int weight) { if ( u >= 0 && u < numVertices && v >= 0 && v < numVertices) { adjMatrix[ u] [ v] = weight; adjMatrix[ v] [ u] = weight; } } void BFS ( int startVertex) ; void DFSUtil ( int vertex, vector< bool > & visited) ; void DFS ( ) ;
} ; void GraphMatrix :: BFS ( int startVertex) { vector< bool > visited ( numVertices, false ) ; queue< int > q; visited[ startVertex] = true ; q. push ( startVertex) ; while ( ! q. empty ( ) ) { int current = q. front ( ) ; cout << "Visited " << current << endl; q. pop ( ) ; for ( int i = 0 ; i < numVertices; ++ i) { if ( adjMatrix[ current] [ i] != INFINITY && ! visited[ i] ) { visited[ i] = true ; q. push ( i) ; } } }
} void GraphMatrix :: DFSUtil ( int vertex, vector< bool > & visited) { visited[ vertex] = true ; cout << "Visited " << vertex << endl; for ( int i = 0 ; i < numVertices; ++ i) { if ( adjMatrix[ vertex] [ i] != INFINITY && ! visited[ i] ) DFSUtil ( i, visited) ; }
} void GraphMatrix :: DFS ( ) { vector< bool > visited ( numVertices, false ) ; for ( int i = 0 ; i < numVertices; ++ i) if ( ! visited[ i] ) DFSUtil ( i, visited) ;
}
# include <iostream> # include <vector> # include <list> # include <queue> using namespace std; class GraphList {
private : int numVertices; vector< list< pair< int , int >> > adjLists; public : GraphList ( int vertices) : numVertices ( vertices) , adjLists ( vertices) { } void addEdge ( int u, int v, int weight) { adjLists[ u] . push_back ( make_pair ( v, weight) ) ; adjLists[ v] . push_back ( make_pair ( u, weight) ) ; } void BFS ( int startVertex) ; void DFSUtil ( int vertex, vector< bool > & visited) ; void DFS ( ) ;
} ; void GraphList :: BFS ( int startVertex) { vector< bool > visited ( numVertices, false ) ; queue< int > q; visited[ startVertex] = true ; q. push ( startVertex) ; while ( ! q. empty ( ) ) { int current = q. front ( ) ; cout << "Visited " << current << endl; q. pop ( ) ; for ( auto & edge : adjLists[ current] ) { int neighbor = edge. first; if ( ! visited[ neighbor] ) { visited[ neighbor] = true ; q. push ( neighbor) ; } } }
} void GraphList :: DFSUtil ( int vertex, vector< bool > & visited) { visited[ vertex] = true ; cout << "Visited " << vertex << endl; for ( auto & edge : adjLists[ vertex] ) { int neighbor = edge. first; if ( ! visited[ neighbor] ) DFSUtil ( neighbor, visited) ; }
} void GraphList :: DFS ( ) { vector< bool > visited ( numVertices, false ) ; for ( int i = 0 ; i < numVertices; ++ i) if ( ! visited[ i] ) DFSUtil ( i, visited) ;
}
核心原理 以深度优先为策略，从起始顶点出发，沿着一条路径持续深入探索，直至无法继续或达成特定条件（如找到目标顶点）。随后回溯到前一步，继续探寻其他未访问路径，直至遍历完起始顶点所在连通分量的所有顶点。若图中存在未访问顶点，则选取其一作为新起始点，重复上述流程，直至整个图的所有顶点均被访问。 实现方式 递归实现 ：在递归函数中，首先标记当前顶点已访问，接着遍历其邻接顶点，对未访问的邻接顶点递归调用 DFS 函数。以下是使用邻接表存储图的递归 DFS 代码：class GraphDFS {
private : vector< bool > visited; void DFSUtil ( Graph& graph, int v) { visited[ v] = true ; cout << v << " " ; for ( const Edge& edge : graph. adjList[ v] ) { int neighbor = edge. to; if ( ! visited[ neighbor] ) { DFSUtil ( graph, neighbor) ; } } } public : void DFS ( Graph& graph) { visited. resize ( graph. numVertices, false ) ; for ( int i = 0 ; i < graph. numVertices; ++ i) { if ( ! visited[ i] ) { DFSUtil ( graph, i) ; } } }
} ;
应用场景 图的连通性检测 ：执行一次 DFS 遍历，若所有顶点均能被访问到，则图是连通的；反之则不连通。连通分量求解 ：多次调用 DFS，每次从一个未访问顶点启动，可获取图的各个连通分量。迷宫探索 ：将迷宫建模为图，迷宫中的格子作为顶点，相邻格子间的通道作为边，DFS 可用于找寻从迷宫入口到出口的路径。核心原理 从给定起始顶点开始，先访问该顶点，接着依次访问其所有未访问的邻接顶点，然后再访问这些邻接顶点的未访问邻接顶点，依此类推，按照层次顺序逐层向外拓展，直至遍历完图中的所有顶点。 实现方式 借助队列 实现。首先将起始顶点入队并标记为已访问，然后循环取出队首顶点，访问其未访问邻接顶点并将这些邻接顶点入队，直至队列为空。以下是使用邻接表 存储图的 BFS 示例代码： class GraphBFS {
public : void BFS ( Graph& graph, int start) { vector< bool > visited ( graph. numVertices, false ) ; queue< int > q; visited[ start] = true ; q. push ( start) ; while ( ! q. empty ( ) ) { int current = q. front ( ) ; q. pop ( ) ; cout << current << " " ; for ( const Edge& edge : graph. adjList[ current] ) { int neighbor = edge. to; if ( ! visited[ neighbor] ) { visited[ neighbor] = true ; q. push ( neighbor) ; } } } }
} ;
应用场景 无权图最短路径计算 ：在 BFS 遍历过程中，从起始顶点到其他顶点的路径长度即为它们在队列中被访问的层数，可用于求解无权图中两点间的最短路径长度及路径。网络爬虫页面遍历 ：网络爬虫从起始页面出发，按照广度优先顺序遍历链接页面，能够优先抓取与起始页面距离较近的页面，确保信息获取的全面性和层次性。核心原理 从图中任选一个顶点作为起始点，构建初始的最小生成树集合。随后不断从剩余顶点中挑选与当前最小生成树集合相连且权值最小的边所对应的顶点，将其纳入最小生成树集合，持续该过程直至所有顶点均被加入。 实现细节 维护两个顶点集合，已在最小生成树中的顶点集合U和未在其中的顶点集合V - U。使用数组key记录每个顶点到当前最小生成树的最小权值边的权值，初始除起始顶点外均设为无穷大，同时用数组parent记录每个顶点在最小生成树中的父顶点。以下是使用邻接表存储图的 Prim 算法代码： class PrimMST {
public : int prim ( Graph& graph, int start) { vector< bool > inMST ( graph. numVertices, false ) ; vector< int > key ( graph. numVertices, INT_MAX) ; vector< int > parent ( graph. numVertices, - 1 ) ; key[ start] = 0 ; for ( int count = 0 ; count < graph. numVertices - 1 ; ++ count) { int minKey = INT_MAX, minIndex = - 1 ; for ( int v = 0 ; v < graph. numVertices; ++ v) { if ( ! inMST[ v] && key[ v] < minKey) { minKey = key[ v] ; minIndex = v; } } inMST[ minIndex] = true ; for ( const Edge& edge : graph. adjList[ minIndex] ) { int neighbor = edge. to; int weight = 1 ; if ( ! inMST[ neighbor] && weight < key[ neighbor] ) { key[ neighbor] = weight; parent[ neighbor] = minIndex; } } } int sumWeight = 0 ; for ( int i = 1 ; i < graph. numVertices; ++ i) { sumWeight += key[ i] ; } return sumWeight; }
} ;
时间复杂度分析 若采用邻接矩阵存储图，时间复杂度为(O(n^2))，其中(n)为顶点数。若运用堆优化，时间复杂度可降至(O((n + m)log n))，其中(m)为边数。 核心原理 首先将图中所有边按照权值从小到大排序，然后依次考察每条边。若选取某条边不会与已选边构成回路，则将其纳入最小生成树，直至选取了(n - 1)条边（(n)为顶点数）。 实现细节 需要借助并查集数据结构判断边加入后是否形成回路。并查集用于维护顶点的连通性信息，初始每个顶点各自属于独立集合，加入边时判断边的两个顶点是否在同一集合，若不在则合并两个集合。 # include <iostream> # include <vector> # include <algorithm> using namespace std;
struct Edge { int src, dest, weight;
} ;
bool compare ( const Edge& a, const Edge& b) { return a. weight < b. weight;
}
class UnionFind {
private : vector< int > parent, rank; public : UnionFind ( int size) : parent ( size) , rank ( size, 0 ) { for ( int i = 0 ; i < size; ++ i) parent[ i] = i; } int find ( int x) { if ( parent[ x] != x) parent[ x] = find ( parent[ x] ) ; return parent[ x] ; } void unionSets ( int x, int y) { int rootX = find ( x) ; int rootY = find ( y) ; if ( rootX != rootY) { if ( rank[ rootX] > rank[ rootY] ) parent[ rootY] = rootX; else if ( rank[ rootX] < rank[ rootY] ) parent[ rootX] = rootY; else { parent[ rootY] = rootX; rank[ rootX] ++ ; } } }
} ;
void kruskalMST ( vector< Edge> & edges, int V) { sort ( edges. begin ( ) , edges. end ( ) , compare) ; UnionFind uf ( V) ; vector< Edge> mst; for ( auto & edge : edges) { int rootSrc = uf. find ( edge. src) ; int rootDest = uf. find ( edge. dest) ; if ( rootSrc != rootDest) { mst. push_back ( edge) ; uf. unionSets ( rootSrc, rootDest) ; } } cout << "Edges in the MST:" << endl; for ( auto & e : mst) cout << e. src << " -- " << e. dest << " == " << e. weight << endl;
} int main ( ) { int V = 4 ; vector< Edge> edges = { { 0 , 1 , 10 } , { 0 , 2 , 6 } , { 0 , 3 , 5 } , { 1 , 3 , 15 } , { 2 , 3 , 4 } } ; kruskalMST ( edges, V) ; return 0 ;
}
时间复杂度分析 时间复杂度主要取决于边的排序操作，通常为(O(mlog m))，其中(m)为边数。在稀疏图中，由于边数相对较少，克鲁斯卡尔算法往往比普里姆算法更具效率。 核心原理 适用于带权有向图（权值非负）。从源点出发，逐步确定到其他顶点的最短路径。维护一个已确定最短路径的顶点集合S，对于不在S中的顶点v，记录从源点到v的当前最短路径长度d[v]。每次从不在S中的顶点里选取d[v]最小的顶点u加入S，并更新与u相邻顶点的d[v]值。 实现细节 初始化时，源点的d值设为(0)，其余顶点设为无穷大。然后持续重复选取最小d值顶点并更新相邻顶点d值的操作，直至所有顶点均被加入S。以下是使用邻接表存储图的 Dijkstra 算法代码： class DijkstraSP {
public : vector< int > dijkstra ( Graph& graph, int source) { vector< int > dist ( graph. numVertices, INT_MAX) ; vector< bool > visited ( graph. numVertices, false ) ; dist[ source] = 0 ; for ( int count = 0 ; count < graph. numVertices - 1 ; ++ count) { int minDist = INT_MAX, minIndex = - 1 ; for ( int v = 0 ; v < graph. numVertices; ++ v) { if ( ! visited[ v] && dist[ v] < minDist) { minDist = dist[ v] ; minIndex = v; } } visited[ minIndex] = true ; for ( const Edge& edge : graph. adjList[ minIndex] ) { int neighbor = edge. to; int weight = 1 ; if ( ! visited[ neighbor] && dist[ minIndex] + weight < dist[ neighbor] ) { dist[ neighbor] = dist[ minIndex] + weight; } } } return dist; }
} ;
时间复杂度分析 若采用邻接矩阵存储图，时间复杂度为(O(n^2))，其中(n)为顶点数。若使用堆优化，时间复杂度可降为(O((n + m)log n))，其中m为边数。 核心原理 可计算出图中任意两个顶点之间的最短路径。基于动态规划思想，对于任意两个顶点(i)和(j)，考虑是否经过中间顶点(k)来更新(i)到(j)的最短路径长度。 实现细节 使用二维数组dist存储顶点之间的最短路径长度。初始时，dist[i][j]为图中(i)到(j）的直接边权值（若有边），否则为无穷大。然后通过三层循环，依次以每个顶点k作为中间顶点更新dist[i][j]的值。以下是使用邻接矩阵存储图的 Floyd 算法示例代码： class FloydSP {
public : vector< vector< int >> floyd ( GraphMatrix& graph) { int n = graph. numVertices; vector< vector< int >> dist = graph. adjMatrix; for ( int k = 0 ; k < n; ++ k) { for ( int i = 0 ; i < n; ++ i) { for ( int j = 0 ; j < n; ++ j) { if ( dist[ i] [ k] != INT_MAX && dist[ k] [ j] != INT_MAX && dist[ i] [ k] + dist[ k] [ j] < dist[ i] [ j] ) { dist[ i] [ j] = dist[ i] [ k] + dist[ k] [ j] ; } } } } return dist; }
} ;
时间复杂度分析 时间复杂度为(O(n^3))，其中(n)为顶点数。由于时间复杂度较高，适用于顶点数较少的图或者对所有顶点对最短路径都有需求的场景。 核心原理 针对有向无环图（DAG），拓扑排序旨在将图中所有顶点排成一个线性序列，使得对于图中的任意一条有向边((u, v))，在序列中(u)均排在(v)之前。 实现方式（基于入度表） 首先统计每个顶点的入度，将入度为(0)的顶点入队。然后循环取出队首顶点，将其输出到拓扑序列中，并将其所有邻接点的入度减(1)，若某个邻接点入度变为(0)，则将其入队，直至队列为空。若最终输出的顶点数小于图中顶点总数，则说明图中有环，不存在拓扑排序。以下是拓扑排序的代码： # include <iostream> # include <vector> # include <queue> using namespace std;
struct Edge { int to; Edge ( int t) : to ( t) { }
} ;
class Graph {
public : int numVertices; vector< vector< Edge>> adjList; Graph ( int n) : numVertices ( n) , adjList ( n) { } void addEdge ( int from, int to) { adjList[ from] . push_back ( Edge ( to) ) ; }
} ; class TopologicalSort {
public : vector< int > topologicalSort ( Graph& graph) { int n = graph. numVertices; vector< int > inDegree ( n, 0 ) ; for ( int i = 0 ; i < n; i++ ) { for ( const Edge& edge : graph. adjList[ i] ) { inDegree[ edge. to] ++ ; } } queue< int > zeroDegreeQueue; for ( int i = 0 ; i < n; i++ ) { if ( inDegree[ i] == 0 ) { zeroDegreeQueue. push ( i) ; } } vector< int > topologicalOrder; while ( ! zeroDegreeQueue. empty ( ) ) { int current = zeroDegreeQueue. front ( ) ; zeroDegreeQueue. pop ( ) ; topologicalOrder. push_back ( current) ; for ( const Edge& edge : graph. adjList[ current] ) { inDegree[ edge. to] -- ; if ( inDegree[ edge. to] == 0 ) { zeroDegreeQueue. push ( edge. to) ; } } } if ( topologicalOrder. size ( ) < n) { cout << "图中存在环，无法进行拓扑排序" << endl; return { } ; } return topologicalOrder; }
} ; int main ( ) { Graph graph ( 6 ) ; graph. addEdge ( 5 , 2 ) ; graph. addEdge ( 5 , 0 ) ; graph. addEdge ( 4 , 0 ) ; graph. addEdge ( 4 , 1 ) ; graph. addEdge ( 2 , 3 ) ; graph. addEdge ( 3 , 1 ) ; TopologicalSort ts; vector< int > result = ts. topologicalSort ( graph) ; if ( ! result. empty ( ) ) { cout << "拓扑排序结果为: " ; for ( int vertex : result) { cout << vertex << " " ; } cout << endl; } return 0 ;
}
