[讨论]急~~~图的建立与输出 — 编程爱好者社区

能将这三个程序合并一下吗？？
实现选择性的图的邻接矩阵输出！！！！
谢谢！

#include <stdio.h>
#define MAXVEX 100
typedef char VertexType; /*定义VertexType为char类型*/
struct vertex
{
int num; /*顶点编号*/
VertexType data; /*顶点的信息*/
};
typedef struct graph
{
struct vertex vexs[MAXVEX]; /*顶点集合*/
int edges[MAXVEX][MAXVEX]; /*边的集合*/
} adjmax;
adjmax creagraph(int *n)
{
int i,j,k,w,e;
char b,t;
adjmax adj;
printf("顶点数(n)和边数(e):");
scanf("%d,%d",n,&e);
for (i=1;i<=*n;i++)
{
getchar(); /*截获上面的回车键*/
printf("\t第%d个顶点的信息:",i);
scanf("%c",&adj.vexs[i].data);
adj.vexs[i].num=i;
}
for (i=1;i<=*n;i++)
for (j=1;j<=*n;j++)
adj.edges[i][j]=0;
for (k=1;k<=e;k++)
{
getchar(); /*截获上面的回车键*/
printf("第%d条边=>",k);
printf(" 起点:");
b=getche();
i=1;
while (i<=*n && adj.vexs[i].data!=b) i++;
if (i>*n)
{
printf("输入的起点不存在!\n");exit(0);
}
printf(" 终点:");
t=getche();
j=1;
while (j<=*n && adj.vexs[j].data!=t) j++;
if (j>*n)
{
printf("输入的终点不存在!\n");exit(1);
}
printf(" 权值:");
scanf("%d",&w);
adj.edges[i][j]=w;
}
return(adj);
}
void dispgraph(adjmax adj,int n)
{
int i,j,k;
printf("\n显示邻接矩阵表示的图:\n");
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (adj.edges[i][j]!=0)
printf("(%c,%c):%d\n",adj.vexs[i].data,
adj.vexs[j].data,adj.edges[i][j]);
}
main()
{
adjmax adj;
int n;
adj=creagraph(&n);
dispgraph(adj,n);
}

#include "adjmatrix.h"
int CreateUDG(MGraph &G)   //构造无向图G
{
int v,e,i,j,t;
char v1,v2;
printf("input the number of the vertices:");
scanf("%d",&v);
if(v<0)
   return ERROR;
G.vexnum=v;
printf("input ghe number of the arcs:");
scanf("%d",&e);
if(e<0)
   return ERROR;
G.arcnum=e;
for(t=0;t<G.vexnum;t++)               //输入V个顶点的值到向量G.vexs[]
{
  printf("input the vertice %d's information:",t+1);
  fflush(stdin);
  scanf("%c",&G.vexs[t]);
}
for(i=0;i<G.vexnum;i++)
  for(j=0;j<G.vwxnum;j++)
  {G.arcs[i][j].adj=INFINITY;
   G.arcs[i][j].info=NULL;              //无边的其他信息
  }
for(t=0;t<G.arcnum;t++)                //构造无向图G的邻接矩阵
{
  fflush(stdin);
  printf("input v1 and v2's information :v1-v2");  //短横线-为分隔符
  scanf("%c%*c%c",&v1,&v2);                        //"%*c"is used to cross out the "_"!
  i=LocateVex(G,v1);
  j=LocateVex(G,v2);
  if(i==-1||j==-1||i==j)
    return ERROR;
  G.arcs[i][j].adj=G.arcs[j][i].adj=1;
}
  return OK;
}

int BFSTraverse(MGraph G,int(*Visit)(char v))   //广度优先遍历图G
{
linkQueue Q;
int v,w,u;
for(v=0;v<G.vexnum;v++)                          //初始化访问标志数组visited[]
   visited[v]=0;
InitQueue(Q);
for(v=0;v<G.vexnum;v++)
{
  if(!visited[v])
  {
   visited[v]=1;
   Visit(G.vexs[v]);
   EnQueue(Q,v);
   while(!EmptyQueue(Q))
   {
    DeQueue(Q,u);
    w=FirstAdjVex(G,G.vexs[u]);
    for(;w>=0;w=NextAdjVex(G,G.vexs[u],G.vexs[w]))
      if(!visited[w])                               //w为u的尚未访问的邻接顶点
      {
      visited[w]=1;
      Visit(G.vexs[w]);
      EnQueue(Q,w);
      }
   }
  }
}
  return OK;
}

void DFS(MGraph G,int v)    //从第V个顶点出了，深度优先遍历图G
{
int w;
visited[v]=1;
Visit(G.vexs[v]);
w=FirstAdjVex(G,G.vexs[v]);
  for(;w>=0;w=NextAdjVex(G,G.vexs[v],G.vexs[w]))
   if(!visited[w])
     DFS(G,w)            //对V的尚未访问的邻接顶点W递归调用DFS()
}

void DFSTraverse(MGraph G)        //深度优先遍历图G
{
int v;
for(v=0;v<G.vexnum;v++)
   visited[v]=0;
for(v=0;v<G.vexnum;v++)
   if(!visited[v])
    DFS(G,v);
}

void main()
{
//clrscr();
MGraph G;
printf("Create the UND G:\n");
if(CreateUDG (G))
{
  printf("output the UDG G in DFS order:")
  DFSTraverse(G);
  printf("\n");
  printf("output ghe UDG G in BFS order:");
  BFSTraverse(G,Visit);
  printf("\n");
}
}

