typedefstructEdgeNode{；intmark,ivex,；structEdgeNode*ilink,*jl；}EdgeN；typedefstruct{；VertexD；EdgeNode*；}VertexN；typedefstruct{；VertexNodeverte
EdgeNode {
mark, ivex,
typedef struct {
typedef struct{
VertexNode
vertex［MAX-VERTEX-NUM］;
/*图的顶点数和弧数*/
/*图的种类*/
} AdjMultiL
/*基于图的邻接多重表表示法(Adjacency Multi-list)*/
7.3 图的遍历
从图中某一顶点出发访问图中其余顶点，每一个顶点仅被访问一次。这一过程叫做图的遍历。
7.3.1深度优先遍历
深度优先遍历(dfs，即depth-first search)类似于树的前序遍历。
假设初始时图中所有顶点未曾被访问，则深度优先遍历可以先访问图中某个顶点v0，然后依次从v0的未被访问的邻接点出发深度优先遍历图中尚未被访问的顶点，直至图中所有和v0有路径相通的顶点都被访问到，若此时图中尚有顶点未访问，则另选图中一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
＃define True
＃define False
＃define Error -1
＃define Ok 1
int visited［MAX-VERTEX-NUM］;
/*访问标志数组*/
TraverseGraph (Graph g)
/*对图g进行深度优先搜索，Graph 表示图的一种存储结构， 如数组表示法或邻接表等*/
for (vi=0; vi&g. vi++)
visited［vi］=F
/*访问标志数组初始*/
for( vi=0; vi&g. vi++)
/*调用深度遍历连通子图的操作*/
/*若图g是连通图， 则此循环调用函数只执行一次*/
if (！visited［vi］ )
DepthFirstSearch(g， vi)；
}/* TraverseGraph */
算法7.3 深度优先搜索图g
DepthFirstSearch（Graph g,
int v0） /*深度遍历v0所在的连通子图*/
visit（v0）； visited［v0］ =True； /*访问顶点v0， 并置访问标志数组相应分量值*/
w=FirstAdjVertex(g, v0);
while ( w![KG-*2]=-1)
/*邻接点存在*/
{ if(! visited ［w］ )
DepthFirstSearch(g, w);
/*递归调用DepthFirstSearch*/
w=NextAdjVertex(g, v0, w);
/*找下一个邻接点*/
} /*DepthFirstSearch*/
算法7.4 深度遍历v0所在的连通子图
1） 用邻接矩阵方式实现深度优先搜索
void DepthFirstSearch(AdjMatrix g, int v0)
/* 图g 为邻接矩阵类型AdjMatrix */
{visit(v0); visited［v0］=T
for ( vj=0; vj&n; vj++)
if (!visited［vj］ && g.arcs［v0］［vj］.adj==1)
DepthFirstSearch(g, vj);
}/* DepthFirstSearch */
采用邻接矩阵的DepthFirstSearch
2） 用邻接表方式实现深度优先搜索
DepthFirstSearch(AdjList g,
/*图g为邻接表类型AdjList */ {visit(v0) ； visited［v0］=True；
p=g.vertex［v0］.firstarc；
while( p! =NULL )
{if (! visited［p-&adjvex］)
DepthFirstSearch（g，
p-&adjvex）；
p=p-&nextarc；
}/*DepthFirstSearch*/
算法7.6 采用邻接表的DepthFirstSearch
3） 用非递归过程实现深度优先搜索
DepthFirstSearch(Graph g,
/*从v0出发深度优先搜索图g*/= {
InitStack(S);
/*初始化空栈*/
while ( ! Empty(S))
{ v=Pop(S);
if (!visited(v))
/*栈中可能有重复顶点*/
{ visit(v);
visited［v］=T
w=FirstAdj(g,
/*求v的第一个邻接点*/
if (!visited(w))
w=NextAdj(g,
/*求v相对于w的下一个邻接点*/
算法7.7 非递归形式的DepthFirstSearch
7.3.2.广度优先遍历
广度优先搜索（Breadth-First Search）是指照广度方向搜索，它类似于树的层次遍历，是树的按层次遍历的推广。广度优先搜索的基本思想是：
（1） 从图中某个顶点v0出发，首先访问v0。
（2） 依次访问v0的各个未被访问的邻接点。
（3） 分别从这些邻接点（端结点）出发，依次访问它们的各个未被访问的邻接点（新的端结点）。访问时应保证：如果vi和vk为当前端结点，vi在vk之前被访问， 则vi的所有未被访问的邻接点应在vk的所有未被访问的邻接点之前访问。重复（3）， 直到所有端结点均没有未被访问的邻接点为止。
BreadthFirstSearch(Graph g,
/*广度优先搜索图g中v0所在的连通子图*/
visit(v0);
visited［v0］=T
InitQueue(&Q);
/*初始化空队*/
EnterQueue(&Q, v0)；
/* v0进队*/
while ( ! Empty(Q))
{ DeleteQueue(&Q,
/*队头元素出队*/
w=FirstAdj(g, v);
/*求v的第一个邻接点*/
while (w! =-1 )
if (!visited(w))
{ visit(w);
visited［w］=T
EnterQueue(&Q,
w=NextAdj(g,
/*求v相对于w的下一个邻接点*/
算法7.8 广度优先搜索图g中v0所在的连通子图
7.4 图的连通性问题
7.4.1 无向图的连通分量
在对无向图进行遍历时，对于连通图，仅需一次调用遍历过程(dfs或bfs)，便从图中任一顶点出发，遍历图中各个顶点。对非连通图，则需多次调用遍历过程，而每次调用得到的顶点集，连同相关的边构成图的一个连通分量。
设G＝(V, E)为连通图，则从图中任一顶点出发遍历图时，必定将E(G)分成两个集合T和B，其中T是遍历图过程中走过的边的集合，B是剩余的边的集合：T?B=φ，T?B=E(G)。显然，G'＝(V, T)是G的极小连通子图，即是G的一棵生成树。
由深度优先遍历得到的称为深度优先生成树；由广度优先遍历得到的称为广度优先生成树。
对于非连通图，每个连通分量中的顶点集和遍历时走过的边一起构成一棵生成树，各个连通分量的生成树组成非连通图的生成森林。
显然，只要在遍历算法的基础上加进适当的语句，便可得到求连通分量或生成森林的算法。因此，它们的时间复杂性和遍历相同。
有向图的强连通分量
为求有向图的强连通分量，可以十字链表作有向图的存储结构，采用深度优先遍历算法，其步骤如下：
(1) 在有向图G上，从某个顶点出发沿以该顶点为尾的弧进行深度优先遍历，并按其所有邻接点的遍历都完成的顺序将顶点排列起来。
(2) 在有向图G上，从最后完成遍历的顶点出发沿着以该顶点为头的弧作逆向的深度优先遍历，若此次遍历不能访问到有向图中所有顶点，则从余下的顶点中最后完成遍历的顶点出发继续作逆向的深度优先遍历，依次类推，直至有向图中所有顶点都被访问到为止。
由此，每一次调用dfs作逆向深度优先遍历所访问到的顶点集便是有向图G中一个强连通分量的顶点集。
显然，利用上述方法求强连通分量的时间复杂性亦和遍历相同。
7.4.2 最小生成树
最小生成树具有下列性质(称为MST性质)：假设G＝(V, E)是一个连通网，T'是顶点集V的一个非空子集。若(u,w)是一条具有最小权值的边，其中u?T'，w?V(G)-T'，则必存在一棵包含边(u,w)的最小生成树T=(T',E')。大多数构造最小生成树的算法都利用了上述性质。
1) 普里姆（Prim）算法
假设N=(V, {E})是连通网，TE为最小生成树中边的集合。
（1） 初始U={u0}(u0∈V), TE=φ；
（2） 在所有u∈U,
v∈V-U的边中选一条代价最小的边（u0， v0）并入集合TE，同时将v0并入U；
（3） 重复（2）， 直到U=V为止。
此时，TE中必含有n-1条边，则T=（V，{TE}）为N的最小生成树。
可以看出， 普利姆算法逐步增加U中的顶点， 可称为“加点法”。
为了实现这个算法需要设置一个辅助数组closedge［ ］，以记录从U到V-U具有最小代价的边。对每个顶点v∈V-U，在辅助数组中存在一个分量closedge［v］，它包括两个域vex和lowcost，其中lowcost存储该边上的权， 显然有
closedge［v］.lowcost=Min({cost(u, v) | u∈U})
普里姆算法可描述如下：
} closedge［MAX_VERTEX_NUM］;
/* 求最小生成树时的辅助数组*/
MiniSpanTree-Prim(AdjMatrix
VertexData
/*从顶点u出发， 按普里姆算法构造连通网gn 的最小生成树， 并输出生成树的每条边*/ {
k=LocateVertex(gn,
closedge［k］.lowcost=0;
/*初始化， U={u} */
for (i=0; i&gn. i++)
if ( i! =k)
/*对V-U中的顶点i， 初始化closedge［i］*/
{closedge［i］.adjvex=u; closedge［i］.lowcost=gn.arcs［k］［i］. }
for (e=1; e&=gn.vexnum-1; e++)
/*找n-1条边(n= gn.vexnum) */
k0=Minium(closedge);
/* closedge［k0］中存有当前最小边（u0, v0）的信息*/
u0= closedge［k0］.
/* u0∈U*/
v0= gn.vexs［k0］
/* v0∈V-U*/
printf(u0,
/*输出生成树的当前最小边（u0, v0）*/
closedge［k0］.lowcost=0;
/*将顶点v0纳入U集合*/
for ( i=0 ; i& i++)
/*在顶点v0并入U之后， 更新closedge［i］*/
if ( gn.arcs［k0］［i］.adj &closedge［i］.lowcost)
{closedge［i］.lowcost= gn.arcs［k0］［i］.
closedge［i］.adjvex=v0;
算法7.9 普里姆算法
算法的时间复杂性为O(n2)，与网中的边数无关。因此，本算法适用于边稠密的网。
2) 克鲁斯卡尔(Kruskal)算法
假设N=(V, {E})是连通网，将N中的边按权值从小到大的顺序排列:
(1) 将n个顶点看成n个集合；
(2) 按权值由小到大的顺序选择边， 所选边应满足两个顶点不在同一个顶点集合内，将该边放到生成树边的集合中。同时将该边的两个顶点所在的顶点集合合并；
(3) 重复(2), 直到所有的顶点都在同一个顶点集合内。
可以看出，克鲁斯卡尔算法逐步增加生成树的边， 与普里姆算法相比，可称为“加边法”。
假设网中有e条边，算法的时间复杂性可以为O(eloge)，因此，它适用于边稀疏的网。
7.5 有向无环图的应用
有向无环图(DirectedAcyclicGraph)是指一个无环的有向图，简称DAG。有向无环图可用来描述工程或系统的进行过程，如一个工程的施工图、学生课程间的制约关系图等。
拓扑排序(TopologicalSort)
用顶点表示活动，用弧表示活动间的优先关系的有向无环图，称为顶点表示活动的网（Activity On Vertex Network），简称为AOV-网。
例如：计算机系学生的一些必修课程及其先修课程的关系如表7―2所示。
用顶点表示课程，弧表示先决条件，则表7―2所描述的关系可用一个有向无环图表示，见图7．21。
在有向图G：(V，&E&)中，V中顶点的线性序列(vi：，vi。，vi，，…，vh)称为拓扑序列，序列必须满足如下条件：对序列中任意两个顶点vi、vj，在G中有一条从vi到vj的路径，则在序列中vi必排在vj之前。
例如，图7．21的一个拓扑序列为：Cl，C2，C3, C4，C5，C8，C9，C7，C6。
AOV―网的特性如下：
?若vi为vj的先行活动，vj为vk的先行活动，则vi必为vk的先行活动，即先行关系
包含各类专业文献、文学作品欣赏、中学教育、幼儿教育、小学教育、专业论文、行业资料、应用写作文书、第7章 图67等内容。　
　基础知识) 第七章 图(基础知识) 7.1 【答案】在图 7.23(下图)所示的各无向图中: (1)找出所有的简单环。 (2)哪些图是连通图?对非连通图给出其连通... 　第7章 图 7.1 选择题 1.对于一个具有 n 个顶点和 e 条边的有向图,在用邻接表表示图时,拓扑排序算法时间复 杂度为( ) A) O(n) B) O(n+e) C)... 　(2)弧(Arc) 设 VR 是图中所有顶点之间的关系集,若&v,w&∈VR,则&v,w&表示从顶点 v -.167.- 第 7 章 图结构到顶点 w 的一条弧。 例如, 在图 7... 　下面哪一方法可以判断出一个有向图是否有环(回路) :( A.深度优先遍历 C.求最短路径 B. 拓扑排序 D. 求关键路径 ) (多选) 数据结构作业(第七章 图) 第... 　第7章 图_理学_高等教育_教育专区。图论7.1 单项选择题 1.在一个图中,所有顶点的度数之和等于所有边数的___倍。 A. 1/2 A.只有一棵 D.可能不存在 3... 　第7章 图 自测卷解答_工学_高等教育_教育专区。第 7 章图 自测卷解答一、单选题(每题 1 分,共 16 分) 单选题( 在一个图中, ( C )1. 在一个图中... 　第7章 图_数学_自然科学_专业资料。第7章 图 一、选择题 1.图中有关路径的定义是( )。 A.由顶点和相邻顶点序偶构成的边所形成的序列 B.由不同顶点所形... 　第7章 图 一、选择题 1.对于一个具有 n 个顶点和 e 条边的有向图,在用邻接表表示图时,拓扑排序 算法时间复杂度为( A) O(n) 【答案】B 2.设无向图... 　第7章 图 7.1 选择题 ) 1. 对于一个具有 n 个顶点和 e 条边的有向图, 在用邻接表表示图时, 拓扑排序算法时间复杂度为 ( A) O(n) 【答案】B 2....【图文】第7章(2) 图_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
第7章(2) 图
上传于||文档简介
&&淮​海​工​学​院​ ​汪​前​进​ ​数​据​结​构​课​件
大小：303.50KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢数据结构（6）
学完图 &只有一个感觉 ，术语真的好多。
图是一种非线性结构。图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有n(n-1)/2条边。
在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有n(n-1)条边。
在无向图G中，如果从顶点v到v‘有路径，则称v和v’是连通的。如果对于图中的任意两个结点都是连通的，则称G是连通图。
在有向图中同理。
1）邻接矩阵：
若图G是一个带权图，则把所有的1换成边的权值。
2）邻接表：
邻接表是对图中的每个顶点建立一个邻接关系的单链表，并把他们的表头指针用一维数组存储的一种图的表示方法。邻结表中的每个结点用来存储以该顶点为端点或起点的一条边的信息，因而叫边结点。边结点通常包含三个域：邻接点域（用来存储顶点Vi的一个邻接顶点Vj的序号j）；权值域（用来存储ij的权值）；链接域（用来链接邻接表的下一个结点）
3)边集数组
边集数组是利用一维数组存储图中所有边的一种图的表示方法，包含起点域，终点域，权值。
public interface GraphADT {
* 根据边集数组参数d建立一个图
* @param d
void create(EdgeElement[] d);
* 返回图的类型
int graphType();
* 返回图中的顶点数
int vertices();
* 返回图中的边数
int edges();
* 从图中查找一条边（i,j）是否存在
* @param i
* @param j
boolean find(int i,int j);
* 从图中插入一条边
* @param theEdge
void putEdge(EdgeElement theEdge);
* 从图中删除一条边（i,j）
* @param i
* @param j
void removeEdge(int i,int j);
* 返回顶点i的度
* @param i
int degree(int i);
* 返回顶点i的入度
* @param i
int inDegree(int i);
* 返回顶点i的出度
* @param i
int outDegree(int i);
* 以图的顶点集和边集的形式输出一个图
void outPut();
* 从顶点v开始深度优先搜索遍历图
* @param v
void depthFirstSearch(int v);
* 从顶点v开始广度优先搜索遍历图
* @param v
void breadthFirstSearch(int v);
* 定义边集数组中的元素类型
* @author Administrator
public class EdgeElement {
//边的起点域
//边的终点域
//边的权值域，假定为整型，对于无权图 ，权值可以为1
public EdgeElement(int v1,int v2) {
// TODO Auto-generated constructor stub
fromvex=v1;
endvex=v2;
public EdgeElement(int v1,int v2,int wgt) {
// TODO Auto-generated constructor stub
fromvex=v1;
endvex=v2;
import java.text.DateFormatS
import .SequenceQ
* 图的邻接矩阵存储类
* @author Administrator
public class AdjacencyGraph implements GraphADT{
private final int MaxValue=1000;
//一个不存在的变得使用的权值
//图的顶点数
//图的边数
//图的类型 0--&无向无权图，1--&无向有权图，2--&有向无权图，3--&有向有权图
private int[][]
//图的邻接矩阵，假定元素类型为int
public int MaxValue(){
//返回最大值常量
带权图中的边不存在时的常量
return MaxV
public int[][] getArray(){
//返回邻接矩阵
* @param n
* @param t
public AdjacencyGraph(int n,int t) {
// TODO Auto-generated constructor stub
if(n&1||t&0||t&3){
System.out.println(&初始化图的参数值出错&);
a=new int[n][n];
//给表示邻接矩阵的数组a分配存储空间
for(int i=0;i&n;i++){
for(int j=0;j&n;j++){
a[i][j]=0;
//对角线的元素被初始化为0
}else if(type==0||type==2){
a[i][j]=0;
//对无权图初始化为0
a[i][j]=MaxV
public void create(EdgeElement[] d) {
// TODO Auto-generated method stub
for(i=0;i&d.i++){
if(d[i]==null){
int v1,v2;
if(v1&0||v1&n-1||v2&0||v2&n-1||v1==v2){
System.out.println(&边的顶点序号无效&);
if(type==0){
a[v1][v2]=a[v2][v1];
}else if(type==1){
a[v1][v2]=a[v2][v1]=d[i].
}else if(type==2){
a[v1][v2]=1;
a[v1][v2]=d[i].
public int graphType() {
// TODO Auto-generated method stub
public int vertices() {
// TODO Auto-generated method stub
public int edges() {
// TODO Auto-generated method stub
public boolean find(int i, int j) {
// TODO Auto-generated method stub
if(i&0||i&n-1||j&0||j&n-1||i==j){
System.out.println(&边的顶点序号无效&);
if(a[i][j]!=0 && a[i][j]!=MaxValue){
public void putEdge(EdgeElement theEdge) {
// TODO Auto-generated method stub
int v1,v2;
v1=theEdge.
v2=theEdge.
if(v1&0||v1&n-1||v2&0||v2&n-1||v1==v2){
System.out.println(&边的顶点序号无效&);
if(a[v1][v2]==0||a[v1][v2]==MaxValue){
if(type==0||type==1){
if(type==0){
a[v1][v2]=a[v2][v1]=1;
a[v1][v2]=a[v2][v1]=theEdge.
if(type==2){
a[v1][v2]=1;
a[v1][v2]=a[v2][v1]=theEdge.
public void removeEdge(int i, int j) {
// TODO Auto-generated method stub
if(i&0||i&n-1||j&0||j&n-1||i==j){
System.out.println(&边的顶点序号无效&);
if(a[i][j]==0||a[i][j]==MaxValue){
System.out.println(&要删除的边不存在&);
if(type==0){
//删除无向无权图的边
a[i][j]=a[j][i]=0;
}else if(type==1){
//删除无向有权图的边
a[i][j]=a[j][i]=MaxV
}else if(type==2){
//删除有向无权图的边
a[i][j]=0;
//删除有向有权图的边
a[i][j]=MaxV
public int degree(int i) {
// TODO Auto-generated method stub
if(i&0||i&n-1){
System.out.println(&参数的顶点序号值无效&);
//k统计顶点i的度数
if(type==0||type==1){
for(int j=0;j&n;j++){
if(a[i][j]!=0 && a[j][i]!=MaxValue){
return inDegree(i)+outDegree(i);
public int inDegree(int i) {
// TODO Auto-generated method stub
if(i&0||i&n-1){
System.out.println(&参数的顶点序号值无效&);
if(type==0||type==1){
return -1;
for(int j=0;j&n;j++){
if(a[j][i]!=0 && a[j][i]!=MaxValue){
public int outDegree(int i) {
// TODO Auto-generated method stub
if(i&0||i&n-1){
System.out.println(&参数的顶点序号值无效&);
if(type==0||type==1){
return -1;
for(int j=0;j&n;j++){
if(a[i][j]!=0 && a[i][j]!=MaxValue){
public void outPut() {
// TODO Auto-generated method stub
System.out.print(&V={&);
for(i=0;i&n-1;i++){
System.out.print(i+&, &);
System.out.println(n-1+&}&);
//输出顶点集结束
System.out.print(&E={&);
if(type==0||type==2){
for(i=0;i&n;i++){
for(j=0;j&n;j++){
if(a[i][j]!=0 && a[i][j]!=MaxValue){
if(type==0){
System.out.print(&(&+i+&,&+j+&)&);
System.out.print(&&&+i+&,&+j+&&,&);
for(i=0;i&n;i++){
for(j=0;j&n;j++){
if(a[i][j]!=0&&a[i][j]!=MaxValue){
if(type==1){
System.out.println(&(&+i+&,&+j+&)&+a[i][j]+&,&);
System.out.print(&&&+i+&,&+j+&&&+a[i][j]+&,&);
System.out.println(&}&);
public void depthFirstSearch(int v) {
// TODO Auto-generated method stub
boolean[] visited=new boolean[n];
for(int i=0;i&n;i++){
visited[i]=
//每一个元素都被初始化为false
dfs(v, visited);
System.out.println();
private void dfs(int i,boolean[] visited){
//从初始点Vi出发深度优先搜索
System.out.print(i+& &);
//访问的顶点Vi以输出该顶点的序号代之
visited[i]=
//标记该顶点已经被访问过了
for(int j=0;j&n;j++){
if(a[i][j]!=0 && a[i][j]!=MaxValue && !visited[j]){
dfs(j, visited);
public void breadthFirstSearch(int v) {
// TODO Auto-generated method stub
boolean[] visited=new boolean[n];
for(int i=0;i&n;i++){
visited[i]=
bfs(v, visited);
System.out.println();
private void bfs(int i,boolean[] visited){
SequenceQueen q=new SequenceQueen();
System.out.print(i+& &);
visited[i]=
q.enter(i);
while(!q.isEmpty()){
int k=(int) q.leave();
for(int j=0;j&n;j++){
if(a[k][j]!=0 && a[k][j]!=MaxValue && !visited[j]){
System.out.print(j+& &);
visited[j]=
q.enter(j);
在这里暂时只有用边集数组表示的图，下次有时间补上其他的代码。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：4627次
排名：千里之外
原创：28篇
转载：15篇
(1)(1)(1)(5)(1)(16)(5)(1)(3)(9)数据结构期末复习（8）
1.图：图G是由顶点集V和边集E组成，顶点集是有穷非空集，边集是有穷集；
2.G中每条边都有方向称有向图；有向边称弧；边的始点称弧尾；边的终点称弧头；G中每条边都没有方向的称无向图。
3.顶点n与边数e的关系：无向图的边数e介于0~n(n-1)/2之间，有n(n-1)/2条边的称无向完全图；有向图的边数e介于0~n(n-1)之间，有n(n-1)条边的称有向完全图；
4.无向图中顶点的度是关联与顶点的边数；有向图中顶点的度是入度与出度的和。
所有图均满足：所有顶点的度数和的一半为边数。
5.图G（V，E），如V’是V的子集，E’是E的子集，且E’中关联的顶点均在V’中，则G’(V’,E’)是G的子图。
6.在有向图中，从顶点出发都有路径到达其它顶点的图称有根图；
7.在无向图中，任意两个顶点都有路径连通称连通图；极大连通子图称连通分量；
8.在有向图中，任意顺序两个顶点都有路径连通称强连通图；极大连通子图称强连通分量；
9.将图中每条边赋上权，则称带权图为网络。
10.图的存储结构：
（1）邻接矩阵表示法：邻接矩阵是表示顶点间相邻关系的矩阵。n个顶点就是n阶方阵。
无向图是对称矩阵；有向图行是出度，列是入度。
（2）邻接表表示法：对图中所有顶点，把与该顶点相邻接的顶点组成一个单链表，称为邻接表，adjvex|next,如要保存顶点信息加入data；对所有顶点设立头结点，vertex|firstedge,并顺序存储在一个向量中；vertex保存顶点信息，firstedge保存邻接表头指针。
11.邻接矩阵表示法与邻接表表示法的比较：
& 1） 邻接矩阵是唯一的，邻接表不唯一；
& 2） 存储稀疏图用邻接表，存储稠密图用邻接矩阵；
& 3） 求无向图顶点的度都容易，求有向图顶点的度邻接矩阵较方便；
& 4） 判断是否是图中的边，邻接矩阵容易，邻接表最坏时间为O(n)；
& 5） 求边数e，邻接矩阵耗时为O(n^2)，与e无关，邻接表的耗时为O(e+n)；
12.图的遍历：
（1）图的深度优先遍历：类似与树的前序遍历。按访问顶点次序得到的序列称DFS序列。
对邻接表表示的图深度遍历称DFS，时间复杂度为O(n+e); 对邻接矩阵表示的图深度遍历称DFSM，时间复杂度为O(n^2);
（2）图的广度优先遍历：类似与树的层次遍历。按访问顶点次序得到的序列称BFS序列。
对邻接表表示的图广度遍历称BFS，时间复杂度为O(n+e); 对邻接矩阵表示的图广度遍历称BFSM，时间复杂度为O(n^2);
13. 将没有回路的连通图定义为树称自由树。
14.生成树：连通图G的一个子图若是一棵包含G中所有顶点的树，该子图称生成树。
有DFS生成树和BFS生成树，BFS生成树的高度最小。
非连通图生成的是森林。
15.最小生成树：将权最小的生成树称最小生成树。（是无向图的算法）
（1）普里姆算法：
& &1） 确定顶点S、初始化候选边集T[0~n-2]；formvex|tovex|lenght
& &2） 选权值最小的T[i]与第1条记录交换；
& &3） 从T[1]中将tovex取出替换以下记录的fromvex计算权；若权小则替换，否则不变；
& &4） 选权值最小的T[i]与第2条记录交换；
& &5） 从T[2]中将tovex取出替换以下记录的fromvex计算权；若权小则替换，否则不变；
& &6） 重复n-1次。
初始化时间是O(n),选轻边的循环执行n-1-k次，调整轻边的循环执行n-2-k；算法的时间复杂度为O(n^2)，适合于稠密图。
（2）克鲁斯卡尔算法：
& &1） 初始化确定顶点集和空边集；对原边集按权值递增顺序排序；
& &2） 取第1条边，判断边的2个顶点是不同的树，加入空边集，否则删除；
& &3） 重复e次。
对边的排序时间是O(elog2e)；初始化时间为O(n)；执行时间是O(log2e)；算法的时间复杂度为O(elog2e)，适合于稀疏图。
16. 路径的开始顶点称源点，路径的最后一个顶点称终点；
17.单源最短路径问题：已知有向带权图，求从某个源点出发到其余各个顶点的最短路径；
18.单目标最短路径问题：将图中每条边反向，转换为单源最短路径问题；
19.单顶点对间最短路径问题：以分别对不同顶点转换为单源最短路径问题；
20.所有顶点对间最短路径问题：分别对图中不同顶点对转换为单源最短路径问题；
21.迪杰斯特拉算法：
& 1） 初始化顶点集S[i],路径权集D[i],前趋集P[i]；
& 2） 设置S[s]为真，D[s]为0；
& 3） 选取D[i]最小的顶点加入顶点集；
& 4） 计算非顶点集中顶点的路径权集；
& 5） 重复3）n-1次。
算法的时间复杂度为O(n^2)。
22.拓扑排序：对一个有向无环图进行拓扑排序，是将图中所有顶点排成一个线性序列，满足弧尾在弧头之前。这样的线性序列称拓扑序列。
（1）无前趋的顶点优先：总是选择入度为0的结点输出并删除该顶点的所有边。
设置各个顶点入度时间是O(n+e)，设置栈或队列的时间是O(n)，算法时间复杂度为O(n+e)。
（2）无后继的顶点优先：总是选择出度为0的结点输出并删除该顶点的所有边。
设置各个顶点出度时间是O(n+e)，设置栈或队列的时间是O(n)，算法时间复杂度为O(n+e)。
求得的是逆拓扑序列。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：22532次
排名：千里之外
原创：72篇
转载：14篇
(1)(1)(1)(3)(2)(4)(2)(3)(5)(2)(9)(35)(18)