图的定义
图(Graph)是由顶点的有穷非空集合和顶点之间的集合组成，通常表示为G[V, E]，其中G表示一个图，V是图G的顶点集合，E是图G中边的集合。
图
图的存储
1.邻接矩阵(顺序)
1.1 数据结构设计
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXVEX 100 /* 最大顶点数，应由用户定义 */
#define INFINITYC 0
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */
typedef struct
{
VertexType vexs[MAXVEX]; /* 顶点表 */
EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */
int numNodes, numEdges; /* 图中当前的顶点数和边数 */
}MGraph;
1.2 存储
void CreateMGraph(MGraph *G){
int i,j,k,w;
printf("输入顶点数和边数:\n");
//1. 输入顶点数/边数
scanf("%d,%d",&G->numNodes,&G->numEdges);
printf("顶点数:%d,边数:%d\n",G->numNodes,G->numEdges);
//2.输入顶点信息/顶点表
for(i = 0; i<= G->numNodes;i++)
scanf("%c",&G->vexs[i]);
//3.初始化邻接矩阵
for(i = 0; i < G->numNodes;i++)
for(j = 0; j < G->numNodes;j++)
G->arc[i][j] = INFINITYC;
//4.输入边表信息
for(k = 0; k < G->numEdges;k++){
printf("输入边(vi,vj)上的下标i,下标j,权w\n");
scanf("%d,%d,%d",&i,&j,&w);
G->arc[i][j] = w;
//如果无向图,矩阵对称;
G->arc[j][i] = G->arc[i][j];
}
/*5.打印邻接矩阵*/
for (int i = 0; i < G->numNodes; i++) {
printf("\n");
for (int j = 0; j < G->numNodes; j++) {
printf("%d ",G->arc[i][j]);
}
}
printf("\n");
1.3 测试
int main(void)
{
printf("邻接矩阵实现图的存储\n");
/*图的存储-邻接矩阵*/
MGraph G;
CreateMGraph(&G);
return 0;
}
2.邻接表
2.1 数据结构设计
#define M 100
#define true 1
#define false 0
typedef char Element;
typedef int BOOL;
//邻接表的节点
typedef struct Node{
int adj_vex_index; //弧头的下标，也就是被指向的下标
Element data; //权重值
struct Node * next; //边指针
}EdgeNode;
//顶点节点表
typedef struct vNode{
Element data; //顶点的权值
EdgeNode * firstedge; //顶点下一个是谁？
}VertexNode, Adjlist[M];
//总图的一些信息
typedef struct Graph{
Adjlist adjlist; //顶点表
int arc_num; //边的个数
int node_num; //节点个数
BOOL is_directed; //是不是有向图
}Graph, *GraphLink;
2.2 存储
void creatGraph(GraphLink *g){
int i,j,k;
EdgeNode *p;
//1. 顶点,边,是否有向
printf("输入顶点数目,边数和有向？：\n");
scanf("%d %d %d", &(*g)->node_num, &(*g)->arc_num, &(*g)->is_directed);
//2.顶点表
printf("输入顶点信息：\n");
for (i = 0; i < (*g)->node_num; i++) {
getchar();
scanf("%c", &(*g)->adjlist[i].data);
(*g)->adjlist[i].firstedge = NULL;
}
//3.
printf("输入边信息：\n");
for (k = 0; k < (*g)->arc_num; k++){
getchar();
scanf("%d %d", &i, &j);
//①新建一个节点
p = (EdgeNode *)malloc(sizeof(EdgeNode));
//②弧头的下标
p->adj_vex_index = j;
//③头插法插进去，插的时候要找到弧尾，那就是顶点数组的下标i
p->next = (*g)->adjlist[i].firstedge;
//④将顶点数组[i].firstedge 设置为p
(*g)->adjlist[i].firstedge = p;
//j->i
if(!(*g)->is_directed)
{
// j -----> i
//①新建一个节点
p = (EdgeNode *)malloc(sizeof(EdgeNode));
//②弧头的下标i
p->adj_vex_index = i;
//③头插法插进去，插的时候要找到弧尾，那就是顶点数组的下标i
p->next = (*g)->adjlist[j].firstedge;
//④将顶点数组[i].firstedge 设置为p
(*g)->adjlist[j].firstedge = p;
}
}
}
void putGraph(GraphLink g){
int i;
printf("邻接表中存储信息:\n");
//遍历一遍顶点坐标，每个再进去走一次
for (i = 0; i < g->node_num; i++) {
EdgeNode * p = g->adjlist[i].firstedge;
while (p) {
printf("%c->%c ", g->adjlist[i].data, g->adjlist[p->adj_vex_index].data);
p = p->next;
}
printf("\n");
}
}
2.3 测试
int main(int argc, const char * argv[]) {
// insert code here...
printf("邻接表实现图的存储\n");
/*
邻接表实现图的存储
输入顶点数目,边数和有向？：
4 5 0
输入顶点信息：
0 1 2 3
输入边信息：
0 1 0 2 0 3 2 1 2 3
邻接表中存储信息:
0->3 0->2 0->1
1->2 1->0
2->3 2->1 2->0
3->2 3->0
*/
/*
邻接表实现图的存储
输入顶点数目,边数和有向？：
4 5 1
输入顶点信息：
0 1 2 3
输入边信息：
1 0 1 2 2 1 2 0 0 3
邻接表中存储信息:
0->3
1->2 1->0
2->0 2->1
*/
GraphLink g = (Graph *)malloc(sizeof(Graph));
creatGraph(&g);
putGraph(g);
return 0;
}
网友评论