1.基于邻接矩阵的BFS（广搜）
typedef struct arcnode//数据关系结构 { int adj; //对于无权图(int)，用1或0表示相邻否；对带权图，则为权值类型。 char *info;//弧相关信息指针 } arcnode, adjmatrix[100][100]; //邻接矩阵 typedef struct//图结构 { char vexs[100];//顶点向量 adjmatrix a; //邻接矩阵 int vexnum;//顶点数 int arcnum;//弧数（边数） } MG; int k;//初始点 status create(MG &g)//数组表示法构造无向图 { scanf("%d %d %d", &g.vexnum, &g.arcnum, &k); for(i=0; i<g.vexnum; i++) // 初始化邻接矩阵 for(j=0; j<g.vexnum; j++) { g.a[i][j].adj = INF; g.a[i][j].info = NULL; } for(k=0; k<g.arcnum; k++)//构造邻接矩阵 { scanf("%d %d %d", &v1, &v2, &w); // 输入一条边依附的顶点及权值 i = LocateVex(G, v1); j = LocateVex(G, v2); // 确定v1和v2在G中位置 (若从零开始则不必要) g.a[i][j].adj = w; g.a[j][i].adj = g.a[i][j].adj;//无向图的对称性 } return 1; } int v[110];//标记数组 void bfs(MG &g, int k) { for(i=0; i<g.vexnum; i++) v[i] = 0; v[k] = 1; q.push(k); //起始结点入队 printf("%d", k); while(!q.empty()) { i = q.front(); q.pop(); for(j=0; j<g.vexnum; j++)//依次搜索vi的邻接点vj { if(g.a[i][j].adj == 1 && !v[j]) { v[j] = 1; q.push(j); printf(" %d", j); } } } } 2.基于邻接表的BFS（广搜） typedef struct arcnode//表结点结构 { int adj; //该弧所指向的顶点的位置 struct arcnode *next;//指向下一条弧的指针 infotype *info; //该弧相关信息的指针(如权值) } arcnode; typedef struct vnode//头结点结构 { int data;//顶点信息 arcnode *first;//指向第一条依附该顶点的弧的指针 } vnode, adjlist[MAX]; typedef struct//图的结构 { adjlist a; int vn, an;//图的当前顶点数和弧数 } ALG; status create(ALG &g) { scanf("%d %d %d", &g.vn, &g.an, &k); for(i=0; i<vn; i++) { g.a[i].first = NULL; } for(i=0; i<g.an; i++) { scanf("%d %d %d", &v1, &v2, &w); p = new arcnode; p->adj = v2; p->info = w; p->next = g.a[v1].first; //逆序建立链表 g.a[v1].first = p; //无向图的对称性 p = new arcnode; p->adj = v1; p->info = w; p->next = g.a[v2].first; g.a[v2].first = p; } return 1; } int v[MAX]; void bfs(ALG &g, int k) { arcnode *p; memset(v, 0, sizeof(v)); v[k] = 1; q.push(k); printf("%d", k); while(!q.empty()) { i = q.front(); q.pop(); p = g.a[i].first; { while(p)//依次搜索vi的邻接点vj(p->adj相当于j) { if(!v[p->adj]) { v[p->adj] = 1; q.push(p->adj); printf(" %d", p->adj); } p = p->next; } } } }3.基于邻接矩阵的DFS（深搜）
void dfs(MG &g, int k) { int j; printf("%d", k); v[k] = 1; for(j=0; j<g.vn; j++) if(g.a[k][j].adj == 1&&!v[j]) dfs(g, j); }