邻接矩阵+邻接表非递归实现 ： 请点这里
#include<stdlib.h> #include<stdio.h> #define MAX 100 #define TRUE 1 #define FALSE 0 typedef struct Stack{ int data; struct Stack * next; }Stack; struct Node// 边表结点 { int adjves;//存储顶点的下标 struct Node* next;//连接下一个邻点 }; typedef struct Node EdgeNode; typedef struct VertexNode//顶点表结点 { int ves;//顶点的值 EdgeNode* firstedge;//相连的顶点的值 }VertexNode,AdjList[MAX]; int ves,edge; //顶点数与边数 typedef struct { AdjList adjlist;//邻接表 int book[MAX];//判断是否有被访问过 }MGraph; Stack* push(Stack * stack,int a){ Stack * line=(Stack*)malloc(sizeof(Stack)); line->data=a; line->next=stack; stack=line; return stack; } Stack * pop(Stack * s){ if (s) { Stack * p=s; s=s->next; free(p); } return s; } int createMGraph(MGraph *G,int a[][2]){ printf("开始创建邻接表\n"); int i,j,k; //k用于记录是否存在未输入的顶点 int start,end,m,n; EdgeNode *e; for(i = 0; i < ves; i++){ G->adjlist[i].ves=a[i][0]; G->adjlist[i].firstedge = NULL; G->book[i]=0; } printf("请输入边(用两个顶点表示,空格分开):\n"); for(i = 0; i < edge; i++){ scanf("%d%d",&m,&n); k=0; for(j=0;j<ves;j++){ if(a[j][1]==m){ start=j; k++; } if(a[j][1]==n){ end=j; k++; } if(j==ves-1&&k<2){ printf("!!!!顶点不存在于顶点表!!!!\n"); return FALSE; } } e =(EdgeNode*)malloc(sizeof(EdgeNode)); e->adjves = start; e->next = G->adjlist[end].firstedge; G->adjlist[end].firstedge = e; e =(EdgeNode*)malloc(sizeof(EdgeNode)); e->adjves = end; e->next = G->adjlist[start].firstedge; G->adjlist[start].firstedge = e; } printf("成功创建邻接表\n"); return TRUE; } void dfs(MGraph *G,int i,int a[][2]){ Stack * s = NULL; EdgeNode *p; G->book[i]=1; s=push(s,a[i][0]); printf("邻接表遍历结果：%d",a[G->adjlist[i].ves][1]); p = G->adjlist[i].firstedge; while(s!=NULL) { p = G->adjlist[s->data].firstedge; while(p){ if(G->book[a[p->adjves][0]] == 0){ G->book[a[p->adjves][0]]=1; printf("%d",a[G->adjlist[p->adjves].ves][1]); s=push(s,a[p->adjves][0]); p = G->adjlist[p->adjves].firstedge; } else p=p->next; } if(p == NULL){ s=pop(s); } } printf("\n"); } void inputVes(int a[][2]){ scanf("%d",&edge); //int a[ves][2]; //a数组本质上是为躲避下面说的的这个bug而设计 printf("请输入各顶点:\n"); //(若为用a[][]处理，为防止程序出错，顶点必须为零开始的递增序列) for(int i = 0; i < ves; i++){ a[i][0]=i; scanf("%d",&a[i][1]); } } int main(){ MGraph G; printf("请输入顶点数与边数(空格分开):\n"); scanf("%d",&ves); int a[ves][2]; inputVes(a); if(createMGraph(&G,a)){ int s; printf("请输入开始结点：\n") ; scanf("%d",&s); for (int i=0;i<ves;i++){ if(s==a[i][1]){ dfs(&G,i,a); break; } } } return 0; }