计算机考研：数据结构常用算法精析（7）

第七章：

对于无向图，e的范围是：

数据结构中所讨论的图都是简单图，任意两结点间不会有双重的边。

对于有向图，e的范围是：

图的各种存储结构

邻接矩阵很方便访问任意两点的边，但是不方便计算其邻接点。在深度和广度遍历中广泛的需要求某点的邻接点。所以邻接矩阵只在Floyed和Prim和Dijstra中采用。

邻接表能很方便的求某顶点的邻接点，索引对于与遍历有关的算法大多都采用邻接表。如深度、广度、拓扑排序、关键路径。但他也有不足的地方，就是不方便求入度或是那些点可以到他的操作。所以有人引进逆邻接表。最后人们把这两种表结合到一起就是十字链表和邻接多重表。一个是存储有向图，另一个是存储无向图。

在十字链表和邻接多重表很方便求邻接点的操作和对应的逆操作。所以实际应用中，凡是能用邻接表实现的一定能用十字链表和邻接多重表实现。并且它们的存储效率更高。

1.邻接矩阵(有向图和无向图和网)又称为数组表示法

typedef struct

{ vextype vexs[maxn]; ∥顶点存储空间∥

adjtype A[maxn][maxn]; ∥邻接矩阵∥

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[maxn]; ∥顶点表∥

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%dn,//输入顶点数和边数

for (i =1,ii++)//输入顶点信息,建立顶点向量

{ scanf(g[i].vertex);

g[i].firstarc=null;

}

for (k=1;kk++)//输入边信息

{ scanf(v1,//输入两个顶点

i= LocateVertex (g,v1); j=GraphLocateVertex (g,v2); //顶点定位

p=(ArcNode *)malloc(sizeof(ArcNode));//申请边结点

p-adjvex=j;

p-next=g[i].firstarc; g[i].firstarc=p;//将边结点链入出边链表的头部

p=(ArcNode *)malloc(sizeof(ArcNode)); //因为是无向图所以要在另外一个

p-adjvex=i;

p-next=g[j].firstarc; g[j].frstarc=p;// 顶点的出边表中插入该结点

}

}//算法CreatGraph结束

两种求最小生成树的算法(Prim和Kruskal)

Prim算法中有双重循环，外层是求n-1条边内层是在closedge[v].lowcost 中求最小值和并列的求得当前加入点对closedge[]的影响。所以他的时间复杂度是O( )，它与途中边的数目没有关系，所以比较适合用在边比较稠密的图中。(顶点数相同，不管边数，都相同)

Kruskal和他相对应，他的时间复杂度为O(eloge)，与图中的结点数目无关，至于边的个数有关。所以适合用在稀疏图中。(边数一定，不管顶点数，复杂度都相同)

求最小生成树的普里姆(Prim)算法中边上的权不可以为负，

typedef struct {

VertexType adjvex;

VRType lowcost;

}closedge[MAX_VERTEX_NUM];

假设cost(u,w)表示边(u,w)上的权值，则对于集合 V-U 中每个顶点 w，

closedge[LocateVex(G, w)].lowcost = Min{cost(u,w)|uU}

void MiniSpanTree_PRIM( MGraph G, VertexType u,SqList MSTree)

{

// G 为数组存储表示的连通网，按普里姆算法从顶点 u 出发构

k = LocateVex ( G, u );

for ( j=0; j

if (j!=k) closedge[j] = { u, G.arcs[k][j].adj };//{adjvex,lowcost}

closedge[k].lowcost = 0; 　　　 // 初始状态，U={u}

for (i=1; i

{　 k = minimum(closedge);　　　　// 求出T的下一个结点(图中第k顶点)

// 此时closedge[k].lowcost =

// Min{ closedge[vi].lowcost | closedge[vi].lowcost0, viV-U }

printf(closedge[k].adkvex, G.vexs[k]); //输出生成编

closedge[k].lowcost = 0; 　　　// 第 k 顶点并入U集

for (j=0; j

if (G.arcs[k][j].adj closedge[j].lowcost) //新顶点并入U后重新选最小边

closedge[j] = { G.vexs[k], G.arcs[k][j].adj };

} // for

} // MiniSpanTree

拓扑排序问题

Status ToplogicalSort(ALGraph G)

{

FindIndegree(G,indegree);//求各点的入度放在Indegree[vnum];

InitStack(S);

for(i=0;i

if(Indegree[i]= =0)

push(S,i);

count=0;

while(!StackEmpty(S))

{ Pop(S,i); printf(i,G.vex[i].data); ++count;

for(p=G..vex[i].firstarc; p; p=p-nextarc)

{ k=p-

Indegree[k]--;

if( Indegree[k]= =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[i]表示当前找到的从源点到vi的最短路径长度。

final[v]为true，即已经求得从v0到v的最短路径。p[v][w]为true，则w是从v0到v当前求得最短路径上的顶点。该算法弧上的权出现__负数__情况时，不能正确产生最短路径

void ShortestPath_DIJ( MGraph G, int v0, PathMatrixp,ShortPathTable Dist )

{　// 用 Dijkstra 算法求有向网G从源点 u 到其余顶点的最短路径

for (v=0; v

{

final[v] = FALSE; dist[v] = G.arcs[v0][v];

for(w=0;w

if(dist[v]

}

dist[v0] = 0; final[v0] = TRUE; // 初始化，顶点 v0 属于S集

for (i=1; i

{

min = INFINITY

for(w=0;w

if(!final[w]) //w在V-S中

if(D[w]

{v=w;min=D[w];}//w顶点离vo更近

final[v]=true; //离vo最近的v加入S集

for(w=0;w

if(!final[w](min+G.arc[v][w]

{ D[w]=min+G.arc[v][w];

p[w]=p[v];p[w][w]=true;//p[w]=p[v]+[w];

}//if

}//for

} // ShortestPath_DIJ

Floyed算法:

void Floyd (mgraph G, int n) ∥求网G中任意两点间最短路径的Floyd算法∥

{ int i,j,k; int D[ ][n],path[ ][n];

∥最短路径长度及最短路径标志矩阵，

即path[i][j]存放路径(vivj)上vi之后继顶点的序号∥

for (i=0;i

for (j=0;j

{ if (G.A[i][j]

path[i][j]=j; ∥若R,vi当前后继为vj∥

else

path[i][j]=-1; //否则为-1//

D[i][j]=G.A[i][j];

}

for (k=0;k

for (i=0;i

for (j=0;j

if (D[i][j]D[i][k]+D[k][j])

{ D[i][j]=D[i][k]+D[k][j]; ∥取小者∥

Path[i][j]=path[i][k]; ∥改vi的后继∥

}

for (i=0;i

for (j=0;j

{ printf (n %d, D[i][j]); ∥输出vi到vj的最短路径长度∥

k=path[i][j]; ∥取路径上vi的后继vk∥

if (k==-1)

printf (%d to %d no path n,i,j); ∥vi到vj路径不存在∥

else

{ printf ((%d ∥输出vi的序号i∥

while (k!=j) ∥k不等于路径终点j时∥

{ printf (,%d ∥输出k∥

k=path[k][j]; ∥求路径上下一顶点序号∥

}

printf (%d) n ∥输出路径终点序号∥

}

}

}

深度优先搜索遍历(非递归的)

void Traver(AdjList g,vertype v)

//图g以邻接表为存储结构，算法从顶点v开始实现非递归深度优先遍历。

{ struct arc *stack[];

visited[v]=1;

printf(v); //输出顶点v

top=0;

p=g[v].firstarc;

stack[++top]=p;

while(top0 || p!=null)

{ while (p)

if (p visited[p-adjvex]) p=p-

else

{ printf(p-

visited[p-adjvex]=1;

stack[++top]=p;

p=g[p-adjvex].firstarc;

}//else

if (top0) {p=stack[top--]; p=p- }

}//while

}//算法结束。

以上算法适合连通图，若是非连通图，则再增加一个主调算法,其核心语句是

for (vi=1;vivi++)

if(!visited[vi])

Traver(g,vi);

判断回路问题：(通常有向图的回路问题，无向图的回路比较繁琐)

两种判断有向图中有回路主要方法：

1：利用深度优先遍历

int visited[]=0; finished[]=0; //finished[i]=1表示i结点的所有邻接点都访问完了

int flag=0;//回路的标记。有回路时值为1

int DFS-travor(Adjlist g)

{ i=1;

while(flag==0i=n)

if(visited[i]==0)

{ dfs(g,i);

finished[i]=1;

}//if

}//总控程序，如果图有多个连通分量，分别进入每个连通分量

void dfs(AdjList g,vertype v)

//以顶点v开始深度优先遍历有向图g，顶点信息就是顶点编号.

{

printf(%d visited[v]=1;

p=g[v].firstarc;

while(p!=null) //访问v的所有邻接点

{ j=p-

if(visited[j]==1finished[j]==0) //如果在v的邻接点中存在vj有访问过

flag=0 ;// 的但vj的邻接点有没有全部访问完的，说明访问v是从vj那里

// 进来的，而现在v和vj有直接的边说明存在回边，

//那么就一定有回路了。(该结论只有在有向图中成立，在无向图中

// 不成立，因为在无向图中vj可能就是v刚刚进来的上一个结点，

//而这时在v中发现Vj也不奇怪，边是双向的，不能作为他是有回

//路的充分条件。而有向图边是单向的)

else if(visited[j]==0)

{ dfs(g,j);

finished[j]=1;

} //if

p=p-

}//while

} //dfs结束

2.利用拓扑排序

在拓扑排序中，有一变量count记录访问到的结点数。在算法结束前判断一下

if(count

求图的连通分量的个数

void Count(AdjList g) //求图中连通分量的个数

{ int k=0 ; visited[1...n]=0;

for (i=1;i=g.vexnum;i++ )

if (visited[i]==0)

{ printf (第%d个连通分量:n

dfs(i);

}//if

}//Count

void dfs(AdjList g,vextype v)

{ visited[v]=1;

printf ( %3d //输出连通分量的顶点。

p=g[v].firstarc;

while (p!=null)

{

if(visited[p-adjvex]==0)

dfs(p-

p=p-

}//while

}// dfs

算法中visited[]数组是全程变量，每个连通分量的顶点集按遍历顺序输出。这里设顶点信息就是顶点编号，否则应取其g[i].vertex分量输出。

第7章节有关数据结构算法，上文中为大家作了分析，希望考生对于这些算法能够熟记于心，方便考试的应用和日后的实际操作，预祝大家都能够取得好成绩，加油!