深度优先遍历,这个跟树中的遍历类似,做深度遍历就是访问一个节点之后,在访问这个节点的子节点,依次下去是一个递归的过程。
具体代码:
void DFS(MGraph g ,int i)
{
int j;
visited[i]=1;
printf("%c",g.vexs[i]);
for(j = 0;j<g.numVertexes;j++)
{
if(g.arc[i][j]==1&&visited[i]!=1)
{
DFS(g,j);
}
}
}
完整代码如下,这边对图的存储结构采用了邻接矩阵
1: #include <stdio.h>2:3: #define MAXVEX 94: #define INFINITY 655355:6: typedef struct MGraph7: {8: char vexs[MAXVEX];
9: int arc[MAXVEX][MAXVEX];
10: int numVertexes, numEdges;
11: }MGraph;12:13: int visited[MAXVEX];
14:15: void createMGraph(MGraph *g);
16: void DFS(MGraph g ,int i);17: void DFSTraverse(MGraph g);
18:19: void createMGraph(MGraph *g)
20: {21: int i, j;
22:23: g->numEdges=15;24: g->numVertexes=9;25:26: g->vexs[0]='A';27: g->vexs[1]='B';28: g->vexs[2]='C';29: g->vexs[3]='D';30: g->vexs[4]='E';31: g->vexs[5]='F';32: g->vexs[6]='G';33: g->vexs[7]='H';34: g->vexs[8]='I';35:36:37: for (i = 0; i < g->numVertexes; i++)
38: {39: for ( j = 0; j < g->numVertexes; j++)
40: {41: g->arc[i][j]=0;42: }43: }44:45: g->arc[0][1]=1;46: g->arc[0][5]=1;47:48: g->arc[1][2]=1;49: g->arc[1][8]=1;50: g->arc[1][6]=1;51:52: g->arc[2][3]=1;53: g->arc[2][8]=1;54:55: g->arc[3][4]=1;56: g->arc[3][7]=1;57: g->arc[3][6]=1;58: g->arc[3][8]=1;59:60: g->arc[4][5]=1;61: g->arc[4][7]=1;62:63: g->arc[5][6]=1;64:65: g->arc[6][7]=1;66:67:68: for(i = 0; i < g->numVertexes; i++)
69: {70: for(j = i; j < g->numVertexes; j++)
71: {72: g->arc[j][i] =g->arc[i][j];73: }74: }75:76: }77:78:79: void DFS(MGraph g ,int i)80: {81: int j;
82: visited[i]=1;83: printf("%c",g.vexs[i]);
84: for(j = 0;j<g.numVertexes;j++)
85: {86: if(g.arc[i][j]==1&&visited[i]!=1)
87: {88: DFS(g,j);89: }90: }91: }92:93: void DFSTraverse(MGraph g)
94: {95: int i;
96: for(i=0;i<g.numVertexes;i++)
97: {98: visited[i] = 0;99: }100: for(i = 0;i<g.numVertexes;i++)
101: {102: if(visited[i]!=1)
103: {104: DFS(g,i);105: }106: }107: }108:109: int main()
110: {111: MGraph g;112: createMGraph(&g);113: DFSTraverse(g);114: return 0;
115: }116: