㈠ 怎样用邻接矩阵为存储结构创建一个无向图
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++;
}
}