graphsearch图的遍历方法有哪两种

求kruskal算法的C语言程序 越简单越好a

对于c语言，指针是灵魂，特别是在稍微高级点的程序中，指针是必不可少的。

以下程序没有用到链表，结构体用到了。

当然如果你一定要用二维数组代替结构体去存储也行，代码会变得相当麻烦而且可读性差，维护困难。

另外注释加上了。

代码临时写成，自带个人风格呵呵。

#include <stdio.h> #include <stdlib.h> #define TURE 1 #define FALSE 0 #define MAX 1000 #define abs(a) a > 0 ? a : -a //图相关---------------------- typedef struct Tnode { int loc; struct Tnode *next; } Tnode; //顶点存放结点 typedef struct Ttable { Tnode *head; Tnode *rear; int length; } Ttable; //顶点链表结构 typedef int ArcCell; /*对于无权图，用1或0表示是否相邻；对带权图，则为权值类型*/ typedef int booleanType; //状态变量 typedef struct { ArcCell **arcs; /*邻接矩阵*/ int vexnum; /*图的顶点数和弧数*/ } MGraph; /*（Adjacency Matrix Graph）*/ //---------------------------- //队列相关（链式）------------- typedef struct QNode //队列结点 { int data; struct QNode *next; } QNode; typedef struct //队列 { QNode *front, *rear; } LinkQueue; //----------------------------- MGraph G; //图 ArcCell **steparcs; //辅助矩阵 Ttable TE; //顶点链表指针 booleanType *visited; //建立标志数组(全局量） LinkQueue Q; //定义队列 int GetGraph(MGraph *G); //建立图结构 void Back(); //还原矩阵 int kruskalTravel(MGraph G); //克鲁斯卡尔算法建立最小生成树 int MinSearch(MGraph G, int *i, int *j); //查找权值最小的边，以i，j返回其两端顶点。

int FirstAdjVex(int v); int NextAdjVex(int v, int w); int InitQueue(LinkQueue *Q); //初始化队列 int EmptyQueue(LinkQueue Q); //判空 int EnQueue(LinkQueue *Q, int v); //入队 int OutQueue(LinkQueue *Q); //出队 int WFSTravel(MGraph *G, LinkQueue *Q, int x, int y); //广度遍历含有i的连通分量，如果含有j顶点，返回TRUE，否则返回FALSE int main() { GetGraph(&G); printf("Kruskal: "); kruskalTravel(G); return 0; } int GetGraph(MGraph *G) //建立邻接矩阵 { int i, j; scanf("%d", &(G->vexnum)); G->arcs = (ArcCell**)malloc(sizeof(ArcCell*) * G->vexnum); for(i = 0; i < G->vexnum; i++) { G->arcs[i] = (ArcCell*)malloc(sizeof(ArcCell) * G->vexnum); } //建立二维动态数组 for(i = 0; i < G->vexnum; i++) { for(j = 0; j < G->vexnum; j++) { scanf("%d", G->arcs[i] + j); } } //输入数据 return 0; }//GetGraph int kruskalTravel(MGraph G) //克鲁斯卡尔算法建立最小生成树 { int i, j; int N = G.vexnum; steparcs = (ArcCell**)malloc(sizeof(ArcCell*) * G.vexnum); //建立二维动态数组 for(i = 0; i < G.vexnum; i++) { steparcs[i] = (ArcCell*)malloc(sizeof(ArcCell) * G.vexnum); } //建立二维动态数组 for(i = 0; i < G.vexnum; i++) //初始化辅助矩阵 { for(j = 0; j < G.vexnum; j++) { steparcs[i][j] = 0; printf("%d ", steparcs[i][j]); } printf(" "); } printf(" "); while(N > 1) //只要剩余的连通分量大于一，就继续链接各个连通分量 { //查找权值最小的边，以i，j返回其两端顶点。

