圖的操作

//圖

#include <stdio.h>

#include <stdlib.h>

#define MaxNum 100

typedef char Type;

//鄰接矩陣類型定義

typedef struct

{

Type vexs[MaxNum];

int edges[MaxNum][MaxNum];

int Vertex_num,edge_num;

}MGraph;

//鄰接表類型定義

typedef struct node

int adjvex;

struct node *next;

}EdgeNode;

struct

  Type vertex;

  EdgeNode * firstedge;

}VertexNode[MaxNum];

}ALGraph;

//為圖G建立鄰接矩陣

void CreateMGraph(MGraph *G)

int i,j,k;

printf("請輸入頂點數：");

scanf("%d",&G->Vertex_num);//輸入頂點數和邊數

printf("請輸入邊數：");

scanf("%d",&G->edge_num);

printf("請輸入頂點數資訊（例如：若有5個頂點，則連續輸入ABCDE）：");

flushall();

for(i=0;i<G->Vertex_num;i++)

  scanf("%c",&G->vexs[i]); //輸入頂點資訊，建立頂點表

}

for(i=0;i<G->Vertex_num;i++)     //初始化鄰接矩陣各元素值為0

  for(j=0;j<G->Vertex_num;j++)

   G->edges[i][j]=0;

printf("注意：頂點序列對應點的序号是從0起始編号，即0,1,2,···\n");

printf("請輸入每條邊對應的兩個頂點的序号（輸入格式為：i,j<cr>）:\n");

for(k=0;k<G->edge_num;k++)

  for(i=0;i<G->Vertex_num;i++)

   printf("%c(%d)",G->vexs[i],i);

  printf("\n");

  printf("請輸入第%d條邊：",k+1);

  scanf("%d,%d",&i,&j);   //輸入e條邊，建立鄰接矩陣

  if(i<0 || i>=G->Vertex_num || j<0 || i>=G->Vertex_num)

  {

   printf("輸入出錯！\n");

   k--;

   continue;

  }

  printf("(%c--%c)\n",G->vexs[i],G->vexs[j]);

  G->edges[i][j]=1;

  G->edges[j][i]=1;  //若為有向圖建立鄰接矩陣，該句舍棄

//深度優先搜尋周遊函數

//第一個形參MGraph * G是指要周遊的圖的存儲結構

//第二個形參int v是指從序号為V的頂點開始深度優先周遊圖

//第三個形參int *visited指向通路數組，訓示頂點是否被通路過

void dfs(MGraph *G,int v,int *visited)

int i;

*(visited+v)=1;   //辨別序号為v的頂點被通路過

printf("通路過的頂點式：%d---%c\n",v,G->vexs[v]);

for(i=0;i<G->Vertex_num;i++) //查找目前頂點的鄰接頂點

  if(G->edges[v][i]=1)   //鄰接頂點找到

   if(*(visited+i)!=1)

    dfs(G,i,visited);

void clear()       //清屏

system("pause");

system("cls");

//深度優先周遊圖

void Depth_first_graph(MGraph *G)

int visited[MaxNum];

//初始化visited數組，該數組每一個元素對應圖的一個頂點，用來辨別頂點是否被通路過

for(int i=0;i<MaxNum;i++)

  visited[i]=0;

  i=0;

do

  printf("從頂點%c開始進行深度優先周遊\n",G->vexs[i]);

  dfs(G,i,visited);  //對圖進行深度優先搜尋周遊

  for(;i<G->Vertex_num;i++)

   if(visited[i]==0)

    break;

}while(i<G->Vertex_num);

//為圖G建立鄰接表

void CreateALGraph(ALGraph *G)

EdgeNode *s;

printf("請輸入頂點數");

scanf("%d",&G->Vertex_num);

printf("請輸入邊數:");

printf("請輸入頂點資訊（例如：若有5個頂點，則連續輸入ABCDE）:");

  scanf("%c",&G->VertexNode[i].vertex);

  G->VertexNode[i].firstedge=NULL;

printf("注意：頂點的序列對應的序号從0開始編号，即0,1,2,···\n");

