G = (V, R) V={A, B, C, D, E} R={<A,B>, <A,E>, <B,C>, <C,D>, <D,B>,<D,A>, <E,C> }
有向图、无向图
A
B
E
CD
B A
F
C D
E
邻接点、度
A
B
E
CD
B A
F
C D
E
子图
A
B
E
CD
B CD
稀疏图、稠密图
n:顶点个数 e:边数 e ≧ nlogn
int v1 = theEdge->vertex1(); int v2 = theEdge->vertex2(); if (v1 < 1 || v2 < 1 || v1 > n || v2 > n || v1 == v2)
throw std::out_of_range("invalid");
template <class T> bool adjacencyWDigraph<T>::existsEdge(int i, int j) const {// Return true iff (i,j) is an edge of the graph.
if (i < 1 || j < 1 || i > n || j > n || a[i][j] == noEdge) return false;
路径和路径长度
A
B
E
C
D
A->B->C->D A->E->C->D
简单路径
A
B
E
C
D
A->B->C->D A->E->C->D->B->C->D
连通图
B
C
A
D
F
E
a、连通图
B
C
A
D
F
E
b、非连通图
强连通图
A
B
E
CD
a、强连通图
A
B
E
CD
b、非强连通图
生成树
B A
F
C
D E
B A
F
C
D E
网
A
for (int i = 1; i <= n; i++)
// initialize adjacency matrix std::fill(a[i], a[i] + n + 1, noEdge);
A0
}
B0
C0
D0
E0
BCD E
0000 0000 0000 0000 0000
AdjacencyWDigraph
15
A9
11
B7 3
21
E
C2 D
图的存储表示
一、图的数组(邻接矩阵)存储表示 二、图的邻接表存储表示 三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示
无向图-邻接矩阵
B A
F
C D
E
ABCD E F
A010010 B100011 C000101 D0 0 1 0 0 1 E110000 F011100
else return true;
} template <class T> void adjacencyWDigraph<T>::eraseEdge(int i, int j) {// Delete the edge (i,j).
if (i >= 1 && j >= 1 && i <= n && j <= n && a[i][j] != noEdge) {
数据结构
｛a1, a2, a3, …, an} 研究数据的组织方法，以提高程序性能 。
研究在线性存储模型中，如何用顺序、链式或二者的组合 方式组织数据，以提高增、删、改、查的性能。
线性存储器模型
0 1 2 3
……
n
内存？外存？
1、编程空间 2、流式文件 3、……
实例
假设有5位同学的成绩表： 2006001 99 2006003 80 2006004 85 2006005 60 2006006 70
组织方式－顺序
存储地址 Lo
Lo+m
存储内容 元素1
元素2
……..
Lo+(i-1)*m 元素i ……..
Lo+（n-1)*m 元素n
2006001 99 2006003 80 2006004 85 2006005 60 2006006 70
组织方式－链式
存储内容
L0
元素1
P
2006001 99
元素3
1、邻接矩阵 2、邻接表 3、十字链表
V2
V1
V4
V3
类的派生层次－基于邻接矩阵
AdjacencyWDigraph
graph
AdjacencyWgraph
AdjacencyDigraph
Adjacencygraph
graph类
template<class T> class graph{
public: virtual ~graph() {} virtual int numberOfVertices() const = 0; virtual int numberOfEdges() const = 0; virtual bool existsEdge(int, int) const = 0; virtual void insertEdge(edge<T>*) = 0; virtual void eraseEdge(int, int) = 0; virtual int degree(int) const = 0; virtual int inDegree(int) const = 0; virtual int outDegree(int) const = 0; virtual bool directed() const = 0; virtual bool weighted() const = 0; virtual vertexIterator<T>* iterator(int) = 0; virtual void output(std::ostream&) const = 0;
AdjacencyWDigraph
template <class T> bool adjacencyWDigraph<T>::make2dArray(T ** &x, int numberOfRows, int numberOfColumns) {// Create a two dimensional array.
AdjacencyWDigraph
。。。。。 public:
adjacencyWDigraph(int numberOfVertices = 0, T theNoEdge = 0); ~adjacencyWDigraph(){delete2dArray(a, n + 1);}; int numberOfVertices() const{return n;} int numberOfEdges() const {return e;} bool existsEdge(int, int) const; void insertEdge(edge<T>*); void eraseEdge(int, int); int degree(int) const{throw std::invalid_argument("no degree");} int inDegree(int) const; int outDegree(int) const; bool directed() const {return true;} bool weighted() const {return true;} vertexIterator<T>* iterator(int) ; void output(std::ostream&) const ; private: bool make2dArray(T ** &x, int numberOfRows, int numberOfColumns); void checkVertex(int theVertex) const; };
if (numberOfVertices < 0)
throw std::out_of_range("number of vertices must be >= 0");
n = numberOfVertices;
e = 0;
noEdge = theNoEdge;
make2dArray(a, n + 1, n + 1);
};
AdjacencyWDigraph
template <class T> class weightedEdge : public edge<T> {
public: weightedEdge(int theV1, int theV2, T theW) {v1 = theV1; v2 = theV2; w = theW;} ~weightedEdge() {}; int vertex1() const {return v1;} int vertex2() const {return v2;} T weight() const {return w;} operator T() const {return w;} void output(std::ostream& out) const{ out << "(" << v1 << ", " << v2 << ", " << w << ")