计算机考研：数据结构常用算法精析(7)
数据结构是计算机考研408计算机学科专业基础综合的重要组成部分，考生需要认真复习，尤其是对于数据结构中一些常用的算法问题，考生一定要弄懂弄会，理解的去掌握。新东方在线小编下面一一为大家分析一下，帮助考生更好地去掌握。第七章：
对于无向图，e的范围是：
数据结构中所讨论的图都是简单图，任意两结点间不会有双重的边。
对于有向图，e的范围是：
图的各种存储结构
邻接矩阵很方便访问任意两点的边，但是不方便计算其邻接点。在深度和广度遍历中广泛的需要求某点的邻接点。所以邻接矩阵只在Floyed和Prim和Dijstra中采用。
邻接表能很方便的求某顶点的邻接点，索引对于与遍历有关的算法大多都采用邻接表。如深度、广度、拓扑排序、关键路径。但他也有不足的地方，就是不方便求入度或是那些点可以到他的操作。所以有人引进逆邻接表。最后人们把这两种表结合到一起就是十字链表和邻接多重表。一个是存储有向图，另一个是存储无向图。
在十字链表和邻接多重表很方便求邻接点的操作和对应的逆操作。所以实际应用中，凡是能用邻接表实现的一定能用十字链表和邻接多重表实现。并且它们的存储效率更高。
1.邻接矩阵(有向图和无向图和网)又称为数组表示法
typedef struct
{ vextype vexs; ∥顶点存储空间∥
adjtype A; ∥邻接矩阵∥
int vexnum,arcnum; //图的顶点数和边数
GraphKind Kind; //图的类型
} mgraph;
2.邻接表(有向图和无向图和网)
typedef struct node ∥边
{ int adj; int w; ∥邻接点、权∥
struct node *next; ∥指向下一弧或边∥
}linknode;
typedef struct ∥顶点类型∥
{ vtype data; ∥顶点值域∥
linknode *farc; ∥指向与本顶点关联的第一条弧或边∥
}Vnode;
typedef struct
{
Vnode G; ∥顶点表∥
int vexnum,arcnum;
GraphKind kind;
}ALGraph;
adjvexnextarcinfo
边结点
datafirstarc
顶点结点
3.十字链表(有向图和有向网)
headvextaivexhlinktlinkinfo
边结点
datafirstinfirstout
顶点结点
4.邻接多重表(无向图)
markivexjvexilinkjlinkinfo
边结点
datafirstedge
顶点结点
有向无环图(DAG)：是描述含有公共子式的表达式的有效工具。二叉树也能表示表达式，但是利用有向无环图可以实现对相同子式的共享，从而节省存储空间。
顶点的度：
无向图：某顶点V的度记为D(V)，代表与V相关联的边的条数
有向图：顶点V的度D(V)=ID(V)+OD(V)
强连通分量:在有向图中，若图中任意两顶点间都存在路径，则称其是强连通图。图中极大 强连通子图称之为强连通分量
“极大”在这里指的是：往一个连通分量中再加入顶点和边，就构不成原图中的一个
连通子图，即连通分量是一个最大集的连通子图。有向图的连通就是指该有向图是
强连通的
遍历图的过程实质上是_对每个顶点查找其邻接点的过程___
其耗费的时间主要取决于采用的存储结构。当用邻接矩阵存储图时，查找每个顶点的邻接点所需的时间O(
)，其中n是图中顶点数。而当用邻接表存储图时，找邻接点的所需时间为O(e)，其中e为图中边的个数或有向弧的个数，由此，当以邻接表作为存储结构时，深度优先搜索遍历图的时间复杂度O(n+e).
广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者的不同之处仅在于对结点访问的顺序不同。也就是说他们的时间复杂度都取决于说采用的存储结构，当用邻接矩阵存储时，复杂度为O(
)，当用邻接表存储时，时间复杂度为O(n+e).
建图的算法：(邻接表是常考的，邻接矩阵简单，十字链表和 多重表和建邻接表十分的相似)
void CreatGraph (AdjList &g) //建立有n个顶点和m 条边的无向图的邻接表存储结构
{ int n,m;
scanf("%d%d",&n,&m);//输入顶点数和边数
for (i =1,iadjvex=j;
p->next=g.firstarc; g.firstarc=p;//将边结点链入出边链表的头部
p=(ArcNode *)malloc(sizeof(ArcNode)); //因为是无向图所以要在另外一个
p->adjvex=i;
p->next=g.firstarc; g.frstarc=p;// 顶点的出边表中插入该结点
}
}//算法CreatGraph结束
两种求最小生成树的算法(Prim和Kruskal)
Prim算法中有双重循环，外层是求n-1条边内层是在closedge.lowcost
中求最小值和并列的求得当前加入点对closedge[]的影响。所以他的时间复杂度是O(
)，它与途中边的数目没有关系，所以比较适合用在边比较稠密的图中。(顶点数相同，不管边数，都相同)
Kruskal和他相对应，他的时间复杂度为O(eloge)，与图中的结点数目无关，至于边的个数有关。所以适合用在稀疏图中。(边数一定，不管顶点数，复杂度都相同)
求最小生成树的普里姆(Prim)算法中边上的权不可以为负，
typedef struct {
VertexType adjvex;
VRType lowcost;
}closedge;
假设cost(u,w)表示边(u,w)上的权值，则对于集合 V-U 中每个顶点 w，
closedge.lowcost = Min{cost(u,w)|u∈U}
void MiniSpanTree_PRIM( MGraph G, VertexType u,SqList& MSTree)
{
// G 为数组存储表示的连通网，按普里姆算法从顶点 u 出发构
k = LocateVex ( G, u );
for ( j=0; j
if (j!=k) closedge = { u, G.arcs.adj };//{adjvex,lowcost}
closedge.lowcost = 0; // 初始状态，U={u}
for (i=1; i
{ k = minimum(closedge); // 求出T的下一个结点(图中第k顶点)
// 此时closedge.lowcost =
// Min{ closedge.lowcost | closedge.lowcost>0, vi∈V-U }
printf(closedge.adkvex, G.vexs); //输出生成编
closedge.lowcost = 0; // 第 k 顶点并入U集
for (j=0; j
if (G.arcs.adj 拓扑排序问题
Status ToplogicalSort(ALGraph G)
{
FindIndegree(G,indegree);//求各点的入度放在Indegree;
InitStack(S);
for(i=0;i
if(Indegree= =0)
push(S,i);
count=0;
while(!StackEmpty(S))
{ Pop(S,i); printf(i,G.vex.data); ++count;
for(p=G..vex.firstarc; p; p=p->nextarc)
{ k=p->adjvex;
Indegree--;
if( Indegree= =0) push(S,k);
}//for
}//while
if(count
return ERROR;
else
return OK
}
算法分析：求各顶点的入度的时间复杂度为O(e)，入度为零的点入栈O(n)，在循环中，每个顶点进一次栈，出栈一次，入度减1操作在while共执行了e次，所以总的时间复杂度为O(n+e).
当图中无环时，也可以利用深度优先遍历进行拓扑排序，因为图中无环，所以最先退出DFS函数的顶点即出度为零的点，是拓扑排序中最后一个顶点。由此，按DFS函数的先后记录下来的顶点序列即为逆向的拓扑有序序列。
Dijkstra算法
首先引进一个辅助向量, Dist表示当前找到的从源点到vi的最短路径长度。
final为true，即已经求得从v0到v的最短路径。p为true，则w是从v0到v当前求得最短路径上的顶点。该算法弧上的权出现__负数__情况时，不能正确产生最短路径
void ShortestPath_DIJ( MGraph G, int v0,
PathMatrix&p,ShortPathTable& Dist )
{ // 用 Dijkstra 算法求有向网G从源点 u 到其余顶点的最短路径
for (v=0; v
{
final = FALSE; dist = G.arcs;
for(w=0;w
if(dist
}
dist = 0; final = TRUE; // 初始化，顶点 v0 属于S集
for (i=1; i
{
min = INFINITY
for(w=0;w
if(!final) //w在V-S中
if(D
{v=w;min=D;}//w顶点离vo更近
final=true; //离vo最近的v加入S集
for(w=0;w
if(!final&&(min+G.arc
{ D=min+G.arc;
p=p;p=true;//p=p+;
}//if
}//for
} // ShortestPath_DIJ
Floyed算法:
void Floyd (mgraph G, int n) ∥求网G中任意两点间最短路径的Floyd算法∥
{ int i,j,k; int D[ ],path[ ];
∥最短路径长度及最短路径标志矩阵，
即path存放路径(vi…vj)上vi之后继顶点的序号∥
for (i=0;i
for (j=0;j
{ if (G.A
path=j; ∥若∈R,vi当前后继为vj∥
else
path=-1; //否则为-1//
D=G.A;
}
for (k=0;k
for (i=0;i
for (j=0;j
if (D>D+D)
{ D=D+D; ∥取小者∥
Path=path; ∥改vi的后继∥
}
for (i=0;i
for (j=0;j
{ printf (“\n %d”, D); ∥输出vi到vj的最短路径长度∥
k=path; ∥取路径上vi的后继vk∥
if (k==-1)
printf (“%d to %d no path \n”,i,j); ∥vi到vj路径不存在∥
else
{ printf (“(%d”,i); ∥输出vi的序号i∥
while (k!=j) ∥k不等于路径终点j时∥
{ printf (“,%d”,k); ∥输出k∥
k=path; ∥求路径上下一顶点序号∥
}
printf (“%d) \n”,j); ∥输出路径终点序号∥
}
}
}
深度优先搜索遍历(非递归的)
void Traver(AdjList g,vertype v)
//图g以邻接表为存储结构，算法从顶点v开始实现非递归深度优先遍历。
{ struct arc *stack[];
visited=1;
printf(v); //输出顶点v
top=0;
p=g.firstarc;
stack[++top]=p;
while(top>0 || p!=null)
{ while (p)
if (p && visited) p=p->next;
else
{ printf(p->adjvex);
visited=1;
stack[++top]=p;
p=g.firstarc;
}//else
if (top>0) {p=stack; p=p->next; }
}//while
}//算法结束。
以上算法适合连通图，若是非连通图，则再增加一个主调算法,其核心语句是
for (vi=1;viadjvex;
if(visited==1&&finished==0) //如果在v的邻接点中存在vj有访问过
flag=0 ;// 的但vj的邻接点有没有全部访问完的，说明访问v是从vj那里
// 进来的，而现在v和vj有直接的边说明存在回边，
//那么就一定有回路了。(该结论只有在有向图中成立，在无向图中
// 不成立，因为在无向图中vj可能就是v刚刚进来的上一个结点，
//而这时在v中发现Vj也不奇怪，边是双向的，不能作为他是有回
//路的充分条件。而有向图边是单向的)
else if(visited==0)
{ dfs(g,j);
finished=1;
} //if
p=p->next;
}//while
} //dfs结束
2.利用拓扑排序
在拓扑排序中，有一变量count记录访问到的结点数。在算法结束前判断一下
if(count
求图的连通分量的个数
void Count(AdjList g) //求图中连通分量的个数
{ int k=0 ; visited=0;
for (i=1;iadjvex]==0)
dfs(p->adjvex);
p=p->next;
}//while
}// dfs
算法中visited[]数组是全程变量，每个连通分量的顶点集按遍历顺序输出。这里设顶点信息就是顶点编号，否则应取其g.vertex分量输出。
第7章节有关数据结构算法，上文中为大家作了分析，希望考生对于这些算法能够熟记于心，方便考试的应用和日后的实际操作，预祝大家都能够取得好成绩，加油!
页:
[1]