《数据结构——C语言描述》第7章：图

1、数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 (vertex) ： 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 1 2 3 5 6 8 74 A B D C E 10 7 9 6 6 7 12 3 15 16 60 30 45 35 80 40 75 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 , ),( , , 否否则则 如如果果 0 1 A.Edge EjiEji ji 或者 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图

2、 ),( , , , ),( . ji ji EjiEjijijiW jiEdge = =! n)， int n，e ； lkgraph ； 数据结构C语言描述第7 章：图 void creatqraph（Ikgraph *ga） /*建立无向图的邻接表建立无向图的邻接表*/ int i，j，e，k； pointer p； printf(“请输入顶点数：请输入顶点数：n”)； scanf (“%d”， in; i+) /*读入顶点信息，建立顶点表读入顶点信息，建立顶点表*/ scanf (“ n %c”， p-next = ga-adlistifirst； ga-adlisti.first =

3、 p；/*将新表结点插入到顶点将新表结点插入到顶点vi的边表的头部的边表的头部*/ p = (pointer)malloc(size(struct node)；/*生成邻接点序号为生成邻接点序号为i的表结点的表结点*/ p- vertex = i； p-next = ga-adlistj.first; ga-adlistj.first=p； /*将新表结点插入到顶点将新表结点插入到顶点vj的边表头部的边表头部*/ scanf (“n%d,%dn”， /*假定假定g-vexsi为顶点的编号，然后变访问标志为为顶点的编号，然后变访问标志为1*/ for（j =0；jn；j+） if（g-edges

4、ij = =1）！）！visidj） DFSM（g，j）；）； 数据结构C语言描述第7 章：图 void DFSL（lkgraph *g，int n ）/*邻接表上进行邻接表上进行DFS遍历遍历*/ pointer p; int j； printf（ %dn ，g- adlistn.data）；）； /*访问出发点，输出顶点数据访问出发点，输出顶点数据*/ visidi=1; /*然后变访问标志为然后变访问标志为1*/ for（p = g-adlistn.first；p!=NULL； p = p-next） if（！（！visidp- vertex ） DFSL（g，p- vertex ）；）

5、； 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 void BFS（graph *g，int v）/*v是出发顶点的序号，按广度优先搜索法遍是出发顶点的序号，按广度优先搜索法遍 历图历图g ，采用邻接矩阵存储结构，采用邻接矩阵存储结构，BFS遍历遍历*/ int j，n； seqqueue q；/*假设采用顺序队列，定义顺序队列类型变量假设采用顺序队列，定义顺序队列类型变量q*/ n = g-n； init_seqqueue（q）；）； /*队列初始化队列初始化*/ printf(

6、“访问出发点访问出发点 %d”,v) ；/*访问出发点，假设为输出顶点序号访问出发点，假设为输出顶点序号*/ visidv = 1； /*置访问标志为置访问标志为1，表示此点已访问过，表示此点已访问过*/ en_sqqueue（q，v）；）； /*顶点顶点v入队入队*/ while (!empty_Seqqueue(q) /*队列空否？队列空否？*/ de_ sqqueue（q，v）；）；/*队列非空时，出队队列非空时，出队*/ for（j= l；jadges vj = = l ！visidj） printf(“访问顶点访问顶点%d”，j)；visidj = 1；/*置顶点置顶点j被访问标志被

7、访问标志*/ en_seqqueue(q，j)； /*顶点顶点j入队入队*/ 数据结构C语言描述第7 章：图 void BFSL（graph *g，int v） /*采用邻接表存储结构，采用邻接表存储结构，BFS遍历遍历*/ seqqueue q； /*假设采用顺序队列假设采用顺序队列,定义顺序队列类型变量定义顺序队列类型变量q*/ pointer p； init_seqqueue（q）；）； /*队列初始化队列初始化*/ printf（“访问出发点访问出发点%d”,v）；）； /*访问出发点，假设为输出顶点序号访问出发点，假设为输出顶点序号*/ visidv = 1； /*置访问标志为置访问

8、标志为1，表示此点已访问过，表示此点已访问过*/ en_seqqueue（q，v）；）； /*顶点顶点v入队入队*/ while（！（！empty _seqqueue（q） de_seqqueue（q，v）；）； p = g-adlistvfirst； While（p != NULL） if（! visidp-vertex） printf(%d”，p- vertex)； visidp- vertex = 1； en_ seqqueue (q，p- vertex)； p = p-next ； 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 TRAVER() /* 遍历用邻接矩阵表

9、示的非连通图遍历用邻接矩阵表示的非连通图*/ int i; for ( i = 0; i n; i+) visitedi = FALSE; /* 标志数组初始化标志数组初始化 */ for ( i = 0; i n; i+) if ( !visitedi) DFS(i); /* 从顶点出发遍历一个连从顶点出发遍历一个连 通分量通分量 */ printf( “comp endn”); 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 1 2 3 4 65 5 6 5 1 7 32 54 6 1 2 3 4 65 5 1

10、 32 4 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 PRIMPRIM算法算法 void prim（graph *g，int u） int v，k，j，min； for (v =1；vn；v+) if（v ! = u） m i n e d g e v . e n d = u ； minedgev.len = g-edgesvu； minedgeu.len = 0； for（ k = 1；kn；k+） min = minedgek.len； v = k； for（j =1；jn；j+） if（ minedgej.len0 for (i =1 ; i= e ; i+) if

11、(em i-1.lenmin) min = em i-1.len； return min； 数据结构C语言描述第7 章：图 void kruskal（edqetype em ，int n，int e） /*n为结点数，e为边数*/ int i，p1，p2，m，i0； for（i=1；i= n；i+）/*初始结点为根，无双亲*/ parenti = -1； /*以后用于累计结点个数，此初值不能置为0*/ m = 1； while（mp2） parentp2= parentp1parentp2；/*p2的双亲中累计结点总数（为负值）*/ parentpl= p2； /*p1成为p2的孩子 else

12、 parent p1= parentp1parentp2; parentp2= p1; m+； printf (“%d%d%dn”，m，emi0.v1，em i0.v2 )； 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 源 点 终 点 最 短 路 径路 径 长 度 v0 v1(v0, v1)10 v2 (v0, v1, v2) (v0, v3, v2) 60 50 v3(v0, v3)30 v4(v0, v4)(v0, v3, v4) (v0, v3, v2, v4)100 90 60 数据结构C语言描述第7

13、章：图 10 30 10 20 数据结构C语言描述第7 章：图 void dijkstra（graph *G，int v，int *dist,int *path,char *S） int i,j,k ,pre ，min ； for（i=l;in;i+） si= 0； disti = G-adgesvi； pathi = V； sv = 1； distv = 0； for（i1；in；i+） min=INTMAX； for(j=1;jn；j+) if (！sj k=j; if(min = = INTMAX) break; Sk=1； for（jl；jn；j+） if（！sj for（i=1；in

14、；i+） printf(“顶点%d的最短路径为：%dn”， i， disti)； Prepathi； do printf(“- %d”, pre)； pre = pathpre； while（pre！= v）； if(disti= =INTMAX)printf(” 无路径n”)； 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 0 jiCjiA ,min 1 jkAkiAjiAjiA kkkk 数据结构C语言描述第7 章：图 void floyd（graph *G） int i，j，k，next； for ( i=

15、1；in；i+) for（j1；jn；j+） Aij = G-adgesij； pathij= 0； for（k=1;kn;k+） for( i=1；in ；i+) for（j= l；jn；j+） if（AikAkj Aij） AijAikAkj； pathij= k； for（i1；in；i+） for（j= 1；jn；j+） printf（” 顶点顶点%d路径长度路径长度%d”， i， Aij）；）； next pathij； printf(“路径为：路径为：%d”，i )； do printf（” %d”， next）；）； next=pathnextj ； while（next！= j

16、）；）； if (Aij = = INTMAX) printf（“无路径无路径n”）；）； 数据结构C语言描述第7 章：图 50 10 30 10 20 60 100 数据结构C语言描述第7 章：图 0 60020 100 500 10030100 A0 0 60020 100 500 1003060100 A2 0 30020 100 60500 1003060100 A3 0 30020 100 60500 1003050100 A4 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 学生课程学习工程图学生课程学习工程图 数据结构C语言描述第7

17、 章：图 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 abcdef 数据结构C语言描述第7 章：图 v10 v22null v31 v42 v53null v60 。 。 。 。 12 34 56 出边表出边表 数据结构C语言描述第7 章：图 数据结构C语言描述第7 章：图 拓扑排序算法拓扑排序算法 int topsort（Ikgraph *g） lkstack s； pointer p； int m，i，v； init_lkstack（s）；）； for (i =1；in；i+) if（g-adlisti.id = = 0） push_lkstack（s，i ）；）； m0； wh