ITPub博客
首页 博客 专栏 学院 社区 IT新媒体评选
发博

首页 > Linux操作系统 > Linux操作系统 > 图的生成，遍历

图的生成，遍历

原创 Linux操作系统 作者：dongyu2013 时间：2014-04-16 10:45:13 0 删除 编辑

点击(此处)折叠或打开

  1. typedef char VertexType;
  2. typedef int EdgeType;
  3. #define MAXVEX 100
  4. #define INFINITY 65535

  6. typedef struct
  7. {
  8.     VertexType vexs[MAXVEX];
  9.     EdgeType arc[MAXVEX][MAXVEX];
  10.     int numVertexes, numEdges;
  11. }MGraph;

  13. void CreateMGraph( MGraph *G)
  14. {
  15.    int i,j,k,w;
  16.    printf(\"输入顶点数和变数:\\n\");
  17.    scanf(\"%d,%d\", &G->numVertexes, &G->numEdges);
  18.    for(i=0; i<G->numVertexes; i++)
  19.    {
  20.      scanf(\"%d\",&G->vexs[i]);
  21.    }
  22.    for(i=0; i<G->numVertexes; i++)
  23.    {
  24.      for(j=0; j<G->numVertexes; j++)
  25.      {
  26.          G->arc[i][j]=INFINITY;
  27.      }
  28.    }
  29.    for(k=0; k<G->numEdges; k++)
  30.    {
  31.      printf(\"输入边(vi,vj)上的下标i,下标j和权w:\\n\");
  32.      scanf(\"%d,%d,%d\",&i,&j,&w);
  33.      G->arc[i][j]=w;
  34.      G->arc[j][i]=G->arc[i][j];
  35.    }
  36. }

  38. typedef struct EdgeNode
  39. {
  40.     int adjvex;
  41.     EdgeType weight;
  42.     struct EdgeNode *next;
  43. }EdgeNode;

  45. typedef struct VertexNode
  46. {
  47.     VertexType data;
  48.     EdgeNode *firstedge;
  49. }VertexNode, AdjList[MAXVEX];

  51. typedef struct {
  52.     
  53.     AdjList adjList;
  54.     int numVertexes, numEdges;

  56. }GraphAdjList;

  58. void CreateALGraph(GraphAdjList *G)
  59. {
  60.     int i,j,k;
  61.     EdgeNode *e;
  62.     printf(\"输入顶点数和边数:\\n\");
  63.     scanf(\"%d,%d\",&G->numVertexes,&G->numEdges);
  64.     for(i=0; i<G->numVertexes; i++)
  65.     {
  66.         scanf(\"%d\",&G->adjList[i].data);
  67.         G->adjList[i].firstedge=NULL;
  68.     }
  69.     for(k=0; k<G->numEdges; k++)
  70.     {
  71.         printf(\"输入边(vi,vj)上的顶点序号:\\n\");
  72.         scanf(\"%d,%d\",&i,&j);
  73.         e=(EdgeNode *)malloc(sizeof(EdgeNode));
  74.         e->adjvex=j;
  75.         e->next=G->adjList[i].firstedge;
  76.         G->adjList[i].firstedge=e;
  77.         e=(EdgeNode *)malloc(sizeof(EdgeNode));
  78.         e->adjvex=i;
  79.         e->next=G->adjList[j].firstedge;
  80.         G->adjList[j].firstedge=e;
  81.     }
  82. }

  84. typedef int Boolean;
  85. Boolean visited[MAXVEX];

  87. void DFS(MGraph G, int i)
  88. {
  89.      int j;
  90.      visited[i]=true;
  91.      printf(\"%c\",G.vexs[i]);
  92.      for(j=0; j<G.numVertexes; j++)
  93.      {
  94.          if(G.arc[i][j]==1&&!visited[j])
  95.          {
  96.              DFS(G, j);
  97.          }
  98.      }

  100. }

  102. void DFSTraverse(MGraph G)
  103. {
  104.    int i;
  105.    for(i=0; i<G.numVertexes; i++)
  106.      visited[i]=false;
  107.    for(i=0; i<G.numVertexes; i++)
  108.    {
  109.      if(!visited[i])
  110.      {
  111.          DFS(G,i);
  112.      }
  113.    }
  114. }

  116. void DFS(GraphAdjList *GL, int i)
  117. {
  118.    EdgeNode *p;
  119.    visited[i]=true;
  120.    printf(\"%c\", GL->adjList[i].data);
  121.    p=GL->adjList[i].firstedge;
  122.    while(p)
  123.    {
  124.        if(!visited[p->adjvex])
  125.        {
  126.          DFS(GL, p->adjvex);
  127.        }
  128.      p=p->next;
  129.    }
  130. }

  132. void DFSTraverse(GraphAdjList *GL)
  133. {
  134.     int i;
  135.     for(i=0; i<GL->numVertexes; i++)
  136.     {
  137.         visited[i]=false;
  138.     }
  139.     for(i=0; i<GL->numVertexes; i++)
  140.     {
  141.         if(!visited[i])
  142.         {
  143.             DFS(GL, i);
  144.         }
  145.     }
  146. }


来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/29012686/viewspace-1143032/ ，如需转载，请注明出处，否则将追究法律责任。

0
0
上一篇： 算法求数组中的最大值最小值
下一篇： 最小生成树（普利姆算法、克鲁斯卡尔算法）
请登录后发表评论 登录
全部评论
dongyu2013

注册时间：2013-12-25

  • 博文量
    263
  • 访问量
    238073

最新文章

支持我们 作者招募 用户协议 FAQ Contact Us

北京盛拓优讯信息技术有限公司. 版权所有  京ICP备16024965号-8 北京市公安局海淀分局网监中心备案编号：11010802021510 niuxiaotong@pcpop.com 17352615567 未成年人举报专区

广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员

违法和不良信息举报电话:18101376593