#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 10
#define ERROR 0
typedef char VertexType;
typedef int VPType;
typedef int Graphkind;
typedef int status;
typedef enum {FALSE, TRUE} boolean;
boolean visit[MAX_VERTEX_NUM];
typedef struct Arcell
{
VPType adj;
}Arcell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{
VertexType vex[MAX_VERTEX_NUM];//顶点标志或者叫代号
int vexnum, arcnum;//点的个数和边的条数
AdjMatrix arcs;
Graphkind kind;//图的类型
}MGraph;

status  CreatGraph(MGraph *G)       //建立图
{
int i, j, select;

printf("1:建立有向图!\n");
printf("2:建立无向图!\n");
printf("3:请选者种类!\n");
scanf("%d",&select);
    if (select == 1)
{
  G->kind = 0;
}
else if (select == 2)
{
  G->kind = 1;
}
else
{
  return ERROR;
}

printf("\n请输入顶点的个数:");
scanf("%d",&G->vexnum);
    getchar();// 吃掉内存中的残留数据
printf("\n 请输入顶点的信息(代号)");
for ( i = 0; i < G->vexnum; i++)
{
  scanf("%c",&G->vex[i]);//注意一下

}

getchar();
printf("\n 请输入2个顶点之间的相互关系(0表示相邻 1表示不相邻):\n");
for ( i = 0 ; i < G->vexnum; i++)
  for ( j = 0; j < G->vexnum; j++)
  {
   scanf("%d",&G->arcs[i][j].adj);
  }

   printf("建立成功\n");
   return 0;
}

status qiudu(const MGraph *G)//求度操作
{
int sum1 , sum2 = 0;
    int i, j;

if (G->kind == 1)
{
  for ( i = 0; i < G->vexnum; i++)
  {
   sum1=0;
   for ( j = 0; j < G->vexnum; j++)
   {
    if ( G->arcs[i][j].adj == 1)
    {
     sum1++;
    }
   }
   printf("编号为%c的第%d的点的度为%d\n",G->vex[i], i+1, sum1);
  }
}
else
{
  for ( i = 0 ; i < G->vexnum; i++)
  {
    sum1=0, sum2=0;
   for ( j = 0 ; j < G->vexnum; j++)
   {
    if ( G->arcs[i][j].adj == 1)
    {
     sum1++;
                }
    if ( G->arcs[j][i].adj == 1)
    {
     sum2++;
    }
   }
   printf("编号为%d的第%d的点的出度为%d入度为%d\n",G->vex[i], i+1, sum1,sum2);

  }
}

return 0;
}

void DFS(MGraph G) //深搜索
{
int i, j;
    void DFS1( MGraph G, int i);//函数声明

for (i = 0 ; i < G.vexnum; i++)
{
  visit[i] = FALSE;
}
for (j = 0; j <G.vexnum; j++)
{
  if (!visit[j])
   DFS1(G,j);//不要用&G 因为G已经是地址了
}

// return 0;
}

void DFS1(MGraph G, int i)
{
int j;

visit[i]=TRUE;
printf("%c",G.vex[i]);

for (j = 0; j < G.vexnum; j++)
{
  if ((i != j) && (G.arcs[i][j].adj == 1) && !visit[j])
  {
   DFS1(G,j);
  }
}

// return 0;
}

status BFS( const MGraph *G,int k)//广度搜索
{
   int s = 0, g = 0;
   int i, j;
   char a[MAX_VERTEX_NUM];

   for (i = 0; i < G->vexnum; i++)
   {
    visit[i] = FALSE;
   }

   printf("%c ",G->vex[k]);
   visit[k]=TRUE;

   for ( j = 0; j < G->vexnum; j++)
   {
    a[j] = -1;
   }
   a[s] = k;

   while(a[s]!=-1)
   {
    int j;

    i = a[g];
    g++;
       for ( j = 0; j < G->vexnum; j++)
    {
     if (G->arcs[i][j].adj == 1 && !visit[j])
     {
      printf("%c ",G->vex[j]);
      visit[j] = TRUE;
      s++;
      a[s] = j;
     }

    }
   if ( s == G->vexnum-1)
   {
   break;
   }
   }
   return 0;
}

int main(void)
{
    MGraph G;
    int flag, select;
int flag1 = 0;
int k;
while(1)
{
  do
  {
   printf("1:构建图\n");
   printf("2:求度\n");
   printf("3:深度搜索\n");
   printf("4:广度搜索\n");
   printf("5:退出\n");
   printf("6:请选择\n");
   scanf("%d",&select);
   if (select == 5)
   {
    flag = 0;
   }
         else
   {
    flag = 1;
   }
  }while(select < 1 || select > 6);

        if (flag == 0)
  {
   break;
  }
  switch(select)
  {
   case 1:
               flag1 = 1;
               CreatGraph(&G);
      break;
        case 2:
               if(flag1 == 1)
      {
                  qiudu(&G);
      }
      else
      {
      printf(" 请先建立图\n");
      }
      break;
        case 3:
      if(flag1 == 1)
      {
                   printf("进行深度搜索:\n");
       DFS(G);
          printf("进行深度搜索:\n");
       printf("\n");
      }
      else
      {
                    printf(" 请先建立图\n");
      }
      break;

        case 4:
      if(flag1 == 1)
      {
       printf("请哪个点开始搜索");
          scanf("%d",&k);
       getchar();
       printf("进行广度搜索\n");
       BFS(&G,k);
       printf("\n");
      }
               else
      {
                    printf(" 请先建立图\n");
      }
      break;

  default: continue;
  }
}

}

主题：[讨论]急~~~图的建立与输出

回复列表（共0个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：[讨论]急~~~图的建立与输出

回复列表 （共0个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共0个回复）