《数据结构与算法》-图的操作

//图的相关操作#include#includetypedef int Dtype;#define MAXVEX 20#defineINFINITY 32768int visited[MAXVEX] = { 0 };//需要一个辅助数组visited来确定已被访问的元素(注： 0号元素不用)typedef struct ArcNode//定义一个邻接表的邻接点结构体变量{int Adjvex;//Adjvex表示数组下标struct ArcNode *next;//指向下一个节点的指针}ArcNode;typedef struct VertexNode//此结构体定义邻接表的数组和指向下一个邻接点的指针{Dtype Adjdata;ArcNode *first;}VertexNode;typedef struct{VertexNode vertex[MAXVEX];int vexnum;//图G中的顶点个数int arcnum;//图G中的边的个数}AdjList;//定义邻接表结构体变量void CreatAdjList(AdjList *G)//创建邻接多表{ArcNode *p;printf("请输入图中顶点的个数：");scanf_s("%d",&G->vexnum);printf("请输入图中的边的个数：");scanf_s("%d",&G->arcnum);G->vertex[0].Adjdata = 0;G->vertex[0].first=NULL;//0号元素不使用，故此处值为零for (int i = 1; i <= G->vexnum; i++) //0号元素不存{printf("请输入第%d个顶点的值：\n",i);scanf_s("%d", &G->vertex[i].Adjdata);//此处的“ %d ”需要指出的是上面定义的数据类型假设为int型；G->vertex[i].first = NULL;//将所有的first指针置空}for (int k = 1; k <= G->arcnum;k++){int i,j;printf("请输入边（vi-vj）的对应的下标值：");scanf_s("%d,%d",&i,&j);p = (ArcNode*)malloc(sizeof(ArcNode));p->Adjvex = j;p->next = G->vertex[i].first;G->vertex[i].first = p;p = (ArcNode*)malloc(sizeof(ArcNode));p->Adjvex = i;p->next = G->vertex[j].first;G->vertex[j].first = p;}}void visit(int v){printf("%d\t", v);}//深度遍历void DFS(AdjList *g, int i){visit(g->vertex[i].Adjdata);visited[i] = 1;ArcNode *p;p = g->vertex[i].first;while (p){if (visited[p->Adjvex] == 0)DFS(g, p->Adjvex);p = p->next;}}//图的深度优先遍历DFS遍历void DFSTraverse(AdjList *g){int i;for (i = 1; i <= g->vexnum; i++)visited[i] = 0;for (i = 1; i <= g->vexnum; i++){if (visited[i] == 0){DFS(g,i);}}}int main(){AdjList G;CreatAdjList(&G);DFSTraverse(&G);}