一、实验目的
1、掌握图的邻接矩阵和邻接表的存储和表示。
2、掌握图的一些基本应用。
3、掌握图的遍历方法。
4、掌握图的最小生成树算法。
5、掌握图的最短路径 Dijkstra 算法。

二、实验内容
1、采用邻接表存储图（要求完成）。
2、输入图并构造邻接矩阵（要求完成）。
3、采用深度优先和广度优先遍历图（要求完成）。

#include <stdio.h> #include <stdlib.h> #define Maxint 10000  //表示极大值 #define MVNum 20      //最大顶点数  typedef struct{     char vexs[MVNum];        //顶点表     int arcs[MVNum][MVNum];  //邻接矩阵     int vexnum, arcnum;      //图的当前点数和边数 }AMGraph;   typedef struct{     int *base;     int front, rear; }Queue;   int visit1[MVNum];  //深度优先遍历辅助数组 int visit2[MVNum];  //广度优先遍历辅助数组   int LocateVex(AMGraph *G, char x) {     int i;     for(i = 0; i < G->vexnum; i++)         if(x == G->vexs[i])             return i;     return -1; }  void CreateUDN(AMGraph *G)  //采用邻接矩阵表示法创建无向网 {     int i, j, k;     char a, b;       printf("Input the vexnum and arcnum:");     scanf("%d %d", &G->vexnum, &G->arcnum);       printf("Input the information of vertexes:n");     for(i = 0; i < G->vexnum; i++)         scanf(" %c", &(G->vexs[i]));       for(i = 0; i < G->vexnum; i++)         for(j = 0; j < G->vexnum; j++)             G->arcs[i][j] = Maxint;          printf("Enter the vertices attached to an edge in turn:n");     for(k = 0; k < G->arcnum; k++ ) {         scanf(" %c,%c", &a, &b);         i = LocateVex(G, a);         j = LocateVex(G, b);         G->arcs[i][j] = 1;         G->arcs[j][i] = 1;     } }  void DFS(AMGraph *G, int a)  //深度优先遍历 {     int i;     printf("%c", G->vexs[a]);     visit1[a] = 1;     for(i = 0; i < G->vexnum; i++) {         if((G->arcs[a][i] != 0) && (!visit1[i]) )             DFS(G,i);     } }  void InitQueue(Queue *Q) {     Q->base = (int*)malloc(20 * sizeof(int));     Q->rear = Q->front = -1; }  void Enqueue(Queue *Q, int i) {     Q->base[Q->rear++] = i; }  int Dequeue(Queue *Q, int i) {     i = Q->base[Q->front++];     return i; }  int Emptyqueue(Queue *Q) {     if (Q->front == Q->rear)         return 1;     else return 0; }  void BFS(AMGraph *G, int a)  //广度优先遍历 {     Queue L;     int i;     InitQueue(&L);     printf("%c", G->vexs[a]);     visit2[a] = 1;     Enqueue(&L, a);     while (!Emptyqueue(&L)) {         a = Dequeue(&L, a);         for (i = 0; i < G->vexnum; i++)         	if (G->arcs[a][i] == 1 && visit2[i] == 0) {             	printf("%c",G->vexs[i]);             	visit2[i] = 1;             	Enqueue(&L, i);         	}     }  }  int main() {     int i;     AMGraph G;     for (i = 0; i < MVNum; i++)  //初始化辅助数组         visit1[i] = 0;     for (i = 0; i < MVNum; i++)         visit2[i] = 0;       CreateUDN(&G);     printf("The result of DFS is:n");     DFS(&G, 0);     printf("n");          printf("The result of BFS is:n");     BFS(&G, 0);     printf("n");     return 0; }