如果两个顶点属于同一连通分量，则查找权次最小边，标志矩阵为负 MinSearch(G, &i, &j); if(!WFSTravel(&G, &Q, i, j)) //广度遍历含有i的连通分量，如果含有j顶点，返回TRUE，否则返回FALSE { steparcs[i][j] = steparcs[j][i] = G.arcs[i][j]; //将符合条件的边和顶点并入到连通分量中 G.arcs[i][j] *= -1; //标志邻接矩阵，表明此条边已经查询过 G.arcs[j][i] *= -1; N--; //剩余的连通分量 for(i = 0; i < G.vexnum; i++) //输出本次步骤 { for(j = 0; j < G.vexnum; j++) { printf("%d ", steparcs[i][j]); } printf(" "); } printf(" "); } //if } //while return 0; } int MinSearch(MGraph G, int *i, int *j) //查找权值最小的边，返回其值，并以i，j返回其两端顶点。

{ int temp = MAX; //存放当前最小值 int m, n; for(n = 0; n < G.vexnum; n++) //循环查找 { for(m = 0; m < G.vexnum; m++) { if(G.arcs[n][m] > 0 && G.arcs[n][m] < temp) //找最小值 { temp = G.arcs[n][m]; *i = n; *j = m; } } } return temp; } int FirstAdjVex(int v) { int i; for(i = 0; i < G.vexnum; i++) if(steparcs[v][i] != 0) return i; return -1; } // 返回下一个邻接顶点的序号。

若顶点在G中没有邻接顶点,则返回-1 int NextAdjVex(int v, int w) { int i; for(i = w + 1; i < G.vexnum; i++) if(steparcs[v][i] != 0) return i; return -1; } int InitQueue(LinkQueue *Q) //初始化队列 { Q->front = Q->rear = (QNode*)malloc(sizeof(QNode)); //头结点 return 0; } int EmptyQueue(LinkQueue Q) //判空 { return Q.front == Q.rear ? 1 : 0; } int EnQueue(LinkQueue *Q, int v) //入队 { Q->rear->next = (QNode*)malloc(sizeof(QNode)); Q->rear = Q->rear->next; Q->rear->data = v; return 0; } int OutQueue(LinkQueue *Q) //出队 { int e; QNode *p; if(Q->front == Q->rear) { printf("Queue Empty "); exit(0); } p = Q->front; Q->front = Q->front->next; e = Q->front->data; free(p); return e; //返回队头元素 } //广度遍历含有i的连通分量，如果含有j顶点，返回TRUE，否则返回FALSE int WFSTravel(MGraph *G, LinkQueue *Q, int x, int y) { int v, = x, i; visited = (booleanType*)malloc(sizeof(booleanType) * G->vexnum); InitQueue(Q); for(v = 0; v < G->vexnum; v++) //初始化标志数组 { visited[v] = FALSE; } v = ; //初始查询顶点 if(!visited[v]) //如果没有遍历过，从此处开始遍历 { visited[v] = TURE; //遍历该结点并标志结点状态 EnQueue(Q, v); while(!EmptyQueue(*Q)) //如果队列中有元素，继续访问其邻接点 { i = OutQueue(Q); for(v = FirstAdjVex(i); v >= 0; v = NextAdjVex(i, v)) //寻找一个顶点的所有邻接点 { if(!visited[v]) //访问未访问过的顶点 { visited[v] = TURE; if(v == y) { G->arcs[x][y] *= -1; //标志邻接矩阵，表明此条边已经查询过 G->arcs[y][x] *= -1; return 1; } EnQueue(Q, v); } } //寻找一个顶点的所有邻接点 } //如果队列中有元素，继续访问其邻接点 } //如果没有遍历过，从此处开始遍历 return 0; }//WFSprint

JOJ 全称是什么

acm解题报告 有各大OJ的解题报告，建议楼主去看看。

参考资料： /category-4-1.html

ISTP检索查询

EI收录查询方法： 1.进入EI Village网站 2.选择“Compendex”数据库 3.在"Search For"中输入文章题目即可 ISTP收录查询发放： 1.进入ISI Web of Knowledge网站 2.选择“Web of Science”数据库 3.在引文数据库中选择Conference Proceedings Citation Index-Science(CPCI-S)和Conference Proceedings Citation Index-Social Science&Humanities(CPCI-SSH) 4.在检索框中输入文章题目并选择检索范围为“标题”即可 楼主自己按照上面的方法查一下，打这么多子累死我了。

什麽是Graph database?

图形数据用计算机将点、线、画霹图形基本元素按一定数据结同灶行存储的数据集合，将地图与其它类型的平面图中的图形描述为点、线、面等基本元素，并将这些图形元素按一定数据结构（通常为拓扑数据结构）建立起来的数据集合。

包括两个层次：第一层次为拓扑编码的数据集合，由描述点、线、面等图形元素间关系的数据文件组成，包括多边形文件、线段文件、结点文件等。

文件间通过关联数据项相互联系；第二层次为坐标编码数据集合，由描述各图形元素空间位置的坐标文件组成。

图形数据库仍是目前地理信息系统中对矢量结构地图数字化数据进行组织的主要形式。

谁帮忙写下这个程序呀：建立无向图的邻接矩阵存储；对已经建立的无向图进行深度优先和广度优先遍历操作。

/* Graph.h */ #include #include #include #include #include #define ERROR 0 #define OK 1 #define MAX_VERTEX_NUM 20 //定义最大值 #define INFINITY 32768 //定义极大值 #define MAX_INFO 20 typedefint VerType; //定义新的类型 typedefint InfoType; typedefchar VertexType; typedefenum {DG,DN,UDG,UDN}GraphKind;//有向图,有向网,无向图,无向网 typedefstruct ArcCell {//邻接矩阵表示法的各个数据结构 VrType adj; // 顶点关系类型。

对无权图，用或表示相邻否；对带权图，则为权值类型。

InfoType *info; // 该弧相关信息的指针 } ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedefstruct { VertexType vertex[MAX_VERTEX_NUM]; // 顶点向量 AdjMatrix arcs; // 邻接矩阵 int vexnum, um; // 图的当前顶点数和弧(边)数 GraphKind kind; // 图的种类标志 } MGraph; typedefstruct {//设置栈 int elem1[MAX_VERTEX_NUM]; ; }SeqStack; int LocateVertex(MGraph G,VertexType v); void CreateUDG(MGraph &G); void CreateUDN(MGraph &G); void DepthFirstSearch1(MGraph G); void BreadthFirstSearch1(MGraph G); int CreateGraph(MGraph &G); void Display(MGraph G); /* Graph.cpp */ int LocateVertex(MGraph G,VertexType v) {//用于返回输弧端点所表示的数值 int j=0,k; for(k=0;k的对称弧 } }//CreateUDG void CreateUDN(MGraph &G) { // 采用数组(邻接矩阵)表示法,构造无向网 int i,j,k,w,IncInfo; //i，j，k为计数器，w用于放置权值,IncInfo为标志符 char ch; VertexType v1,v2; //用于放置输入的弧的两个顶点 printf("请输入无向图G的顶点数,边数,弧是否含相关信息（是：，否：）: "); scanf("%d,%d,%d",&G.vexnum,&um,&IncInfo); ch=getchar(); printf("请输入%d个顶点的值(1个字符，空格隔开): ",G.vexnum); for(i=0;i的对称弧 } }//CreateUDN void DepthFirstSearch1(MGraph G) {//无向图、无向网深度优先遍历 int i,j,k,visited[20],t=1,a=1; //i,j,k为计数器，visited[20]为标志符用于表示是否已经访问过 SeqStack p; for(i=0;i图的遍历方法有哪两种通常有两条遍历图的路径：深度优先搜索和广度优先搜索。

它们对无向图和有向图都适用。