2015考研：计算机数据结构常用算法（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%d",&n,&m);//输入顶点数和边数
for (i =1,i<=n;i++)//输入顶点信息,建立顶点向量
{ scanf(&g[i].vertex);
g[i].firstarc=null;
}
for (k=1;k<=m;k++)//输入边信息
{ scanf(&v1,&v2);//输入两个顶点
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)|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[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].lowcost>0, vi∈V-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->adjvex;
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函数的先后记录下来的顶点序列即为逆向的拓扑有序序列。
考研有疑问、不知道如何总结考研考点内容、不清楚考研报名当地政策，点击底部咨询官网，免费领取复习资料：https://www.87dh.com/xl/
绛旓細渚嬪锛欵xp=a*b+(c-d/e)*f 鑻 Exp=a*b+(c-d/e)*f 銆鍒欏畠鐨 鍓嶇紑寮忎负锛 +*ab*-c/def 涓紑寮忎负锛 a*b+c-d/e*f 鍚庣紑寮忎负锛 ab*cde/-fx+ 缁煎悎姣旇緝瀹冧滑涔嬮棿鐨勫叧绯诲彲寰椾笅鍒楃粨璁猴細1.涓夊紡涓殑 鈥滄搷浣滄暟涔嬮棿鐨勭浉瀵规搴忕浉鍚屸;(浜屽弶鏍戠殑涓夌璁块棶娆″簭涓紝鍙跺瓙鐨勭浉瀵硅闂搴忔槸鐩稿悓鐨)...
绛旓細骞垮害浼樺厛鎼滅储閬嶅巻鍥剧殑鏃堕棿澶嶆潅搴﹀拰娣卞害浼樺厛鎼滅储閬嶅巻鐩稿悓锛屼袱鑰呯殑涓嶅悓涔嬪浠呭湪浜庡缁撶偣璁块棶鐨勯『搴忎笉鍚屻備篃灏辨槸璇翠粬浠殑鏃堕棿澶嶆潅搴﹂兘鍙栧喅浜庤閲囩敤鐨勫瓨鍌缁撴瀯锛屽綋鐢ㄩ偦鎺ョ煩闃靛瓨鍌ㄦ椂锛屽鏉傚害涓篛( )锛屽綋鐢ㄩ偦鎺ヨ〃瀛樺偍鏃讹紝鏃堕棿澶嶆潅搴︿负O(n+e).寤哄浘鐨勭畻娉曪細(閭绘帴琛ㄦ槸甯歌冪殑锛岄偦鎺ョ煩闃电畝鍗曪紝鍗佸瓧閾捐〃鍜 澶氶噸...
绛旓細A鏄疊鐨勫厖鍒嗘潯浠 = 濡傛灉A鐪燂紝鍒橞鐪 = (閫氬父琛ㄨ堪涓)鏈堿涓瀹氭湁B A鏄疊鐨勫繀瑕佹潯浠 = 濡傛灉A鍋囷紝鍒橞鍋 =(閫氬父琛ㄨ堪涓)鏃燗涓瀹氭棤B 濡傛灉A鏄疊鐨勫厖鍒嗘潯浠讹紝鍒橞鏄疉鐨勫繀瑕佹潯浠躲傚弽涔嬩害鐒躲傗槅 鏉′欢鍏崇郴鐨勫洓绉嶆儏鍐碉細1.鍏呭垎浣嗕笉蹇呰 2. 蹇呰浣嗕笉鍏呭垎 3.鍏呭垎蹇呰 4.涓嶆瀯鎴愭潯浠跺叧绯 鈽 鏉′欢鍏崇郴鐨勬棩...
绛旓細璁句富涓睸[]鍜屾ā寮忎覆T[],濡傛瘮杈冨埌妯″紡涓茬殑绗琷涓瓧绗︺ 褰撲富涓叉寚閽坕鍜屾ā寮忎覆鎸囬拡j姣旇緝鏃 锛岃鏄庝粬浠墠闈㈢殑鎵鏈夊瓧绗﹂兘宸茬粡瀵瑰簲鐩哥瓑浜嗐傝 Next[j]=k鐨勫畾涔夋槸T1T2鈥k-1==Tj-k+1Tj-k+2鈥.Tj-1涓攌鏄渶澶т簡锛屾病鏈夋洿闀跨殑浜嗐傛墍浠i鍜孴j姣旇緝澶辫触鏃禨i鍜孴k鍘绘瘮杈冦備笉鍙兘鏈 杩欑鍖归厤鐨勬垚鍔燂紝...
绛旓細銆愭枃浠舵帶鍒跺潡(fcb)銆戞枃浠舵帶鍒跺潡鏄搷浣滅郴缁熶负绠＄悊鏂囦欢鑰岃缃殑鏁版嵁缁撴瀯锛屽瓨鏀句簡涓虹鐞嗘枃浠舵墍闇鐨勬墍鏈夋湁鍏充俊鎭傛枃浠舵帶鍒跺潡鏄枃浠跺瓨鍦ㄧ殑鏍囧織銆傘愪綔涓氭銆戜竴鑸儏鍐典笅锛屼竴涓綔涓氬彲鍒掑垎鎴愯嫢骞蹭釜閮ㄥ垎锛屾瘡涓儴鍒嗙О涓轰竴涓綔涓氭銆傚湪浣滀笟杩愯鏈熼棿锛屽悇浣滀笟姝ヤ箣闂村瓨鍦ㄧ潃鐩镐簰鑱旂郴锛屽線寰涓婁竴涓綔涓氭鐨勭粨鏋滀綔涓轰笅涓涓...
绛旓細璁＄畻鏈瀛︾涓撲笟鍩虹缁煎悎锛屽嵎闈㈡弧鍒嗗间负150鍒嗭紝鐢卞叏鍥界粺涓缁勭粐鍛介锛岄槄鍗风敱鐪佺骇鎷涚敓鑰冭瘯鏈烘瀯缁熶竴缁勭粐銆傝绠楁満瀛︾涓撲笟鍩虹鐨勮冭瘯鍐呭鍖呮嫭锛氭暟鎹粨鏋銆佽绠楁満缁勬垚鍘熺悊銆佹搷浣滅郴缁熷拰璁＄畻鏈虹綉缁滐紝閲嶇偣鑰冩煡鑰冪敓鐨勫熀纭鐭ヨ瘑銆佸熀鏈悊璁哄拰鍒嗘瀽闂瑙ｅ喅闂鐨勮兘鍔涳紝鑰冭瘯鍐呭鍙婄粨鏋勫湪澶х翰涓‘瀹氥傝冭瘯鍐呭鍜岃瘯鍗风粨鏋 (1)璇曞嵎婊″垎...
绛旓細鏁版嵁缁撴瀯鍦璁＄畻鏈绉戝涓捣鐫鍏抽敭浣滅敤锛屽畠娑夊強閫昏緫缁撴瀯銆佸瓨鍌ㄧ粨鏋勫拰鏁版嵁杩愮畻銆傞昏緫缁撴瀯鍖呮嫭绾挎х粨鏋勶紙濡傜嚎鎬ц〃銆佹爤鍜岄槦鍒楋級鍜岄潪绾挎х粨鏋勶紙濡傞泦鍚堛佹爲褰㈢粨鏋勫拰鍥剧姸缁撴瀯锛夈傞『搴忓瓨鍌ㄩ珮鏁堟敮鎸侀殢鏈鸿闂紝鑰岄摼寮忓瓨鍌ㄥ垯涓嶆敮鎸侊紝浣嗗埄浜庡姩鎬佸鍒犮傞『搴忚〃涓庨摼琛ㄧ殑鍖哄埆鏄捐憲锛岄『搴忚〃鍏佽闅忔満璁块棶锛屽瓨鍌ㄥ瘑搴﹂珮锛屼絾鎻掑叆鍒犻櫎...
绛旓細2022璁＄畻鏈408鑰冪爺SVIP 閾炬帴: https://pan.baidu.com/s/1cfy-wcYk0StC98VBOmjHYQ 鎻愬彇鐮: 2us6 澶嶅埗杩欐鍐呭鍚庢墦寮鐧惧害缃戠洏鎵嬫満App锛屾搷浣滄洿鏂逛究鍝 鑻ヨ祫婧愭湁闂娆㈣繋杩介棶~
绛旓細2銆璁＄畻鏈涓撲笟澶囪冨涔犵殑涓変釜闃舵 绗竴闃舵鏄涔犮佹墦濂藉熀纭鐨勯樁娈点傛椂闂翠竴鑸粠3鏈堜唤寮濮嬪埌7鏈堜唤宸﹀彸銆傝繖涓闃舵閫夌敤鐨勫涔犺祫鏂欎富瑕佹槸鍜屽ぇ绾叉瘮杈冨惢鍚堢殑鏁欐潗浠ュ強閰嶅鐨勪範棰樸傜洰鍓嶆潵璇达紝鏁欐潗宸茬粡鍩烘湰缁熶竴銆鏁版嵁缁撴瀯閫夌敤涓ヨ敋鏁忎富缂栥佹竻鍗庡ぇ瀛﹀嚭鐗堢ぞ鍑虹増鐨凜璇█鐗堢殑銆婃暟鎹粨鏋勩嬶紝涔犻寤鸿閫夌敤鏉庢槬钁嗕富缂栥佹竻鍗庡ぇ瀛...
绛旓細涓銆佷互澶х翰涓哄熀鍑嗭紝鍑嗙‘鎶婃彙澶嶄範瑕佺偣 璁＄畻鏈涓撲笟璇剧殑缁熻冨ぇ绾叉槸鏈鍏锋潈濞佹х殑鎸囧悜鏍囷紝鑰冭瘯澶х翰瀵硅冩煡鑼冨洿銆佽冩煡鐩爣鐨勮瀹氭槸鍚屽浠‘瀹氬涔犺寖鍥翠互鍙婂涔犱晶閲嶇偣鐨勯噸瑕佷緷鎹傝鐪熺爺绌惰冪翰涓叧浜鏁版嵁缁撴瀯銆佽绠楁満缁勬垚鍘熺悊銆佹搷浣滅郴缁熴佽绠楁満缃戠粶鍥涘ぇ閮ㄥ垎鐨勫垎鍊笺佽冪偣銆佽冩煡瑕佹眰鏂归潰鐨勪俊鎭紝鍒欏彲鎹鏄庣‘澶嶄範杩囩▼涓殑...
