2015考研:计算机数据结构常用算法(七)？
对于无向图，e的范围是:
数据结构中讨论的图都是简单图，任何两个节点之间都不会有双边。
对于有向图，e的范围是:
图的各种存储结构
邻接矩阵方便访问任意两点的边，但不方便计算其邻接点。在深度和广度遍历中，广泛需要要求某一点的相邻点。所以邻接矩阵只在Floyed和Prim和Dijstra中使用。
邻接表可以很容易的找到一个顶点的邻接点，索引对于遍历相关的算法大多使用邻接表。例如深度、宽度、拓扑排序和关键路径。但是他也有一些缺点，就是不方便进去或者那些点可以供他操作。于是有人引入了反向邻接表。最后，人们将这两种表结合在一起，即交叉链表和相邻多表。一种是存储有向图，另一种是存储无向图。
在交叉链表和相邻多表中查找相邻点和对应的逆运算非常方便。所以在实际应用中，凡是邻接表能实现的，一定要用交叉链表和邻接多重表来实现。并且它们的存储效率更高。
1.邻接矩阵(有向图和无向图和网)也称为数组表示。
typedef结构
{ vextype vexs[maxn]；∨顶点存储空间∨
adj type A[maxn][maxn]；∑邻接矩阵∧
int vexnum，arcnum//图形的顶点数和边数
GraphKind类；//图形的类型
} mgraph
2.邻接表(有向图和无向图和网络)
Typedef结构节点edge
{ int adjint w；∑邻接点和权值
结构节点* next指向下一个弧或边
} linknode
Typedef结构∨顶点类型∨
{ vtype数据；∑顶点范围
linknode * farc∑指向与该顶点相关联的第一条弧或边
} Vnode
typedef结构
{
vnode G[maxn]；∨顶点表∨
int vexnum，arcnum
GraphKind类；
} ALGraph
adjvexnextarcinfo
边缘节点
数据firstarc
顶点节点
3.交叉链表(有向图和有向网络)
headvextaivexhlinktlinkinfo
边缘节点
datafirstinfirstout
顶点节点
4.邻接多表(无向图)
markivexjvexilinkjlinkinfo
边缘节点
数据边缘
顶点节点
有向无环图(DAG):是用公共子表达式描述表达式的有效工具。二叉树也可以表示表达式，但是使用有向无环图可以实现同一个子公式的共享，从而节省存储空间。
顶点度数:
无向图:一个顶点V的度数为D(V)，表示与V关联的边数。
有向图:顶点V的度d(V)= ID(V)+OD(V)
强连通分支:在有向图中，如果图中任意两个顶点之间有一条路，则称为强连通图。图中的最大强连通子图称为强连通分量。
这里的“Maxim”是指如果在一个连通分支上加上顶点和边，就不能形成原图中的一个连通子图，即该连通分支是一个集合最大的连通子图。有向图的连通性意味着有向图是
强连通的
遍历图的过程本质上是为每个顶点寻找其邻点的过程，其耗时主要取决于所采用的存储结构。图用邻接矩阵存储时，求每个顶点的邻接点需要时间o()，其中n是图中顶点的个数。用邻接表存储图时，求邻接点所需时间为O(e)，其中e是图中边或有向弧的个数。因此，当采用邻接表作为存储结构时，首先对遍历图的时间复杂度O(n+e)进行深度搜索。
广度优先搜索遍历图和深度优先搜索遍历图的时间复杂度是一样的，两者唯一的区别是访问节点的顺序不同。也就是说，它们的时间复杂度取决于所采用的存储结构。用邻接矩阵存储时，复杂度为O()，用邻接表存储时，时间复杂度为O(n+e)。
建图算法:(邻接表常考，邻接矩阵简单，交叉链表和多重表很像建邻接表)
void creat graph(adj list & amp；G) //建立n个顶点m条边的无向图的邻接表存储结构。
{ int n，m；
scanf("%d%d "，& ampn & amp；m)；//输入顶点和边的数量。
for (i =1，i & lt= n；I++)//输入顶点信息，建立顶点向量。
scanf(& amp；g[i]。顶点)；
g[i]。firstarc = null
}
for(k = 1；k & lt= m；K++)//输入边信息
scanf(& amp；v1。v2)；//输入两个顶点。
i= LocateVertex (g，v 1)；j=GraphLocateVertex (g，v2)；//顶点定位
p =(ArcNode *)malloc(sizeof(ArcNode))；//申请一个边缘节点
p->；adj vex = j；
p->；next=g[i]。firstarcg[i]。first arc = p；//将边缘节点链接到边缘列表的头部。
p =(ArcNode *)malloc(sizeof(ArcNode))；//因为是无向图，所以应该在另一个里面。
p->；adj vex = I；
p->；next=g[j]。firstarcg[j]。frstarc = p；//将节点插入顶点的边表中。
}
}//算法CreatGraph结束
求最小生成树的两种算法(Prim和Kruskal)
Prim算法有一个双循环，外层是寻找n-1条边，内层是寻找closedge[v]中的最小值。lowcost和当前添加点对closedge[]的影响是并行发现的。所以它的时间复杂度是O()，与途中边数无关，所以更适合边密集的图。(无论边的数量是多少，顶点的数量都是相同的。)
Kruskal对应他，他的时间复杂度是O(eloge)，与图的节点数无关，而与边数有关。因此它适用于稀疏图。(边的数量是固定的，不管顶点的数量是多少，复杂度都是一样的)
在寻找最小生成树的Prim算法中，边的权重不能为负，
typedef结构{
顶点类型adjvex
VRType低成本；
} closedge[MAX _ VERTEX _ NUM]；
假设cost(u，w)表示边(U，w)上的权重，对于集合V-U中的每个顶点w，
closedge[LocateVex(G，w)]。低成本=最小{成本(U，w)|u∈U}
void MiniSpanTree_PRIM( MGraph G，VertexType u，SqList & ampMSTree)
{
// G是用数组存储表示的连通网络，由顶点U按照prim算法构造。
k = LocateVex ( G，u)；
for(j = 0；j
如果(j！=k) closedge[j] = { u，G.arcs[k][j]。adj }；//{adjvex，lowcost}
克洛斯奇[k]。低成本= 0；//初始状态，U={u}
for(I = 1；我
{ k =最小值(close dge)；//找到T的下一个节点(图中第k个顶点)
//此时closedge[k]。低成本=
// Min{ closedge[vi]。低成本的。低成本& gt0，vi∈V-U }
printf(closedge[k]。adkvex，g . vexs[k])；//输出生成编辑器
克洛斯奇[k]。低成本= 0；//第k个顶点合并到U集中。
for(j = 0；j
if (G.arcs[k][j].adj & lt克洛斯奇[j]。lowcost) //将新顶点合并到u后重新选择最小的边。
closedge[j] = { G.vexs[k]，G.arcs[k][j]。adj }；
} // for
} // MiniSpanTree
拓扑排序问题
状态ToplogicalSort(代数G)
{
FindIndegree(G，in degree)；//求指数中各点的渗透率[vnum]；
InitStack
for(I = 0；我
if(Indegree[i]= =0)
推(S，I)；
count = 0；
而(！栈顶)
{ Pop(S，I)；printf(i，G.vex[i]。数据)；++计数；
for(p=G..使烦恼。firstarcp；p = p-& gt；nextarc)
{ k = p-& gt；adjvex
in degree[k]-；
if( Indegree[k]= =0) push(S，k)；
}//for
}//当
如果(计数
返回错误；
其他
返回OK
}
算法分析:求每个顶点的贯穿度的时间复杂度为O(e)，贯穿度为零的点进入栈O(n)。在循环中，每个顶点入栈一次，出栈一次，在while***中执行1减少渗透的操作e次，所以总时间复杂度为O(n+e)。
当图中没有圈时，深度优先遍历也可以用于拓扑排序。因为图中没有圈，所以最先退出DFS函数的顶点，也就是度数为零的点，就是拓扑排序中的最后一个顶点。所以按照DFS函数的顺序记录的顶点序列就是逆拓扑有序序列。
如果你对考研有疑问，不知道考研中心的内容怎么总结，不了解考研报名的地方政策，点击最下方咨询官网，免费获取复习资料:/xl/