無向圖矩陣存儲數據結構

A. 求用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

B. 數據結構問題 什麼是有向圖和無向圖

有向圖在圖中的邊是有方向的，表現出來就是有個箭頭指示方向，節點只能單向通信或傳遞消息，相當於單行道，無向圖邊沒方向是雙向的，邊連接的兩個節點有通路可以雙向通信，類似於雙行道。

無向圖，邊沒有方向的圖稱為無向圖。鄰接矩陣則是對稱的，且只有0和1，因為沒有方向的區別後，要麼有邊，要麼沒邊。

有向圖，一個有向圖D是指一個有序三元組(V(D)，A(D)，ψD)，其中ψD為關聯函數，它使A(D)中的每一個元素(稱為有向邊或弧)對應於V(D)中的一個有序元素(稱為頂點或點)對。

(2)無向圖矩陣存儲數據結構擴展閱讀：

的G2和(c)圖中的G3均是無向圖，它們的頂點集和邊集分別為：

V(G2)={v1，v2，v3，v4}

E(G2)={(vl，v2)，(v1，v3)，(v1，v4)，(v2，v3)，(v2，v4)，(v3，v4)}

V(G3)={v1，v2，v3，v4，v5，v6，v7}

E(G3)={(v1，v2)，(vl，v3)，(v2，v4)，(v2，v5)，(v3，v6)，(v3，v7)}

C. 請問一下這道數據結構無向圖的題目

1. 鄰接矩陣的表示方法，如果圖中兩個頂點間有直接路徑則矩陣相應位置為1或者路徑權值，否則為0.可以用公式描述：

   

D. 數據結構中的圖 無向和有向，怎樣存入文件

通常圖都分為結點和弧，您存儲圖到文件可以按照這種方法來實現。
typedef struct {
int type; //標識是有向圖還是無向圖，例如0表示有向圖，非0表示無向圖
int vexnum;
char *arclist; //arclist指向一個vexnum*vexnum的矩陣，存儲節點間的弧
}CHART;

1. 寫文件時將上面的結構寫入文件，然後將vexnum*vexnum的弧矩陣寫入文件
2. 讀文件時先讀取上面的結構，然後依據vexnum先申請一個vexnum*vexnum大小的空間
賦值給arclist，然後從文件繼續讀取vexnum*vexnum大小的數據存儲到arclist指向的數
組中。

E. 計算機考研：數據結構常用演算法解析(7)

第七章：
對於無向圖，e的范圍是：
數據結構中所討論的圖都是簡單圖，任意兩結點間不會有雙重的邊。
對於有向圖，e的范圍是：
圖的各種存儲結構
鄰接矩陣很方便訪問任意兩點的邊，但是不方便計算其鄰接點。在深度和廣度遍歷中廣泛的需要求某點的鄰接點。所以鄰接矩陣只在Floyed和Prim和Dijstra中採用。
鄰接表能很方便的求某頂點的鄰接點，索引對於與遍歷有關的演算法大多都採用鄰接表。如深度、廣度、拓撲排序、關鍵路徑。但他也有不足的地方，就是不方便求入度或是那些薯早握點可以到他的操作。所以有人引進逆鄰接表。最後人們把這兩種表結合到一起就是十字鏈表和鄰接多重表。一個是存儲有向圖，另一個是存儲無向圖。
在十字鏈睜歷表和鄰接多重表很方便求鄰接點的操作和對應的逆操作。所以實際應用中，凡是能用鄰接表實現的一定能用十字鏈表和鄰接多重表實現。並且它們的存儲效率更高。
1.鄰接矩陣(有向圖和無向圖和網)又稱為數組表示法
typedef struct
{ vextype vexs[maxn]; ∥頂點存儲空間∥
adjtype A[maxn][maxn]; ∥鄰接矩陣∥
int vexnum,arcnum; //圖的頂點數和邊數
GraphKind Kind; //圖的類型
} mgraph;
2.鄰接表(有向圖和無向圖和網)
typedef struct node ∥邊
{ int adj; int w; ∥鄰接點、權∥
struct node *next; ∥指向下一弧或邊∥
}linknode;
typedef struct ∥頂點類型∥
{ vtype data; ∥頂點值域∥
linknode *farc; ∥指向與本頂點關聯的第一條弧或邊∥
}Vnode;
typedef struct
{
Vnode G[maxn]; ∥頂點表∥
int vexnum,arcnum;
GraphKind kind;
}ALGraph;
adjvexnextarcinfo
邊結點
datafirstarc
頂點結點
3.十字鏈表(有向圖和有向網)
headvextaivexhlinktlinkinfo
邊結點
datafirstinfirstout
頂點結點
4.鄰接多重表(無向圖)
markivexjvexilinkjlinkinfo
邊結點
datafirstedge
頂點結點
有向無環圖(DAG)：是描述含有公共子式的表達式的有效工具。二叉樹也能表示表達式，但是利用有向無環圖可以實現對相同子式的共享，從而節省存儲空間。
頂點的度：
無向圖：某頂點V的度記為D(V)，代表與V相關聯的邊的條數
有向圖：頂點V的度D(V)=ID(V)+OD(V)
強連通分量:在有向圖中，若圖中任意兩頂點間都存在路徑，則稱其是強連通圖。圖中極大 強連通子圖稱之為強連通分量
「極大」在這里指的是：往一個連通分量中再加入頂點和邊，就構不成原圖中的一個 連通子圖，即連通分量是一個最大集的連通子圖。有向圖的連通就是指該有向圖是強連通的。

考研有疑問、不知道如何總結考研考點內容、不清楚數慶考研報名當地政策，點擊底部咨詢官網，免費領取復習資料：https://www.87dh.com/xl/