返回分类：全部文章 >> 基础知识
本文将介绍图的基础知识，并用C++实现它。
它包含两部分：
在查看本文之前，需要一些数据结构和程序语言的基础。
尤其是“二维数组”、“矩阵”、“矩阵的压缩(matrix)” 。一些遍历和应用的内容还需要“栈(stack)” ，“队列(queue)” ，“二叉树(binary tree)” 等的知识。
图的概念很多，我们只说一些重要的，其它可以去查资料。
图的基本存储方式有：
邻接矩阵 (Adjacency Matrix)
邻接表 (Adjacency List)
十字链表 (Orthogonal List)
邻接多重表 (Adjacency Multilist)
在图的邻接矩阵表示中：
顶点列表：记录各个顶点的数据信息；
邻接矩阵：表示各个顶点之间的关系（边或权）；
其中无向图的邻接矩阵是对称方阵，有向图的邻接矩阵不一定对称。
Tips 特殊矩阵的压缩存储 (Compressed Storage of Special Matrix)
无向图的邻接矩阵，一般只存储与其它结点是否连接，0表示没有连接，1表示右连接。
其矩阵为：
A B C D E F A 0 1 0 0 1 0 B 1 0 0 1 1 1 C 0 0 0 1 0 1 D 0 1 1 0 0 0 E 1 1 0 0 0 0 F 0 1 1 0 0 0
\begin{matrix}
&A &B &C &D &E &F \\[2ex]
A &0 &1 &0 &0 &1 &0 \\[2ex]
B &1 &0 &0 &1 &1 &1 \\[2ex]
C &0 &0 &0 &1 &0 &1 \\[2ex]
D &0 &1 &1 &0 &0 &0 \\[2ex]
E &1 &1 &0 &0 &0 &0 \\[2ex]
F &0 &1 &1 &0 &0 &0
\end{matrix}
A B C D E F A 0 1 0 0 1 0 B 1 0 0 1 1 1 C 0 0 0 1 0 1 D 0 1 1 0 0 0 E 1 1 0 0 0 0 F 0 1 1 0 0 0
有向图的邻接矩阵，分有没有权值：
没有权值依然存储0或者1；
有权值的话存储的是权值，其矩阵也叫网络邻接矩阵，如果无连接用无穷符号（ ∞ \infin ∞
其矩阵为：
A B C D E F A ∞ 6 ∞ ∞ 3 ∞ B 2 ∞ ∞ 1 9 0 C ∞ ∞ ∞ 2 ∞ 0 D ∞ ∞ ∞ ∞ ∞ ∞ E ∞ ∞ ∞ ∞ ∞ ∞ F ∞ ∞ ∞ ∞ 3 ∞
\begin{matrix}
&A &B &C &D &E &F \\[2ex]
A &\infin &6 &\infin &\infin &3 &\infin \\[2ex]
B &2 &\infin &\infin &1 &9 &0 \\[2ex]
C &\infin &\infin &\infin &2 &\infin &0 \\[2ex]
D &\infin &\infin &\infin &\infin &\infin &\infin \\[2ex]
E &\infin &\infin &\infin &\infin &\infin &\infin \\[2ex]
F &\infin &\infin &\infin &\infin &3 &\infin
\end{matrix}
A B C D E F A ∞ 2 ∞ ∞ ∞ ∞ B 6 ∞ ∞ ∞ ∞ ∞ C ∞ ∞ ∞ ∞ ∞ ∞ D ∞ 1 2 ∞ ∞ ∞ E 3 9 ∞ ∞ ∞ 3 F ∞ 0 0 ∞ ∞ ∞
顶点的度：
无向图：其所在行或列的元素之和；
有向图：
出度：顶点所在行元素之和；
入度：顶点所在列元素之和。
假设图中有 n n n e e e n 2 n^2 n 2
无向图：有 2 e 2e 2 e
有向图：有 e e e
若 e e e n 2 n^2 n 2
若 e e e n 2 n^2 n 2
邻接矩阵更适合稠密图。
对一个图来说，邻接矩阵是唯一确定的；
查找所有顶点的邻接顶点的时间复杂度为 O ( n 2 ) O(n^2) O ( n 2 )
其基本结构C++代码为：
#pragma once
#include <limits>
#include <vector>
namespace Graphs
{
template < typename T>
class AdjacencyMatrix
{
public :
static constexpr double INFINITE_WEIGHT = std:: numeric_limits< double > :: max ( ) ;
protected :
std:: vector< T> * m_Vertexes;
std:: vector< std:: vector< double >> * m_Edges;
public :
T GetVertex ( int index) ;
void PutVertex ( int index, const T& vertex) ;
double GetWeight ( int startVertex, int endVertex) ;
void PutWeight ( int startVertext, int endVertex, double weight) ;
public :
AdjacencyMatrix ( bool oriented) ;
AdjacencyMatrix ( const std:: vector< T> & vertexElements, bool oriented) ;
virtual ~ AdjacencyMatrix ( ) ;
public :
bool InitializeVertexes ( std:: vector< T> & vertexElements) ;
bool InitializeEdges ( std:: vector< int > & startVertex,
std:: vector< int > & endVertexes, std:: vector< double > & weights) ;
int GetVertexCount ( ) ;
int GetEdgeCount ( ) ;
int FirstNeighbor ( int index) ;
int NextNeighbor ( int index, int neighborIndex) ;
} ;
}
在图的邻接表中：
其基本结构C++代码为：
#pragma once
#include <vector>
namespace Graphs
{
class ALEdgeNode
{
public :
int destination;
double weight;
ALEdgeNode* next;
ALEdgeNode ( int dest, double w)
{
destination = dest;
weight = w;
next = 0 ;
}
~ ALEdgeNode ( )
{
delete next;
next = 0 ;
}
} ;
template < typename T>
class ALVertexNode
{
public :
T element;
ALEdgeNode* firstEdge;
ALVertexNode ( const T& e)
{
element = e;
firstEdge = 0 ;
}
~ ALVertexNode ( )
{
delete firstEdge;
firstEdge = 0 ;
}
} ;
template < typename T>
class AdjacencyList
{
protected :
std:: vector< ALVertexNode< T> * > * m_Vertexes;
public :
T GetVertex ( int index) ;
void PutVertex ( int index, const T& vertex) ;
double GetWeight ( int startVertex, int endVertex) ;
void PutWeight ( int startVertext, int endVertex, double weight) ;
public :
AdjacencyList ( ) ;
virtual ~ AdjacencyList ( ) ;
public :
bool InitializeVertexes ( std:: vector< T> & vertexElements) ;
bool InitializeEdges ( std:: vector< int > & startVertex, std:: vector< int > & endVertexes, std:: vector< double > & weights) ;
int GetVertexCount ( ) ;
int GetEdgeCount ( ) ;
int FirstNeighbor ( int index) ;
int NextNeighbor ( int index, int neighborIndex) ;
} ;
}
十字链表是有向图的存储格式 ，它是由邻接表和逆邻接表结合后的产物。在这之中我们称边为弧。
其中弧包括：
而顶点包括：
（1）数据；
（2）第一条入弧；
（3）第一条出弧；
十字链表举例：
0：element A, firstin NULL, firstout A->B
A->B: head 0(A), tail 1(B), right A->D, down C->B
A->D: head 0(A), tail 3(D), right NULL, down NULL
1：element B, firstin A->B, firstout B->C
B->C: head 1(B), tail 2(C), right NULL, down D->C
2：element C, firstin B->C, firstout C->B
C->B: head 2(C), tail 1(B), right NULL, down NULL
3：element D, firstin A->D, firstout D->C
D->C: head 3(D), tail 2(C), right NULL, down NULL
我使用了文字描述，图示与矩阵结构相同，下面用矩阵来说明。
放在矩阵中去看，非常清晰。
A B C D A ∞ 1 ∞ 1 B ∞ ∞ 1 ∞ C ∞ 1 ∞ ∞ D ∞ ∞ 1 ∞
\begin{matrix}
&A &B &C &D \\[2ex]
A &\infin &1 &\infin &1 \\[2ex]
B &\infin &\infin &1 &\infin \\[2ex]
C &\infin &1 &\infin &\infin \\[2ex]
D &\infin &\infin &1 &\infin
\end{matrix}
A B C D A ∞ ∞ ∞ ∞ B 1 ∞ 1 ∞ C ∞ 1 ∞ 1 D 1 ∞ ∞ ∞
首先是A：
再看B：
第一条出弧，即行中第一条弧：Vertex(B)->firstout = Arc(B, C)
弧头指向的下一条弧，即行中下一个弧：Arc(B, C)->right = NULL
指向同一个弧尾的下一条弧，即列中下一个弧：Arc(B, C)->down = Arc(D, C)
第一条入弧，即列中第一条弧：Vertex(B)->firstin = Arc(A, B)
其基本结构C++代码为：
#pragma once
#include <vector>
namespace Graphs
{
class ArcNode
{
public :
int row;
int col;
double weight;
ArcNode* nextCol;
ArcNode* nextRow;
ArcNode ( int r, int c, double w)
{
row = r;
col = c;
weight = w;
nextCol = 0 ;
nextRow = 0 ;
}
~ ArcNode ( )
{
delete nextCol;
nextCol = 0 ;
delete nextRow;
nextRow = 0 ;
}
} ;
template < typename T>
class OLVertexNode
{
public :
T element;
ArcNode* firstOut;
ArcNode* firstIn;
OLVertexNode ( )
{
firstOut = 0 ;
firstIn = 0 ;
}
~ OLVertexNode ( )
{
delete firstOut;
firstOut = 0 ;
delete firstIn;
firstIn = 0 ;
}
} ;
template < typename T>
class OrthogonalList
{
protected :
std:: vector< OLVertexNode< T> * > * m_Vertexes;
} ;
}
类似的，邻接多重表是为了解决邻接表中每条边都存储两次的问题。
其边结点：
其顶点结点：
我们以有向图（无向图同理）为例：
以边Edge(A-B)为例：
vertex1为A，vertex2为B；
path1为Edge(A->D)；
path2为Edge(B->C)；
其基本结构C++代码为：
#pragma once
#include <vector>
namespace Graphs
{
class AMLEdgeNode
{
public :
int mark;
int row;
int col;
double weight;
AMLEdgeNode* nextRow;
AMLEdgeNode* nextCol;
AMLEdgeNode ( int r, int c, double w)
{
row = r;
col = c;
weight = w;
nextRow = 0 ;
nextCol = 0 ;
}
~ AMLEdgeNode ( )
{
nextRow = 0 ;
nextCol = 0 ;
}
} ;
template < typename T>
class AMLVertexNode
{
public :
T element;
AMLEdgeNode* firstOut;
AMLEdgeNode* firstIn;
AMLVertexNode ( const T& e)
{
element = e;
firstOut = 0 ;
firstIn = 0 ;
}
~ AMLVertexNode ( )
{
firstOut = 0 ;
firstIn = 0 ;
}
} ;
template < typename T>
class AdjacencyMultilist
{
protected :
std:: vector< AMLVertexNode< T> * > * m_Vertexes;
} ;
}
后接 编程基础 - 图 II (Graph II)
实例待补充，如果有补充将会在这里更新链接。
转播
