厦门网站制作全程服务,WordPress 爬取插件,晋江论坛怎么搜索帖子,西部数码网站助手 安装图抽象数据类型
ADT Graph
{数据对象#xff1a;D{ai | 1in, n0, ai为ElemType类型#xff1b;}数据关系#xff1a;R {ai,aj | ai,aj属于D, 1 i,j n, 其中每个元素可以有零个或多个前驱元素#xff0c;可以有0个或多个后继元素; }基本运算…图抽象数据类型
ADT Graph
{数据对象D{ai | 1in, n0, ai为ElemType类型}数据关系R {ai,aj | ai,aj属于D, 1 i,j n, 其中每个元素可以有零个或多个前驱元素可以有0个或多个后继元素; }基本运算CreateGraph(g):创建图DestroyGraph(g):销毁图DispGraph(g):输出图DFS(g,v):从v出发的深度优先遍历图gBFS(g,v): 从v出发的广度优先遍历图g
} 邻接矩阵存储
//邻接矩阵
#define MAXV 105
#define INF 32767typedef int InfoType;
typedef struct
{int no;InfoType info;
}VertexType;
typedef struct
{int edges[MAXV][MAXV]; //起点 终点int n, e; //总顶点数 总边数VertexType vexs[MAXV]; //顶点信息数组
}MatGraph;
邻接表存储
//邻接表
typedef struct ANode
{int adjvex; //边的邻接点编号struct ANode* nextarc; //指向下一条边的指针int weight; //边信息
}ArcNode; //边结点 -- 存该点邻接点编号 指向下一边的指针 边的信息
typedef struct VNode
{InfoType info; //顶点信息ArcNode* firstarc; //指向表的第一个边结点
}VNode; //头结点类型 -- 存信息 指向第一个记录的边
typedef struct
{VNode adjlist[MAXV]; //头结点的数组int n, e; //总顶点数边数
}AdjGraph; // -- 头结点数组 点数 边数 由矩阵创建图
void CreateAdj(AdjGraph* G, int A[MAXV][MAXV], int n, int e)
{int i, j;ArcNode* p; //用于建立结点G (AdjGraph*)malloc(sizeof(AdjGraph));for (i 0; i n; i)G-adjlist[i].firstarc NULL; //初始化for (i 0; i n; i)for (j n - 1; j 0; j--)if (A[i][j] ! 0 A[i][j] ! INF){p (ArcNode*)malloc(sizeof(ArcNode));p-adjvex j;p-weight A[i][j];//链表头插法p-nextarc G-adjlist[i].firstarc;G-adjlist-firstarc p;}G-n n; G-e e;
}输出图
void DispAdj(AdjGraph* G)
{int i;ArcNode* p; //用于建立结点for (i 0; i G-n; i){p G-adjlist[i].firstarc; //第一个的边结点cout i :;while (p ! NULL){cout p-adjvex [ p-weight ] - ; //遍历链p p-nextarc;}cout endl;}
}
销毁图
void DestroyAdj(AdjGraph* G)
{int i;ArcNode* pre, * p;for (int i 0; i G-n; i){pre G-adjlist[i].firstarc; //pre也freeif (pre ! NULL){p pre-nextarc; //p往下保存结点while (p ! NULL){free(pre); //先free掉prepre p;p p-nextarc;}free(pre);}}free(G);
} 邻接矩阵转邻接表
void MatToList(MatGraph g, AdjGraph* G)
{int i, j;ArcNode* p;G (AdjGraph*)malloc(sizeof(AdjGraph));for (i 0; i g.n; i)G-adjlist[i].firstarc NULL; //置初值for (i 0; i g.n; i)for (j g.n - 1; j 0; j--)if (g.edges[i][j] ! 0 g.edges[i][j] ! INF){p (ArcNode*)malloc(sizeof(ArcNode));p-adjvex j;p-weight g.edges[i][j];p-nextarc G-adjlist[i].firstarc;G-adjlist[i].firstarc p;}G-n g.n; G-e g.e;
}
邻接表转邻接矩阵
void ListToMat(AdjGraph* G, MatGraph g)
{int i;ArcNode* p;for (int i 0; i G-n; i){p G-adjlist[i].firstarc;while (p ! NULL){g.edges[i][p-adjvex] p-weight;p p-nextarc;}}g.n G-n; g.e G-e;
}
