a[ ]="((0,1),(0,2),(0,3),(1,4),(1,5),(1,6),(2,6),(4,5))";
如何读取字符串中每条边？
利用字符串输入流每次读取5个字符
数据结构与算法 Data Structures and Algorithms
#include<sstream>
字符串流头文件
istringstream sin(s); char c1,c2,c3;
e
(b) G6 E(G)={<0,1>2,<0,2>3,<0,3>8,<1,3>12,<2,0>6,<2,3>6,
<2,4>1,<3,4>4}
数据结构与算法 Data Structures and Algorithms
7.1.3 图的抽象数据类型 数据部分： 为一个图G，采用顺序、链接等任一种存储结构， 假定存储类型用GraphType标识符表示， 操作部分： 包括初始化图、建立图、遍历图、查找图、输出 图、清除图等常用运算，以及求图的最小生成树、最 短路径、拓扑排序、关键路径等特定运算。
typedef int adjmatrix[MaxVertemNum][MaxVertemNum];
邻接矩阵
数据结构与算法 Data Structures and Algorithms
1. 图的邻接矩阵存储的初始化算法
void InitMatrix(adjmatrix GA,int k) { int i,j;
数据结构与算法 Data Structures and Algorithms
7.2 图的存储结构
邻接矩阵
邻接表 边集数组
数据结构与算法 Data Structures and Algorithms
1. 邻接矩阵(adjacency matrix)表示法
利用矩阵表示图形中顶点之间相邻关系
a 2 TJ 4 c e (b) G4
b
d
f
5. 路径和回路 路径(path)：从顶点v到顶点v'的一个顶点序列。序列 中的第一个顶点为v，最后一个顶点为v'。 路径长度是指该路径上经过的边的数目。
简单路径：一条路径上的所有顶点均不同。
回路或环(cycle)：一条路径上的前后两端点相同。 简单回路或简单环：除前后两端点相同外，其余顶点 均不同的回路。
邻接矩阵的大小怎么确定？
由图中顶点数确定
无向图的邻接矩阵为对称矩阵
数据结构与算法 Data Structures and Algorithms
(1,4)
0 0 A2 0 0 0
1 1 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 0 1 0
行标为起点
列标为终点
(2,1)
数据结构与算法 Data Structures and Algorithms
(1,4)
0 7 2
5 12 6
1 3 3 (a) G5 15
8 4 20
0 5 7 0 a 6 5 0 122 3 8 3 1 A1 7 12 0 6 20 b 8 3 6 0 15 6 8 1220 15 0 4 3 d e
数据结构与算法 Data Structures and Algorithms
6. 连通和连通分量 在无向图G中，若从顶点vi到顶点vj有路径，则
称vi和vj是连通的。
若图G中任意两个顶点都连通，则称G为连通 图，否则称为非连通图。 无向图G的极大连通子图称为G的连通分量。 任何连通图都可以通过一个连通分量把所有顶
端点
0 1 2 3 2 C
互为邻接点 0
A
端点
4 (a) G1
数据结构与算法 Data Structures and Algorithms
5
3 D (b) G2
A的出边 B的入边 起点
0 A 3B的入边 1 B
终点
邻接点
3 D
2 C 4 E (b) G2
A的出边 邻接点
5
G1
数据结构与算法 Data Structures and Algorithms
从vi到vj是连通的。若图G中的任意两个顶点vi和vj都
连通，即从vi到vj和从vj到vi都存在路径，则称G是强
连通图。有向图G的极大强连通子图称为G的强连通
分量。
强连通图可以通过一个强连通分量把所有结点
连通起来，非强连通图有多个强连通分量。
数据结构与算法 Data Structures and Algorithms
图的结点数
const int MaxVertexNum; const int MaxEdgeNum; typedef int WeightType;
权重类型 定义∞
const WeightType MaxValue = ?;
顶点信息
typedef VertexType vexlist[MaxVertemNum];
数据结构与算法 Data Structures and Algorithms
DAT GRAPH is Data: 一个图G，存储类型用标识符GraphType表示 Operations： void InitGraph(GraphType& G); void CreateGraph(GraphType& G, char* E, int n); void TraverseGraph(GraphType& G, int i, int n); bool FindGraph(GraphType& G, VertexType& item, int n); void PrintGraph(GraphType& G, int n); void ClearGraph(GraphType& GT); void MinSpanGraph(GraphType& G, int n); void MinPathGraph(GraphType& G, int n); void TopolGraph(GraphType& G, int n); void KeyPathGraph(GraphType& G, int n); end GeneralTree
点连通起来，而非连通图有多个连通分量。
数据结构与算法 Data Structures and Algorithms
CA
C A
E
C
E
E
A
B (b)
D B (c) (a) (b)
D
FD
(d) (c)
F B
(c)
(d)
数据结构与算法 Data Structures and Algorithms
7. 强连通图和强连通分量 在有向图G中，若从顶点vi到顶点vj有路径，则称
字符串输入流
int i,j;
WeightType w;
sin>>c1;
数据结构与算法 Data Structures and Algorithms
数据结构与算法 Data Structures and Algorithms
图的邻接矩阵表示应如何实现？
adjmatrix[ ][ ]
一个二维数组
存储顶点之间相邻的关系
一个一维数组
vexlist[ ]
存储图中n个顶点元素的信息
数据结构与算法 Data Structures and Algorithms
(4,1)
(b) G6
数据结构与算法 Data Structures and Algorithms
1 b
2 8
0 a 3
6 2 c 6 1 4
12 3 d
4 (b) G6
e
0 2 3 8 0 12 A2 6 0 6 1 0 4 0
D(VB)=2+2=4
5
G1
(b) G2 入度：该顶点的入边的数目，记为 ID(v)；
出度：该顶点的出边的数目，记为OD(v)；
D(v)=ID(v)+OD(v)
数据结构与算法 Data Structures and Algorithms
3. 完全图、稠密图、稀疏图 若无向图中的每两个顶点之间都存在着一条边， 有向图中的每两个顶点之间都存在着方向相反的两 条边，则称此图为完全图。
有向图
0 A 3 2 C 3 D (b) G2 4 E 1 B
5
V(G)={A,B,C,D,E}
E(G)={<A,B>,<A,C>,<B,C>,<B,E>,<C,B>,<C,D>,<E,D>}
数据结构与算法 Data Structures and Algorithms
7.1.2 图的基本术语
1. 端点和邻接点
k=0：无权图 k≠0：有权图
for(i=0;i<MaxVertexNum;i++)
for(j=0;j<MaxVertexNum;j++)
if(i= =j) GA[i][j]=0; else if(k) GA[i][j]=MaxValue; else GA[i][j]==0; }
数据结构与算法 Data Structures and Algorithms
数据结构与算法 Data Structures and Algorithms
无向图
0 1 2 4 5 (a) G1 3 D 3 2 0 A
V(G)={0,1,2,3,4,5}
(