数据结构中用邻接矩阵方式储存图，广度优先，深度优先遍历

    博客分类：

  • c 语言
数据结构J#

以下是作业，用它用实现用邻接矩阵的方式来进行广度优先和深度优先的遍历。

代码比较简单，用了两个小时来写出来。

/**用邻接矩阵的方式来储存图，用广度优先方式进行遍历 **/

C代码
  1. #include"stdio.h"
  2. #definemax_matrix10
  3. intvisited[max_matrix],matrix[max_matrix][max_matrix];
  4. intn;
  5. intboard_traverse();
  6. intmain()
  7. {
  8. inti,j;
  9. scanf("%d",&n);
  10. if(n<1)
  11. {
  12. printf("nmustbe>1\n");
  13. exit(0);
  14. }
  15. if(n>max_matrix)
  16. {
  17. printf("nmustbe<%d\n",max_matrix);
  18. exit(0);
  19. }
  20. for(i=0;i<n;i++)
  21. {
  22. visited[i]=0;
  23. for(j=0;j<n;j++)
  24. matrix[i][j]=0;
  25. }
  26. while(scanf("%d%d",&i,&j)==2)
  27. {
  28. matrix[i-1][j-1]=1;
  29. }
  30. for(i=0;i<n;i++)
  31. {
  32. for(j=0;j<n;j++)
  33. printf("%d",matrix[i][j]);
  34. printf("\n");
  35. }
  36. printf("1");
  37. board_traverse(0);
  38. }
  39. intboard_traverse()
  40. {
  41. inttemp,i,j,ma_j,ma_i;
  42. for(ma_i=0;ma_i<n;ma_i++)
  43. for(ma_j=ma_i;ma_j<n;ma_j++)
  44. if(matrix[ma_i][ma_j]&&visited[ma_j]==0)
  45. {
  46. printf("%d",ma_j+1);
  47. visited[ma_j]=1;
  48. }
  49. }
#include "stdio.h"
#define max_matrix 10
int visited[max_matrix],matrix[max_matrix][max_matrix];
int n;
int board_traverse();
int main()
{
int i,j;
scanf("%d",&n);
if (n<1)
{
printf("n must be >1\n");
exit(0);
}
if (n>max_matrix)
{
printf("n must be <%d\n",max_matrix);
exit(0);
}
for (i=0;i<n;i++)
{
visited[i]=0;
for (j=0;j<n;j++)
matrix[i][j] = 0;
}
while (scanf("%d %d",&i,&j)==2)
{
matrix[i-1][j-1]=1;
}
for(i=0;i<n;i++)
{
for (j=0;j<n;j++)
printf("%d ",matrix[i][j]);
printf("\n");
}
printf("1 ");
board_traverse(0);
}
int board_traverse()
{
int temp,i,j,ma_j,ma_i;
for (ma_i=0;ma_i<n;ma_i++)
for (ma_j=ma_i;ma_j<n;ma_j++)
if (matrix[ma_i][ma_j] && visited[ma_j]==0)
{
printf("%d ",ma_j+1);
visited[ma_j]=1;
}
}

/**用邻接矩阵的方式来储存图，用深度优先方式进行遍历 **/

C代码
  1. #include"stdio.h"
  2. #definemax_matrix10
  3. intvisited[max_matrix],matrix[max_matrix][max_matrix];
  4. intn;
  5. intdeep_traverse(int);
  6. intmain()
  7. {
  8. inti,j;
  9. scanf("%d",&n);
  10. if(n<1)
  11. {
  12. printf("nmustbe>1\n");
  13. exit(0);
  14. }
  15. if(n>max_matrix)
  16. {
  17. printf("nmustbe<%d\n",max_matrix);
  18. exit(0);
  19. }
  20. for(i=0;i<n;i++)
  21. {
  22. visited[i]=0;
  23. for(j=0;j<n;j++)
  24. matrix[i][j]=0;
  25. }
  26. while(scanf("%d%d",&i,&j)==2)
  27. {
  28. matrix[i-1][j-1]=1;
  29. }
  30. for(i=0;i<n;i++)
  31. {
  32. for(j=0;j<n;j++)
  33. printf("%d",matrix[i][j]);
  34. printf("\n");
  35. }
  36. printf("1->");
  37. deep_traverse(0);
  38. }
  39. intdeep_traverse(intma_i)
  40. {
  41. inttemp,i,j,ma_j;
  42. ma_j=ma_i;
  43. while(ma_j<n)
  44. {
  45. if(matrix[ma_i][ma_j]&&visited[ma_j]==0)
  46. {
  47. printf("%d->",ma_j+1);
  48. visited[ma_j]=1;
  49. deep_traverse(ma_j);
  50. }
  51. ma_j++;
  52. }
  53. }
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。