数据结构笔记-图

图的基本操作

CreatGraph(G):输入图G的顶点和边，建立图G的存储DFSTraverse(G,v):在图G中，从顶点v出发 深度优先遍历图GBFSTraverse(G,v):在图G中，从顶点v出发 广度优先遍历图G

图的存储

1.邻接链表

1 if （vi,vj）或<vi,vj> 是E(G)中的边 Adj[i][j] = 0 if （vi,vj）或<vi,vj> 不是E(G)中的边 G 若是网(有权)，则可定义为： wij(vi到vj路径上的权重) if （vi,vj）或<vi,vj> 是E(G)中的边 Adj[i][j] = 0或无穷(表示无权) if （vi,vj）或<vi,vj> 不是E(G)中的边 **(A,A) 即自己指向自己 值为0或无穷 #define maxlen 100 typedef struct { char vexs[maxlen]; int edges[maxlen][maxlen]; int n,e; }MGraph; void CreateMGraph(Mgraph &G) { int i,j,k; char ch1,ch2; printf("intput the number of vexs and edges\n"); scanf("%d %d",&(G.n),&(G.e)); for(i = 0 ;i<G.n;i++) { fflush(stdin); scanf("%c",&(G.vexs[i])); } for(i=0;i<G.n;i++) for(j=0;j<G.n;j++) G.e[i][j] = 0; printf("input the edges :\n"); for(k=0;k<G.e;k++) { fflush(stdin); printf("请输入第%d条边的两个顶点标志:",k+1); sacnf("%c,%c",&ch1,&ch2); for(i = 0; ch1 != G.vexs[i];i++) for(j=0;ch2 != G.vexs[j];j++) G.edges[i][j] = 1; } }

2.邻接表