printf("請輸入每條邊對應的兩個頂點的序号（輸入格式為:ij<cr>）:\n");

   printf("%c(%d)",G->VertexNode[i].vertex,i);

  printf("請輸入第%d條邊:",k+1);

  scanf("%d,%d",&i,&j);  //讀入邊的兩頂點的對應的序号

  if(i<0||i>=G->Vertex_num||j<0||i>=G->Vertex_num)

  printf("(%c--%c)\n",G->VertexNode[i].vertex,G->VertexNode[j].vertex);

  s=new(EdgeNode);

  s->adjvex=j;  //鄰接點序号為j

  s->next=G->VertexNode[i].firstedge;

  G->VertexNode[i].firstedge=s;

  s=new(EdgeNode);    //再申請一個新邊表結點

  s->adjvex=i;   //鄰接點序号為i

  s->next=G->VertexNode[j].firstedge; //将新邊表結點s插入到序号為J的頂點的邊表頭部

  G->VertexNode[j].firstedge=s;

//孤獨優先搜尋周遊函數

//第一個形參ALGraph *G是指要周遊的圖的存儲結構

//第二個形參int V 是指從序号為V的頂點開始廣度優先周遊圖

//第三個形參int *visited指向通路數組，表示頂點是否被通路過

void bfs(ALGraph *G,int v,int *visited)

int quene[MaxNum],front=0,rear=1; //定義一個隊列

EdgeNode *p; //定義邊指針

*(visited+v)=1;

printf("現在通路的頂點式:%d--%c\n",v,G->VertexNode[v].vertex); //輸出正通路的頂點

if(front==rear)

  exit(1);//隊列滿，溢出

quene[rear]=v;//把通路過的點放入隊列中

rear=(rear+1)%MaxNum;

while((front+1)!=rear)   //隊列不空

  front=(front+1)%MaxNum;   //一個頂點出隊

  v=quene[front];

  p=G->VertexNode[v].firstedge;

  while(p)

   if(visited[p->adjvex]==0)//判斷p->adjvex是否被通路過

   {

    visited[p->adjvex]=1; //若沒有，則對其進行通路

    printf("通路的頂點是:%d--%c\n",p->adjvex,G->VertexNode[p->adjvex].vertex);//輸出正通路的結點

    if(front==rear)

     exit(1);

    quene[rear]=p->adjvex;

    rear=(rear+1)%MaxNum;

   }

   p->next;

//廣度優先周遊圖

void Breadth_first_graph(ALGraph *G)

int i,visited[MaxNum];

//初始化visited數組，該數組的每一個元素對應圖的每一個頂點是否被通路過

for(i=0;i<MaxNum;i++)

i=0;

  printf("從頂點%c開始進行廣度優先搜尋周遊\n",G->VertexNode[i].vertex);

  bfs(G,i,visited);//對圖進行深度優先搜尋周遊

  for(;i<G->Vertex_num++;i++)

void showmenu()

printf("\n\n\n");

printf("                  --圖的周遊--                 \n");

printf("****************************************************\n");

printf("*       1------用鄰接矩陣表表示一個圖              *\n");

printf("*       2------深度優先搜尋周遊圖（鄰接矩陣表）    *\n");

printf("*       3------用鄰接表表示一個圖                  *\n");

printf("*       4------廣度優先搜尋周遊圖（鄰接矩陣表）    *\n");

printf("*                                                  *\n");

printf("*       0------退出                                *\n");

printf("請選擇菜單号（0-4）:");

void graphOP()

char choice ='N';

int adjacency_martrix=0;

int adjacency_list=0;//标志位鄰接表是否存在

MGraph G;

ALGraph T;

while(choice!=0)

  showmenu();

  flushall();

  scanf("%c",&choice);

  switch(choice)

  case '1':

   CreateMGraph(&G);

   adjacency_martrix=1;

      clear();

   break;

  case '2':

   if(adjacency_martrix)

    Depth_first_graph(&G);

   else

    printf("請先輸入圖的頂點資訊！\n");

   clear();

  case '3':

   CreateALGraph(&T);//建立圖的鄰接表

   adjacency_list=1;

  case '4':

   if(adjacency_list)

    Breadth_first_graph(&T);

    printf("請輸入圖的頂點資訊！\n");

  case '0':

   printf("\n\t程式結束！\n");

  default:

   printf("\n\t輸入錯誤，請重新輸入！\n");

void main()

graphOP();