邻接矩阵图的创建及遍历

你的名字 2022-09-18 11:59 133阅读 0赞

\#include <stdio.h>  
\#include <stdlib.h>  
\#include <string.h>

typedef char VertexType;   //顶点的数据类型  
typedef int EdgeType;     //边的权值数据类型

\#define MAXVEX 100        //最多的边的数目  
\#define INFINITY 65535

typedef struct  
\{  
 int numVexs,numEdges;  
 EdgeType arc\[MAXVEX\]\[MAXVEX\];  
 VertexType vexs\[MAXVEX\];  
\}MGraph;                 //图的邻接矩阵的数据结构

bool visited\[MAXVEX\];    //指向图的顶点有没有访问过

//创建无向无权图  
bool CreateMGraph1(MGraph \*G)  
\{  
 int i,j,k;  
 printf("请输入图的边数目:");  
 scanf("%d",&G->numEdges);  
 putchar('\\n');  
 printf("请输入图的顶点数目:");  
 scanf("%d",&G->numVexs);  
 getchar();  
 putchar('\\n');  
 printf("请输入顶点信息\\n");  
 for(i=0;i<G->numVexs;i++)  
 \{  
  printf("请输入第%d个顶点信息:",i+1);  
  scanf("%c",&G->vexs\[i\]);  
  getchar();  
  putchar('\\n');  
 \}  
 printf("请输入边的信息,例如vi,vj表示vi下标到vj下表的边\\n");  
 for(k=0;k<G->numEdges;k++)  
 \{  
  printf("请输入第%d条边的信息:",k+1);  
  scanf("%d,%d",&i,&j);  
  putchar('\\n');  
  G->arc\[i\]\[j\] = 1;  
  G->arc\[j\]\[i\] = 1;  
 \}  
 return 1;  
\}

//创建有向无权图  
bool CreateMGraph2(MGraph \*G)  
\{  
 int i,j,k;  
 printf("请输入图的边数目:");  
 scanf("%d",&G->numEdges);  
 putchar('\\n');  
 printf("请输入图的顶点数目:");  
 scanf("%d",&G->numVexs);  
 getchar();  
 putchar('\\n');  
 printf("请输入顶点信息\\n");  
 for(i=0;i<G->numVexs;i++)  
 \{  
  printf("请输入第%d个顶点信息:",i+1);  
  scanf("%c",&G->vexs\[i\]);  
  getchar();  
  putchar('\\n');  
 \}  
 printf("请输入边的信息,例如vi,vj表示vi下标到vj下表的边\\n");  
 for(k=0;k<G->numEdges;k++)  
 \{  
  printf("请输入第%d条边的信息:",k+1);  
  scanf("%d,%d",&i,&j);  
  putchar('\\n');  
  G->arc\[i\]\[j\] = 1;  
 \}  
 return 1;  
\}

//创建有权无向图  
bool CreateMGraph3(MGraph \*G)  
\{  
 int i,j,k,w;  
 printf("请输入图的顶点数目:");  
 scanf("%d",&G->numVexs);  
 putchar('\\n');  
 printf("请输入图的边数目:");  
 scanf("%d",&G->numEdges);  
 getchar();  
 putchar('\\n');  
 //输入顶点信息  
 for(i=0;i<G->numVexs;i++)  
 \{  
  printf("请输入第%d个顶点",i+1);  
  scanf("%c",&G->vexs\[i\]);  
  getchar();  
  putchar('\\n');  
 \}  
 //使得每一个边的权重都是最大值  
 for(i=0;i<G->numEdges;i++)  
 \{  
  for(j=0;j<G->numEdges;j++)  
  \{  
   G->arc\[i\]\[j\] = INFINITY;  
  \}  
 \}  
 //输入边的信息  
 printf("请输入边的信息,例如vi,vj,w.表示vi下标到vj下表的边权重是w\\n");  
 for(k=0;k<G->numEdges;k++)  
 \{  
  printf("请输入第%d个边的信息:",i+1);  
  scanf("%d,%d,%d",&i,&j,&w);  
  G->arc\[i\]\[j\] = G->arc\[j\]\[i\] = w;  
  putchar('\\n');  
 \}  
 return 1;  
\}

//创建有权有向图  
bool CreateMGraph4(MGraph \*G)  
\{  
 int i,j,k,w;  
 printf("请输入图的顶点数目:");  
 scanf("%d",&G->numVexs);  
 putchar('\\n');  
 printf("请输入图的边数目:");  
 scanf("%d",&G->numEdges);  
 getchar();  
 putchar('\\n');  
 //输入顶点信息  
 for(i=0;i<G->numVexs;i++)  
 \{  
  printf("请输入第%d个顶点",i+1);  
  scanf("%c",&G->vexs\[i\]);  
  getchar();  
  putchar('\\n');  
 \}  
 //使得每一个边的权重都是最大值  
 for(i=0;i<G->numEdges;i++)  
 \{  
  for(j=0;j<G->numEdges;j++)  
  \{  
   G->arc\[i\]\[j\] = INFINITY;  
  \}  
 \}  
 //输入边的信息  
 printf("请输入边的信息,例如vi,vj,w.表示vi下标到vj下表的边权重是w\\n");  
 for(k=0;k<G->numEdges;k++)  
 \{  
  printf("请输入第%d个边的信息:",i+1);  
  scanf("%d,%d,%d",&i,&j,&w);  
  G->arc\[i\]\[j\] = w;  
  putchar('\\n');  
 \}  
 return 1;  
\}

void DFS(MGraph \*G,int i)  
\{  
 int j;  
 visited\[i\] = true;  
 printf("%c->",G->vexs\[i\]);  
 for(j=0;j<G->numVexs;j++)  
 \{  
  if(G->arc\[i\]\[j\] && !visited\[i\])  
  \{  
   DFS(G,j);  
  \}  
 \}  
\}

void DFSTraverse(MGraph \*G)  
\{  
 int i;  
 for(i=0;i<G->numVexs;i++)  
 \{  
  visited\[i\] = false;  
 \}  
 for(i=0;i<G->numVexs;i++)  
 \{  
  if(!visited\[i\])  
  \{  
   DFS(G,i);  
  \}  
 \}  
\}  
int main()  
\{  
 MGraph G;  
 CreateMGraph1(&G);  
 DFSTraverse(&G);  
 return 1;  
\}