㈠ 怎樣用鄰接矩陣為存儲結構創建一個無向圖
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);
}
㈡ 存儲結構為鄰接矩陣，怎麼編寫無向圖添加、刪除一個頂點，添加、刪除一條邊的演算法
鄰接表，存儲方法跟樹的孩子鏈表示法相類似，是一種順序分配和鏈式分配相結合的存儲結構。如這個表頭結點所對應的頂點存在相鄰頂點，則把相鄰頂點依次存放於表頭結點所指向的單向鏈表中。
對於無向圖來說，使用鄰接表進行存儲也會出現數據冗餘，表頭結點A所指鏈表中存在一個指向C的表結點的同時，表頭結點C所指鏈表也會存在一個指向A的表結點。
/* MGraph.cc: 圖的鄰接矩陣存儲表示和實現 */
/* 包含圖類型Graph定義；創建圖；深度優先遍歷；廣度優先遍歷 */
/* 用到引用型參數，在TC下無法通過編譯，VC等C++編譯器可通過 */
#include <stdio.h>
#include <string.h>
#include <limits.h> //含INT_MAX
#define VType char //頂點值類型
#define EType int //邊權值類型
#define MAXVNUM 50 //最大頂點個數
#define DIGRAPH 0 //有向圖(網)
#define UNDIGRAPH 1 //無向圖(網)
#define INVALID INT_MAX //無效權值(最大整數表示無窮大)
#define EMPTY -1 //"空"頂點序號
㈢ 鄰接矩陣的表示法
在圖的鄰接矩陣表示法中：
① 用鄰接矩陣表示頂點間的相鄰關系
② 用一個順序表來存儲頂點信息
圖的矩陣
設G=(V，E)是具有n個頂點的圖，則G的鄰接矩陣是具有如下性質的n階方陣：
【例】
下圖中無向圖G 5 和有向圖G 6 的鄰接矩陣分別為A l 和A 2 。
網路矩陣
若G是網路，則鄰接矩陣可定義為：
其中：
w ij 表示邊上的權值;
∞表示一個計算機允許的、大於所有邊上權值的數。
【例】下面帶權圖的兩種鄰接矩陣分別為A 3 和A 4 。
圖的鄰接矩陣存儲結構形式說明
#define MaxVertexNum l00 //最大頂點數，應由用戶定義
typedef char VertexType; //頂點類型應由用戶定義
typedef int EdgeType; //邊上的權值類型應由用戶定義
typedef struct{
VextexType vexs[MaxVertexNum] //頂點表
EdeType edges[MaxVertexNum][MaxVertexNum];//鄰接矩陣，可看作邊表
int n，e; //圖中當前的頂點數和邊數
}MGragh;
注意：
① 在簡單應用中，可直接用二維數組作為圖的鄰接矩陣(頂點表及頂點數等均可省略)。
② 當鄰接矩陣中的元素僅表示相應的邊是否存在時，EdgeTyPe可定義為值為0和1的枚舉類型。
③無向圖的鄰接矩陣是對稱矩陣，對規模特大的鄰接矩陣可壓縮存儲。
④鄰接矩陣表示法的空間復雜度S(n)=0(n 2 )。
⑤建立無向網路的演算法。
void CreateMGraph(MGraph *G)
{//建立無向網的鄰接矩陣表示
int i，j，k，w;
scanf("%d%d"，&G->n，&G->e); //輸入頂點數和邊數
for(i = 0;i < n;i++) //讀入頂點信息，建立頂點表
{
G->vexs=getchar();
}
for(i = 0;i < G->n;i++)
{
for(j = 0;j <G->n;j++)
{
G->edges[i][j] = 0; //鄰接矩陣初始化
}
}
for(k = 0;k < G->e;k++)
{//讀入e條邊，建立鄰接矩陣
scanf("%d%d%d"，&i，&j，&w); //輸入邊(v i ,v j )上的權w
G->edges[i][j]=w;
G->edges[j][i]=w;
}
}//CreateMGraph
該演算法的執行時間是0(n+n 2 +e)。由於e
根據圖的定義可知，圖的邏輯結構分為兩部分：V和E的集合。因此，用一個一維數組存放圖中所有頂點數據；用一個二維數組存放頂點間關系（邊或弧）的數據，稱這個二維數組為鄰接矩陣。鄰接矩陣又分為有向圖鄰接矩陣和無向圖鄰接矩陣。
Matlab表達N=4;//圖中的節點數目
dag=zeros(N,N);//鄰接矩陣初始化，值均為0
C=1;S=2;R=3;
W=4;//制定各節點編號
dag(C,[RS])=1;//有兩條有向邊：C->R,C->S
dag(R,W)=1;//有向邊：R->W
dag(S,W)=1;//有向邊：S->W
㈣ 一個含有n個頂點和e條邊得簡單無向圖,在其鄰接矩陣存儲結構中共有______個零元素
因為有n個頂點，所以有n*n個元素，2*e個非零元素（無向圖，對稱），所以有n*n-2*e個零元素。
㈤ 數據結構：畫出下圖的鄰接矩陣存儲結構
我定義一個int型二維數組 G[5][5].
點a，b,c,d分別定義編號為1,2,3,4
G[u][v]的值為零 則有向邊(u,v)不聯通
若值為1則有向邊(u,v)聯通
又因為在c,c ,java中 數組的范圍是從0開始的
為了使用方便 我們不使用下標為0的數組元素
因為有四個點 所以我們定義一個5x5的二維數組
矩陣數據如下
00000
00110
00000
00001
01000
其中 G[1][2] G[1][3]G[3][4]G[4][1]的值為一
㈥ 數據結構利用鄰接矩陣存儲結構怎樣求圖中兩個頂點之間的所有路徑
typedef struct {
ElemType vexs[MVN]; //頂點向量
AdjMatrix arcs; //鄰接矩陣
int vexnum, arcnum; //圖的當前頂點數和弧數
}MGraph;
int visited[100]; //指示頂點是否在當前路徑上
bool exist(MGraph &G,int i,int j)
{
int k;
if(i == j)
{
return false;
}
else
{
if(G.arcs[i][j] == 1)
{
return true;
}
visited[i] = 1;
for(k = 0;k < G.vexnum;k++)
{
if(!visited[k] && exist(G,k,j))
{
return true;
}
}
}
}
int main()
{
system("pause");
return 0;
}
可以參考一下
㈦ c/c++圖的鄰接矩陣存儲結構
關於圖的深度優先遍歷代碼如下：
#include <stdio.h>
#include <stdlib.h>
#define FALSE 0
#define TURE 1
#define OK 1
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20 //最大頂點個數
typedef struct ArcCell{
int adj; //頂點關系類型。用1或0表示相鄰與否
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //二維數組
typedef struct {
char vexs[MAX_VERTEX_NUM]; //頂點向量
AdjMatrix arcs; //鄰接矩陣
int vexnum,arcnum; //頂點數和弧數
}MGraph;
int LocateVex(MGraph G,char u)
{ //若圖G中存在頂點u，則返回該頂點在圖中的位置；否則返回-1
int i;
for(i=0;i<G.vexnum;i++)
if(G.vexs[i]==u)
return i;
else return -1;
}
int CreateDG(MGraph G){ //構造有向圖G
int i,j,k;
char va,vb;
printf("請輸入有向圖G的頂點數 弧數：");
scanf("%d%d",&G.vexnum,&G.arcnum);
printf("請輸入%d個頂點的值(<5個字元)：\n",G.vexnum);
for(i=0;i<G.vexnum;i++) scanf("%s",&G.vexs[i]); //構造頂點向量
for(i=0;i<G.vexnum;i++) //初始化鄰接矩陣
for(j=0;j<G.vexnum;j++)
{
G.arcs[i][j].adj=0;
}
printf("請輸入%d條弧的弧尾 弧頭：\n",G.arcnum);
for(k=0;k<G.arcnum;++k)
{
scanf("%s%s%*c",&va,&vb);
i=LocateVex(G,va);
j=LocateVex(G,vb);
G.arcs[i][j].adj=1;
}
return OK;
}
int FirstAdjVex(MGraph G,char v)
{ //返回v的第一個鄰接頂點的序號。若頂點在G中沒有鄰接頂點，則返回-1
int i,k;
k=LocateVex(G,v); //k為頂點v在圖G中的序號
for(i=0;i<G.vexnum;i++)
if(G.arcs[k][i].adj!=0)
return i;
else return -1;
return OK;
}
int NextAdjVex(MGraph G,char v,char w)
{ //返回v的相對於（w）的下一個鄰接頂點的序號，若w是v的最後一個鄰接頂點，則返回-1
int i,k1,k2;
k1=LocateVex(G,v); //k1為頂點v在圖G中的序號
k2=LocateVex(G,w); //k2為頂點w在圖G中的序號
for(i=k2+1;i<G.vexnum;i++)
if(G.arcs[k1][i].adj!=0)
return i;
else return -1;
return OK;
}
int visited[MAX_VERTEX_NUM];
int DFS(MGraph G,int v)
{ //從第v個頂點出發遞歸的深度優先遍歷圖G
int w;
visited[v]=TURE; //設置訪問標志為TURE
printf("%s",G.vexs[v]);
for(w=FirstAdjVex(G,G.vexs[v]);w>=0;w=NextAdjVex(G,G.vexs[v],G.vexs[w]))
if(!visited[w])
DFS(G,w); //對尚未訪問的序號為w的鄰接頂點遞歸的調用DFS
return OK;
}
int DFSTraverse(MGraph G)
{ //從第一個頂點起，深度優先遍歷圖G
int v;
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE; //訪問標志數組初始化
for(v=0;v<G.vexnum;v++)
if(!visited[v])
DFS(G,v); //對尚未訪問的頂點v調用DFS
printf("\n");
return OK;
}
int main()
{
MGraph G;
CreateDG(G);
DFSTraverse(G);
system("pause");
return OK;
}
廣度可以自己參照改寫。。
㈧ 以鄰接矩陣為存儲結構，分別寫出基於DFS和BFS遍歷
#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
template <class VertexType>
class Graph
{
public:
vector<VertexType> vertex; //存放節點數據
int ** edge;//鄰邊矩陣
int vcount; //頂點個數
int ecount; //邊個數
Graph():edge(NULL),vcount(0),ecount(0){}//構造函數
void CreateGraph()//創建矩陣
{
VertexType item; //頂點信息
int v ,u,w; //邊信息
cout << "請輸入頂點的個數： ";
cin >> vcount;
cout << "請輸入頂點" << endl;
for(int i = 0; i < vcount; ++i)
{
cin >> item;
vertex.push_back(item); //將頂點信息存放到向量中
}
edge = new int*[vcount]; //創建二維矩陣
for( i = 0; i < vcount; ++i )
{
edge[i] = new int[vcount];
for( int j = 0 ; j < vcount ; j++ )
edge[i][j] = 0;
}
cout << "請輸入邊的個數： ";
cin >> ecount;
cout << "請輸入邊的信息（始點，終點,權重)" << endl;
for( i = 0; i < ecount; ++i)
{
cin >> v >> u >> w;
edge[v][u] = w;
edge[u][v] = w;
cout<<"繼續輸入"<<endl;
}
}
void ShowGraph()
{
cout << "頂點的個數：" << vcount << endl;
cout << "邊的個數：" << ecount << endl;
for(int i = 0; i < vcount; ++i)
{
for(int j = 0; j < vcount; ++j)
cout << edge[i][j] << " ";
cout << endl;
}
}
void DFS(const int v)//深度優先搜索
{
cout << "深度優先搜索" << endl;
int * visited = new int[vcount]; //標志數組
for( int i = 0 ; i < vcount ; i++ )
visited[i] = 0;
DepthFS( v, visited );
cout << endl;
delete[] visited;
}
void DepthFS( const int v , int * visited )//深度優先搜索
{
cout << vertex[v] << " ";
visited[v] = 1;
for(int i = 0; i < vcount; i++ )
{
if( visited[i] == 0 && edge[v][i] != 0 )
{
DepthFS( i, visited );
}
}
}
void BFS(const int v)//廣度優先搜索
{
cout << "廣度優先搜索" << endl;
int * visited = new int[vcount];
for( int i = 0 ; i < vcount ; i++ )
visited[i] = 0;
queue<int> Q;
Q.push(v); //入隊列
while(!Q.empty())
{
int u = Q.front();
Q.pop(); //出隊列
cout << vertex[u] << " ";
visited[u] = 1;
for(int j = 0; j < vcount; ++j)
{
if( visited[j] == 0 && edge[u][j] != 0 )
{
visited[j] = 1;
Q.push(j);
}
}
}
cout << endl;
delete[] visited;
}
};
int main()
{
Graph<char> graph;
graph.CreateGraph();
graph.ShowGraph();
cout << "請輸入搜索的起始節點：-1表示終止";
int n;
cin>>n;
while(n!=-1)
{
cout << "請輸入搜索的起始節點：";
cin >> n;
graph.DFS(n);
graph.BFS(n);
}
return 0;
}
代碼還應該多自己寫呦，不要走捷徑
㈨ 在無向圖的鄰接矩陣存儲結構中,頂點度可以如何計算
該頂點行所有非零元素個數（或者該列所有非零元素個數）就是頂點的度
㈩ 數據結構 用C語言編程:求鄰接矩陣存儲結構的有向圖G中各結點的出度
對每個結點所對應的那一列，中的所有1加起來，就是出度。(鄰接矩陣中存的是0, 1)
入度的計算也是類似的。
V : 結點集合。v_i (i = 0, n-1), n = |V|.
E : 邊集合。表示為n*n的鄰接矩陣。
E[i, j] = { if v_i -> v_j 存在有向邊，1。else 0 }
求結點v_i的出度（偽碼）：
for (i = 0; i < n-1; i++) {
degree_sum = 0;
for (j = 0; j < n-1; j++) {
if (E[i][j] == 1)
degree_sum++;
}
}