邻接表实现的图创建及遍历源码

左手的ㄟ右手 2022-09-18 11:59 120阅读 0赞

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

\#define MAXVEX 100  
\#define INFINITY 65535

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

typedef struct EdgeNode   //邻接表的边的顶点  
\{  
 int adjvex;            //每一个顶点的下标  
 int weight;             //权值  
 EdgeNode \*next;      
\}EdgeNode;

typedef struct VexNode  
\{  
 VertexType data;      //顶点表的数据  
 EdgeNode \*first;      //指向的第一个边  
\}AdjList\[MAXVEX\];

typedef struct  
\{  
 AdjList adjlist;      //邻接表的数据结构  
 int numVexs,numEdges;  //边和顶点的数目  
\}MGraphAdjList;          //图的结构体

bool visited\[MAXVEX\];  
bool found = false;

//创建无权无向图  
bool CreateMGraphAdjList1(MGraphAdjList \*G)  
\{  
 int i,j,k;  
 EdgeNode \*e,\*temp;  
 printf("请输入图的边的数目:");  
 scanf("%d",&G->numEdges);  
 printf("请输入图的顶点的数目:");  
 scanf("%d",&G->numVexs);  
 getchar();  
 //输入顶点信息  
 for(i=0;i<G->numVexs;i++)  
 \{  
  printf("请输入第%d个顶点信息:",i+1);  
  scanf("%c",&G->adjlist\[i\].data);  
  G->adjlist\[i\].first = NULL;  
  getchar();  
 \}  
 printf("请输入边的信息，vi,vj代表vi和vj的一条边\\n");  
 //输入边的信息  
 for(k=0;k<G->numEdges;k++)  
 \{  
  printf("请输入第%d条边信息:",k+1);  
  scanf("%d,%d",&i,&j);

//创建  
  e = (EdgeNode \*)malloc(sizeof(EdgeNode));  
  e->adjvex = i;  
  e->next = NULL;  
  //加入链表上边  
  if(G->adjlist\[j\].first == NULL)  
  \{  
   G->adjlist\[j\].first = e;  
  \}  
  else  
  \{  
   temp = G->adjlist\[j\].first;  
   while(temp->next)  
   \{  
    temp = temp->next;  
   \}  
   temp->next = e;  
  \}

//创建  
  e = (EdgeNode \*)malloc(sizeof(EdgeNode));  
  e->adjvex = j;  
  e->next = NULL;  
  //加入链表上边  
  if(G->adjlist\[i\].first == NULL)  
  \{  
   G->adjlist\[i\].first = e;  
  \}  
  else  
  \{  
   temp = G->adjlist\[i\].first;  
   while(temp->next)  
   \{  
    temp = temp->next;  
   \}  
   temp->next = e;  
  \}  
 \}  
 return true;  
\}

//创建有权无向图  
bool CreateMGraphAdjList2(MGraphAdjList \*G)  
\{  
 int i,j,k,w;  
 EdgeNode \*e,\*temp;  
 printf("请输入图的边的数目:");  
 scanf("%d",&G->numEdges);  
 printf("请输入图的顶点的数目:");  
 scanf("%d",&G->numVexs);  
 getchar();  
 //输入顶点信息  
 for(i=0;i<G->numVexs;i++)  
 \{  
  printf("请输入第%d个顶点信息:",i+1);  
  scanf("%c",&G->adjlist\[i\].data);  
  getchar();  
  G->adjlist\[i\].first = NULL;  
 \}  
 printf("请输入边的信息，vi,vj,w代表vi和vj的一条边,权值为w\\n");  
 //输入边的信息  
 for(k=0;k<G->numEdges;k++)  
 \{  
  printf("请输入第%d条边的信息:",k+1);  
  scanf("%d,%d,%d",&i,&j,&w);  
  //创建新的顶点  
  e = (EdgeNode \*)malloc(sizeof(EdgeNode));  
  e->adjvex = i;  
  e->next = NULL;  
  e->weight = w;  
  //加入连表中  
  if(G->adjlist\[j\].first == NULL)  
  \{  
   G->adjlist\[j\].first = e;  
  \}  
  else  
  \{  
   temp = G->adjlist\[j\].first;  
   while(temp->next)  
   \{  
    temp= temp->next;  
   \}  
   temp->next = e;  
  \}  
  //创建新的顶点  
  e = (EdgeNode \*)malloc(sizeof(EdgeNode));  
  e->adjvex = j;  
  e->next = NULL;  
  e->weight = w;  
  //加入连表中  
  if(G->adjlist\[i\].first == NULL)  
  \{  
   G->adjlist\[i\].first = e;  
  \}  
  else  
  \{  
   temp = G->adjlist\[i\].first;  
   while(temp->next)  
   \{  
    temp= temp->next;  
   \}  
   temp->next = e;  
  \}  
 \}  
 return 1;  
\}

//展示邻接表  
bool MGraphAdjListShow(MGraphAdjList \*G)  
\{  
 int i;  
 EdgeNode \*temp;  
 for(i=0;i<G->numVexs;i++)  
 \{  
  printf("%c",G->adjlist\[i\].data);  
  temp = G->adjlist\[i\].first;  
  while(temp)  
  \{  
   printf("->%c",G->adjlist\[temp->adjvex\].data);  
   temp = temp->next;  
  \}  
  putchar('\\n');  
 \}  
 return true;  
\}  
//深度优先搜索  
void DFS(MGraphAdjList \*G,int i)  
\{  
 int j;  
 EdgeNode \*temp;  
 visited\[i\] = true;  
 printf("%c",G->adjlist\[i\].data);  
 temp = G->adjlist\[i\].first;  
 while(temp)  
 \{  
  if(!visited\[temp->adjvex\])  
  \{  
   DFS(G,temp->adjvex);  
  \}  
  temp = temp->next;  
 \}  
\}  
void DFSTraverse(MGraphAdjList \*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()  
\{  
 MGraphAdjList G;  
 CreateMGraphAdjList2(&G);  
 DFSTraverse(&G);  
 return 1;  
\}