無向圖的存儲結構

⑴ 建立圖的存儲結構（圖的類型可以是有向圖、無向圖、有向網、無向網，學生可以任選

鏈表

⑵ 要求採用鄰接矩陣作為無向圖的存儲結構，鄰接表作為有向圖的存儲結構，完成無向圖和有向圖的建立，並對建

#include"utility.h"
#include"adj_matrix_undir_graph.h"
#include"adj_list_dir_graph.h"
#include"dfs.h"
#include"bfs.h"

int main(void)
{
int n,j=0,i=0;
int m,e,b=0;
char vexs[20],c;
char nums[20];

cout<<"輸入無向圖的頂點個數n:"<<endl;
cin>>n;
cout<<"輸入頂點元素："<<endl;
for(i=0;i<n;i++)
{
cout<<"請輸入第"<<j<<"個結點"<<endl;
cin>>vexs[i];
j++;
}

cout<<"輸出無向圖的鄰接矩陣："<<endl;

AdjMatrixUndirGraph<char> aundir(vexs,n);
for(i=0;i<n;i++)
{
for(int v=1;v<n;v++)
{
cout<<"輸入Y/N，是否插入邊:";
cin>>c;
if(c == 'Y' )
aundir.InsertEdge(i,v);
}
}
Display(aundir);

cout<<"請輸入有向圖的頂點個數m：";
cin>>m;
for(int a=0;a<m;a++)
{
cout<<"輸入第"<<b<<"個頂點數據";
cin>>nums[a];
b++;
}

AdjListDirGraph<char> dir(nums,m);

for(int k=0;k<m;k++)
{
for(e=0;e<m;e++)
{
cout<<"是否插入邊V"<<k<<",V"<<e<<":";
cin>>c;
if(c == 'Y' )
dir.InsertEdge(k,e);
}
}
Display(dir);

cout<<"無向圖的深度遍歷：";
DFSTraverse<char>(aundir,Write<char>);
cout<<endl;
cout<<"無向圖的廣度遍歷：";
BFSTraverse<char>(aundir,Write<char>);

cout<<endl;
cout<<"有向圖的深度遍歷：";
DFSTraverse<char>(dir,Write<char>);
cout<<endl;
cout<<"有向圖的廣度遍歷：";
BFSTraverse<char>(dir,Write<char>);

⑶ 無向圖 其臨街矩陣存儲結構共有多少元素

因為有n個頂點,所以有n*n個元素,2*e個非零元素（無向圖,對稱）,所以有n*n-2*e個零元素.

⑷ 怎樣將一棵二叉樹的存儲結構轉化為一個無向圖的存儲結構，誰能說說編程思想啊

圖的存儲機構一般用鄰接矩陣或鄰接表,二叉樹一般是鏈表結構,就是把鏈表變成臨近矩陣了,用中序形勢對鏈表節點進行編號和訪問並做為臨近矩陣的順序,用中序訪問,對當前節點和後繼節點判斷,然後置對應的矩陣為1,(a[當前],[後繼]=1 ,a[後繼],[當前]=1 ) ,中序訪問完就可以了

⑸ 求用C語言和數據結構中的無向圖存儲結構編一個校園導游圖完全的程序代碼

#define Infinity 1000
#define MaxVertexNum 35
#define MAX 40
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<string.h>
#include<iostream.h>
typedef struct arcell //邊的權值信息
{
int adj; //權值
}arcell,adjmatrix[MaxVertexNum][MaxVertexNum]; //圖的鄰接矩陣類型

typedef struct vexsinfo //頂點信息
{
int position; //景點的編號
char name[32]; //景點的名稱
char introction[256]; //景點的介紹
}vexsinfo;

typedef struct mgraph //圖結構信息
{
vexsinfo vexs[MaxVertexNum]; //頂點向量(數組)
adjmatrix arcs; //鄰接矩陣
int vexnum,arcnum; //分別指定頂點數和邊數
}mgraph;

//全局變數

int visited[35]; //用於標志是否已經訪問過

int d[35]; //用於存放權值或存儲路徑頂點編號

mgraph campus; //圖變數(大學校園)

// (1) 對圖初始化

mgraph initgraph()
{
int i=0,j=0;
mgraph c;

c.vexnum =28; //頂點個數
c.arcnum =39; //邊的個數
for(i=0;i<c.vexnum ;i++) //依次設置頂點編號
c.vexs[i].position =i;
//依次輸入頂點信息
strcpy(c.vexs[0].name ,"小西南門");
strcpy(c.vexs[0].introction ,"離公交站近");
strcpy(c.vexs[1].name ,"學校南正門");
strcpy(c.vexs[1].introction ,"學校大門、學校班車進出口");
strcpy(c.vexs[2].name ,"語言文化職業學院");
strcpy(c.vexs[2].introction ,"語言文化職業學院辦公樓，樓高6層");
strcpy(c.vexs[3].name ,"藝術學院");
strcpy(c.vexs[3].introction ,"音樂系、美術系，樓高4層");
strcpy(c.vexs[4].name ,"行政樓");
strcpy(c.vexs[4].introction ,"行政辦公大樓，樓高5層");
strcpy(c.vexs[5].name,"文學院");
strcpy(c.vexs[5].introction ,"文學院，樓高6層");
strcpy(c.vexs[6].name ,"體育場");
strcpy(c.vexs[6].introction ,"室外標准田徑場");
strcpy(c.vexs[7].name,"教育科學學院");
strcpy(c.vexs[7].introction ,"教心系、經管系，樓高5層");
strcpy(c.vexs[8].name ,"南區學生宿舍");
strcpy(c.vexs[8].introction ,"離西南門近");
strcpy(c.vexs[9].name, "數學與經濟管理學院");
strcpy(c.vexs[9].introction , "數學與經濟管理學院大樓，樓高4層");
strcpy(c.vexs[10].name ,"中區學生宿舍");
strcpy(c.vexs[10].introction ,"若干棟，離學生1、2食堂近");
strcpy(c.vexs[11].name ,"職業學院教學大樓");
strcpy(c.vexs[11].introction ,"職業學院教學大樓，樓高5層");
strcpy(c.vexs[12].name ,"體育系");
strcpy(c.vexs[12].introction ,"體育系，樓高5層");
strcpy(c.vexs[13].name ,"游泳館");
strcpy(c.vexs[13].introction ,"室內小型游泳館");
strcpy(c.vexs[14].name ,"報告廳、階梯教室");
strcpy(c.vexs[14].introction ,"可舉辦中、大型學術會議。有大小報告廳1－6個、階梯教室1－6個");
strcpy(c.vexs[15].name ,"大禮堂、體育館");
strcpy(c.vexs[15].introction ,"文藝演出所在地、室內運動場");
strcpy(c.vexs[16].name ,"1食堂");
strcpy(c.vexs[16].introction ,"教工食堂及學生1食堂在此");
strcpy(c.vexs[17].name ,"新圖書館");
strcpy(c.vexs[17].introction ,"建築面積46000平方米");
strcpy(c.vexs[18].name ,"2食堂");
strcpy(c.vexs[18].introction ,"學校東區，學生食堂");
strcpy(c.vexs[19].name ,"東區學生宿舍");
strcpy(c.vexs[19].introction ,"離學生2食堂近");
strcpy(c.vexs[20].name ,"計算機學院");
strcpy(c.vexs[20].introction ,"計算機學院大樓，樓高5層");
strcpy(c.vexs[21].name ,"教工宿舍");
strcpy(c.vexs[21].introction ,"學校青年教職工租住地");
strcpy(c.vexs[22].name ,"西區學生宿舍");
strcpy(c.vexs[22].introction ,"離學生3、4食堂近");
strcpy(c.vexs[23].name ,"3食堂");
strcpy(c.vexs[23].introction ,"學校西區，學生食堂");
strcpy(c.vexs[24].name ,"外國語學院");
strcpy(c.vexs[24].introction ,"外國語學院大樓，樓高5層");
strcpy(c.vexs[25].name ,"4食堂");
strcpy(c.vexs[25].introction ,"學校西區，學生食堂，人氣較高");
strcpy(c.vexs[26].name ,"校醫院");
strcpy(c.vexs[26].introction ,"看小病的地方");
strcpy(c.vexs[27].name ,"實驗樓");
strcpy(c.vexs[27].introction ,"物電學院、化學與生命科學學院、機電系、建材系所在地，機房及多媒體教室若干");

//依次輸入邊上的權值信息
for(i=0;i<c.vexnum ;i++)
for(j=0;j<c.vexnum ;j++)
c.arcs [i][j].adj =Infinity; //先初始化圖的鄰接矩陣

//部分弧長

c.arcs[0][2].adj=50; c.arcs[0][3].adj=60;

c.arcs[1][4].adj=90;

c.arcs[2][3].adj=60; c.arcs[2][8].adj=40;

c.arcs[3][4].adj=60; c.arcs[3][6].adj=40;

c.arcs[4][5].adj=70; c.arcs[4][9].adj=70; c.arcs[4][10].adj=80; c.arcs[4][17].adj=200;

c.arcs[5][7].adj=70;

c.arcs[6][9].adj=40;

c.arcs[7][18].adj=190;

c.arcs[8][11].adj=50;

c.arcs[9][12].adj=40;

c.arcs[10][18].adj=70;

c.arcs[11][12].adj=60; c.arcs[11][14].adj=50; c.arcs[11][15].adj=50;

c.arcs[12][16].adj=50;

c.arcs[13][14].adj=40; c.arcs[13][22].adj=60;

c.arcs[14][15].adj=50; c.arcs[14][20].adj=90;

c.arcs[15][16].adj=60; c.arcs[15][21].adj=40;

c.arcs[16][17].adj=60;

c.arcs[17][18].adj=80;

c.arcs[18][19].adj=60;

c.arcs[20][21].adj=60; c.arcs[20][24].adj=80;

c.arcs[22][23].adj=60; c.arcs[22][25].adj=80;

c.arcs[23][24].adj=60;

c.arcs[24][26].adj=100; c.arcs[24][27].adj=100;

c.arcs[25][26].adj=90;

c.arcs[26][27].adj=90;

for(i=0;i<c.vexnum ;i++) //鄰接矩陣是對稱矩陣，對稱賦值
for(j=0;j<c.vexnum ;j++)
c.arcs[j][i].adj =c.arcs[i][j].adj ;
return c;
}//initgraph

// (2) 查找景點在圖中的序號

int locatevex(mgraph c,int v)
{
int i;
for(i=0;i<c.vexnum ;i++)
if(v==c.vexs[i].position)
return i; //找到，返回頂點序號i

return -1; //否則，返回-1
}

//(3) 、(4) 求兩景點間的所有路徑

// (3) 列印序號為m,n景點間的長度不超過8個景點的路徑

void path(mgraph c, int m,int n,int k)
{
int s,x=0;
int t=k+1; //t 記載路徑上下一個中間頂點在d[]數組中的下標
if(d[k]==n && k<8) //d[k]存儲路徑頂點。若d[k]是終點n且景點個數<=8，則輸出該路徑
{ //遞歸出口，找到一條路徑
for(s=0;s<k;s++)
printf("%s--->",c.vexs[d[s]].name); //輸出該路徑。s=0 時為起點m
printf("%s",c.vexs[d[s]].name); //輸出最後一個景點名(即頂點n的名字，此時s==k)
printf("\n\n");
}
else
{
s=0;
while(s<c.vexnum) //從第m個頂點，試探至所有頂點是否有路徑
{
if((c.arcs[d[k]][s].adj<Infinity) && (visited[s]==0)) //初態：頂點m到頂點s有邊，且未被訪問
{
visited[s]=1;
d[k+1]=s; //存儲頂點編號s 至d[k+1]中
path(c,m,n,t); //求從下標為t=k+1的第d[t]個頂點開始的路徑(遞歸調用)，同時列印出一條m至n的路徑
visited[s]=0; //將找到的路徑上頂點的訪問標志重新設置為0，以用於試探新的路徑
}
s++; //試探從下一個頂點 s 開始是否有到終點的路徑
}//endwhile

}//endelse

}//endpath

//(4) 列印兩景點間的景點個數不超過8的所有路徑。調用(3)

int allpath(mgraph c)
{
int k,i,j,m,n;
printf("\n\n請輸入你要查詢的兩個景點編號:\n\n");
scanf("%d%d",&i,&j);
printf("\n\n");
m=locatevex(c,i); //調用(2)，確定該頂點是否存在。若存在，返回該頂點編號
n=locatevex(c,j);
d[0]=m; //存儲路徑起點m (int d[]數組是全局變數)
for(k=0;k<c.vexnum;k++) //全部頂點訪問標志初值設為0
visited[k]=0;
visited[m]=1; //第m個頂點訪問標志設置為1
path(c,m,n,0); //調用(3)。k=0，對應起點d[0]==m。k為d[]數組下標
return 1;
}

// (5) 用迪傑斯特拉演算法，求出一個景點到其他景點間的最短路徑，並列印

void shortestpath_dij(mgraph c)
{
//迪傑斯特拉演算法，求從頂點v0到其餘頂點的最短路經及其帶權長度d[v]
//若p[v][w]為1，則w是從v0到v的最短路經上的頂點
//final[v]類型用於設置訪問標志

int v,w,i,min,t=0,x,flag=1,v0; //vo為起始景點的編號
int final[35],d[35],p[35][35];
printf("\n請輸入一個起始景點的編號：");
scanf("%d",&v0);
printf("\n\n");
while(v0<0||v0>c.vexnum)
{
printf("\n你所輸入的景點編號不存在\n");
printf("請重新輸入：");
scanf("%d",&v0);
}//while
for(v=0;v<c.vexnum ;v++)
{
final[v]=0; //初始化各頂點訪問標志
d[v]=c.arcs[v0][v].adj; //v0 到各頂點 v 的權值賦值給d[v]
for(w=0;w<c.vexnum ;w++) //初始化p[][]數組，各頂點間的路徑全部設置為空路徑0
p[v][w]=0;
if(d[v]<Infinity) //v0 到v 有邊相連，修改p[v][v0]的值為1
{
p[v][v0]=1;
p[v][v]=1; //各頂點自己到自己要連通
}
}//for
d[v0]=0; //自己到自己的權值設為0
final[v0]=1; //v0的訪問標志設為1，v 屬於 s 集
for(i=1;i<c.vexnum ;i++) //對其餘c.vexnum-1個頂點w，依次求 v 到 w 的最短路徑
{
min=Infinity;
for(w=0;w<c.vexnum ;w++) //在未被訪問的頂點中，查找與 v0 最近的頂點v
if(!final[w])
if(d[w]<min) //v0 到 w (有邊)的權值<min
{
v=w;
min=d[w];
}//if
final[v]=1; //v 的訪問標志設置為1，v 屬於s集
for(w=0;w<c.vexnum ;w++) //修改v0 到其餘各頂點w 的最短路徑權值d[w]
if(!final[w]&&(min+c.arcs[v][w].adj <d[w])) //若w 不屬於s，且v 到w 有邊相連
{
d[w]=min+c.arcs[v][w].adj; //修改v0 到w 的權值d[w]
for(x=0;x<c.vexnum ;x++) //所有v0 到v 的最短路徑上的頂點x，都是v0 到w 的最短路徑上的頂點
p[w][x]=p[v][x];
p[w][w]=1;
}//if
}//for
for(v=0;v<c.vexnum ;v++) //輸出v0 到其它頂點v 的最短路徑
{
if(v!=v0)
printf("%s",c.vexs[v0].name); //輸出景點v0 的景點名
for(w=0;w<c.vexnum ;w++) //對圖中每個頂點w，試探w 是否是v0 到v 的最短路徑上的頂點
{
if(p[v][w] && w!=v0 && w!=v) //若w 是且w 不等於v0，則輸出該景點
printf("--->%s",c.vexs[w].name);

}
printf("---->%s",c.vexs[v].name);
printf("\n總路線長為%d米\n\n",d[v]);

}//for
}//shortestpath

//(6)-(11)修改圖的信息。包括建圖、更新信息、刪除、增加結點和邊

//(6) 構造圖的鄰接矩陣

int creatgragh(mgraph &c) //建圖。以圖的鄰接矩陣存儲圖
{
int i,j,m,n;
int v0,v1;
int distance;
printf("請輸入圖的頂點數和邊數: \n");
scanf("%d %d",&c.vexnum ,&c.arcnum );
printf("下面請輸入景點的信息：\n");
for(i=0;i<c.vexnum ;i++) //構造頂點向量(數組)
{
printf("請輸入景點的編號：");
scanf("%d",c.vexs[i].position );
printf("\n請輸入景點的名稱：");
scanf("%s",c.vexs[i].name );
printf("\n請輸入景點的簡介：");
scanf("%s",c.vexs[i].introction );
}
for(i=0;i<c.arcnum ;i++) //初始化鄰接矩陣
for(j=0;j<c.arcnum ;j++)
c.arcs[i][j].adj =Infinity;

printf("下面請輸入圖的邊的信息：\n");
for(i=1;i<=c.arcnum ;i++) //構造鄰接矩陣
{
printf("\n第%d條邊的起點 終點 長度為：",i);//輸入一條邊的起點、終點及權值
scanf("%d %d %d",&v0,&v1,&distance);
m=locatevex(c,v0);
n=locatevex(c,v1);
if(m>=0 && n>=0)
{
c.arcs[m][n].adj =distance;
c.arcs[n][m].adj =c.arcs[m][n].adj ;
}
}
return 1;
}//creatgragh

// (7) 更新圖的部分信息。返回值: 1

int newgraph(mgraph &c)
{
int changenum; //計數。用於記錄要修改的對象的個數
int i,m,n,t,distance,v0,v1;
printf("\n下面請輸入你要修改的景點的個數：\n");
scanf("%d",&changenum);
while(changenum<0||changenum>c.vexnum )
{
printf("\n輸入錯誤！請重新輸入");
scanf("%d",&changenum);
}

for(i=0;i<changenum;i++)
{
printf("\n請輸入景點的編號：");
scanf("%d",&m);
t=locatevex(c,m);
printf("\n請輸入景點的名稱：");
scanf("%s",c.vexs[t].name );
printf("\n請輸入景點的簡介：");
scanf("%s",c.vexs[t].introction );
}

printf("\n下面請輸入你要更新的邊數");
scanf("%d",&changenum);
while(changenum<0||changenum>c.arcnum )
{
printf("\n輸入錯誤！請重新輸入");
scanf("%d",&changenum);
}

printf("\n下面請輸入更新邊的信息：\n");
for(i=1;i<=changenum ;i++)
{
printf("\n修改的第%d條邊的起點 終點 長度為：",i);
scanf("%d %d %d",&v0,&v1,&distance);
m=locatevex(c,v0);
n=locatevex(c,v1);
if(m>=0&&n>=0)
{
c.arcs[m][n].adj =distance;
c.arcs[n][m].adj =c.arcs[m][n].adj ;
}
}
return 1;
}//newgraph

⑹ 採用鄰接矩陣作為無向圖的存儲結構

沒分還要做那麼多，………………

⑺ 無向完全圖採用什麼存儲結構較省空間

鄰接矩陣比較好~
凡是邊比較多的圖，用矩陣相對省一點。。。

⑻ 怎樣用鄰接矩陣為存儲結構創建一個無向圖

int CreateUDG(AdjMatrix *G){
int i,j,k,weight;
VertexData v1,v2;
printf("輸入圖的弧數和頂點數\n");
fflush(stdin);
scanf("%d,%d",&G->arcnum,&G->vexnum); /*輸入圖的頂點數和弧數*/
for(i=0;i<G->vexnum;i++) /*初始化鄰接矩陣*/
for(j=0;j<G->vexnum;j++)
G->arcs[i][j].adj=INFINITY;
for(i=0;i<G->vexnum;i++)
{
printf("輸入圖的頂點\n");
fflush(stdin);
scanf("%c",&G->vexs[i]); /* 輸入圖的頂點*/
}
for(k=0;k<G->arcnum;k++)
{
printf("輸入一條弧的兩個頂點及權值\n");
fflush(stdin);
scanf("%c,%c,%d",&v1,&v2,&weight);/*輸入一條弧的兩個頂點及權值*/
i=LocateVertex(G,v1);
j=LocateVertex(G,v2);
G->arcs[i][j].adj=weight; /*建立弧*/
}
return(Ok);
}

void main()
{
AdjMatrix G;
CreateDN(&G);
}

⑼ 採用鄰接矩陣作為無向圖的存儲結構，鄰接表作為有向圖的存儲結構，完成無向圖和有

YOUdiano~~~~

⑽ 以鄰接多重表為存儲結構，實現連通無向圖的深度優先遍歷和廣度優先遍歷。

沒有現成的，自己看看套用一下吧。
鄰接多重表
/*********************************************************
Title : graph-multiadjacentlist.c
Author :
Time :
Purpose : 圖的多重鄰接鏈表表示法
Thread :
Comment :
Usage :
**********************************************************/
#include "stdio.h"
#include "stdlib.h"

/*=====================變數聲明--variable declaration=================*/
struct edge /* 圖形邊線結構聲明 */
{
int vertex1; /* 頂點1資料 */
int vertex2; /* 頂點2資料 */
struct edge *edge1; /* 頂點1下一邊線 */
struct edge *edge2; /* 頂點2下一邊線 */
};
typedef struct edge *nextedge; /* 圖形的邊線新型態 */

struct node /* 圖形頂點結構宣告 */
{
int vertex; /* 頂點資料 */
struct edge *edge; /* 頂點下一邊線 */
};
typedef struct node *graph; /* 圖形的結構新型態 */
struct node head[6]; /* 圖形頂點結構數組 */

/*=====================函數聲明--function declaration=================*/
void creategraph(int *node,int num);

/*====================函數實現--function implementation================*/
/* --------------------------------------------------
Function : void creategraph()
Purpose :
Arguments :
Returns :
------------------------------------------------- */
void creategraph(int *node,int num)
{
nextedge newnode; /* 新邊線指標 */
nextedge previous; /* 前一邊線指標 */
nextedge ptr; /* 目前邊線指標 */
int from; /* 邊線的起點 */
int to; /* 邊線的終點 */
int i;

for ( i = 0; i < num; i++ ) { /* 讀取邊線的迴路 */
from = node[i*2]; /* 邊線的起點 */
to = node[i*2+1]; /* 邊線的終點 */
/* 建立新邊線記憶體 */
newnode = ( nextedge ) malloc(sizeof(struct edge));
newnode->vertex1 = from; /* 建立頂點內容 */
newnode->vertex2 = to; /* 建立頂點內容 */
newnode->edge1 = NULL; /* 設定指標初值 */
newnode->edge2 = NULL; /* 設定指標初值 */
previous = NULL; /* 前一邊線指標 */
ptr = head[from].edge; /* 目前邊線指標 */

while ( ptr != NULL ) { /* 遍歷到最後邊線 */
previous = ptr; /* 保留前一邊線 */
if ( ptr->vertex1 == from ) /* 決定走的邊線 */
ptr = ptr->edge1; /* 下一邊線 */
else
ptr = ptr->edge2; /* 下一邊線 */
}

if ( previous == NULL )
head[from].edge = newnode; /* 設定頂點邊線指標 */
else
if ( previous->vertex1 == from ) /* 決定走的邊線 */
previous->edge1 = newnode; /* 連接下一邊線 */
else
previous->edge2 = newnode; /* 連接下一邊線 */
previous = NULL; /* 前一邊線指標 */
ptr = head[to].edge; /* 目前邊線指標 */

while ( ptr != NULL ) { /* 遍歷到最後邊線 */
previous = ptr; /* 保留前一邊線 */
if ( ptr->vertex1 == to ) /* 決定走的邊線 */
ptr = ptr->edge1; /* 下一邊線 */
else
ptr = ptr->edge2; /* 下一邊線 */
}

if ( previous == NULL )
head[to].edge = newnode; /* 設定頂點邊線指標 */
else
if ( previous->vertex1 == to ) /* 決定走的邊線 */
previous->edge1 = newnode; /* 連接下一邊線 */
else
previous->edge2 = newnode; /* 連接下一邊線 */
}
}

/*======================主函數--main function--建立圖形後,將邊線列印出========================*/
int main(int argc, char* argv[])
{
nextedge ptr;
int node[6][2] = { {1, 2}, /* 邊線數組 */
{1, 3},
{2, 3},
{2, 4},
{3, 5},
{4, 5}, };
int i;

for ( i = 1; i <= 5; i++ ) {
head.vertex = i; /* 設定頂點值 */
head.edge = NULL; /* 清除圖形指標 */
}

creategraph(node,6); /* 建立圖形 */
printf("圖形的多重鄰接鏈表內容:\n");

for ( i = 1; i <= 5; i++ ) {
printf("頂點%d =>",head.vertex); /* 頂點值 */
ptr = head.edge;
/* 邊線位置 */
while ( ptr != NULL ) { /* 遍歷至鏈表尾 */
/* 印出邊線 */
printf("(%d,%d)",ptr->vertex1,ptr->vertex2);
/* 決定下一邊線指標 */
if ( head.vertex == ptr->vertex1 )
ptr = ptr->edge1; /* 下一個邊線 */
else
ptr = ptr->edge2; /* 下一個邊線 */
}

printf("\n"); /* 換行 */
}

return 1;
}

// 圖的遍歷 *
// 生成，深度、廣度優先遍歷 *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTEX_NUM 20 //圖的最大頂點數
#define MAXQSIZE 30 //隊列的最大容量
enum BOOL {False,True};
typedef struct ArcNode
{int adjvex; //該弧所指向的頂點的位置
struct ArcNode *nextarc; //指向下一條弧的指針
}ArcNode; //弧結點
typedef struct
{ArcNode* AdjList[MAX_VERTEX_NUM]; //指向第一條依附該頂點的弧的指針
int vexnum,arcnum; //圖的當前頂點和弧數
int GraphKind; //圖的種類，0---無向圖，1---有向圖
}Graph;
typedef struct //隊列結構
{int elem[MAXQSIZE]; //數據域
int front; //隊頭指針
int rear; //隊尾指針
}SqQueue;
BOOL visited[MAX_VERTEX_NUM]; //全局變數——訪問標志數組
void CreateGraph(Graph &); //生成圖的鄰接表
void DFSTraverse(Graph); //深度優先搜索遍歷圖
void DFS(Graph,int);
void BFSTraverse(Graph); //廣度優先搜索遍歷圖
void Initial(SqQueue &); //初始化一個隊列
BOOL QueueEmpty(SqQueue); //判斷隊列是否空
BOOL EnQueue(SqQueue &,int); //將一個元素入隊列
BOOL DeQueue(SqQueue &,int &); //將一個元素出隊列
int FirstAdjVex(Graph,int); //求圖中某一頂點的第一個鄰接頂點
int NextAdjVex(Graph,int,int); //求某一頂點的下一個鄰接頂點
void main()
{Graph G; //採用鄰接表結構的圖
char j='y';
//------------------程序解說----------------------------
printf("本程序將演示生成一個圖，並對它進行遍歷.
");
printf("首先輸入要生成的圖的種類.
");
printf("0---無向圖, 1--有向圖
");
printf("之後輸入圖的頂點數和弧數。
格式：頂點數，弧數；例如:4,3
");
printf("接著輸入各邊(弧尾，弧頭).
例如:
1,2
1,3
2,4
");
printf("程序會生成一個圖，並對它進行深度和廣度遍歷.
");
printf("深度遍歷:1->2->4->3
廣度遍歷:1->2->3->4
");
//------------------------------------------------------
while(j!='N'&&j!='n')
{printf("請輸入要生成的圖的種類(0/1):");
scanf("%d",&G.GraphKind); //輸入圖的種類
printf("請輸入頂點數和弧數：");
scanf("%d,%d",&G.vexnum,&G.arcnum); //輸入圖的頂點數和弧數
CreateGraph(G); //生成鄰接表結構的圖
DFSTraverse(G); //深度優先搜索遍歷圖
BFSTraverse(G); //廣度優先搜索遍歷圖
printf("圖遍歷完畢，繼續進行嗎?(Y/N)");
scanf(" %c",&j);
}
}

void CreateGraph(Graph &G)
{//構造鄰接表結構的圖G
int i;
int start,end;
ArcNode *s;
for(i=1;i<=G.vexnum;i++) G.AdjList=NULL; //初始化指針數組
for(i=1;i<=G.arcnum;i++)
{scanf("%d,%d",&start,&end); //輸入弧的起點和終點
s=(ArcNode *)malloc(sizeof(ArcNode)); //生成一個弧結點
s->nextarc=G.AdjList[start]; //插入到鄰接表中
s->adjvex=end;
G.AdjList[start]=s;
if(G.GraphKind==0) //若是無向圖，再插入到終點的弧鏈中
{s=(ArcNode *)malloc(sizeof(ArcNode));
s->nextarc=G.AdjList[end];
s->adjvex=start;
G.AdjList[end]=s;
}
}
}
void DFSTraverse(Graph G)
{//深度優先遍歷圖G
int i;
printf("DFSTraverse:");
for(i=1;i<=G.vexnum;i++) visited=False; //訪問標志數組初始化
for(i=1;i<=G.vexnum;i++)
if(!visited) DFS(G,i); //對尚未訪問的頂點調用DFS
printf("\b\b
");
}
void DFS(Graph G,int i)
{//從第i個頂點出發遞歸地深度遍歷圖G
int w;
visited=True; //訪問第i個頂點
printf("%d->",i);
for(w=FirstAdjVex(G,i);w;w=NextAdjVex(G,i,w))
if(!visited[w]) DFS(G,w); //對尚未訪問的鄰接頂點w調用DFS
}

void BFSTraverse(Graph G)
{//按廣度優先非遞歸的遍歷圖G，使用輔助隊列Q和訪問標志數組visited
int i,u,w;
SqQueue Q;
printf("BFSTreverse:");
for(i=1;i<= G.vexnum;i++) visited=False; //訪問標志數組初始化
Initial(Q); //初始化隊列
for(i=1;i<=G.vexnum;i++)
if(!visited)
{visited=True; //訪問頂點i
printf("%d->",i);
EnQueue(Q,i); //將序號i入隊列
while(!QueueEmpty(Q)) //若隊列不空，繼續
{DeQueue(Q,u); //將隊頭元素出隊列並置為u
for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))
if(!visited[w]) //對u的尚未訪問的鄰接頂點w進行訪問並入隊列
{visited[w]=True;
printf("%d->",w);
EnQueue(Q,w);
}
}
}
printf("\b\b
");
}

int FirstAdjVex(Graph G,int v)
{//在圖G中尋找第v個頂點的第一個鄰接頂點
if(!G.AdjList[v]) return 0;
else return(G.AdjList[v]->adjvex);
}
int NextAdjVex(Graph G,int v,int u)
{//在圖G中尋找第v個頂點的相對於u的下一個鄰接頂點
ArcNode *p;
p=G.AdjList[v];
while(p->adjvex!=u) p=p->nextarc; //在頂點v的弧鏈中找到頂點u
if(p->nextarc==NULL) return 0; //若已是最後一個頂點，返回0
else return(p->nextarc->adjvex); //返回下一個鄰接頂點的序號
}

void Initial(SqQueue &Q)
{//隊列初始化
Q.front=Q.rear=0;
}
BOOL QueueEmpty(SqQueue Q)
{//判斷隊列是否已空，若空返回True,否則返回False
if(Q.front==Q.rear) return True;
else return False;
}

BOOL EnQueue(SqQueue &Q,int ch)
{//入隊列，成功返回True，失敗返回False
if((Q.rear+1)%MAXQSIZE==Q.front) return False;
Q.elem[Q.rear]=ch;
Q.rear=(Q.rear+1)%MAXQSIZE;
return True;
}

BOOL DeQueue(SqQueue &Q,int &ch)
{//出隊列,成功返回True，並用ch返回該元素值，失敗返回False
if(Q.front==Q.rear) return False;
ch=Q.elem[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
return True; //成功出隊列，返回True
}

轉載