欢迎大家访问我的个人博客：endeavorchuan.com
有向完全图： 有向图中有n个顶点，则边至多有n(n-1)条，有n(n-1)条边的有向图称为有向完全图。
无向完全图： 无向图中有n个顶点，最多有n(n-1)/2条边，有n(n-1)/2的无向图称为无向完全图。
简单路径： 序列中顶点不重复出现的路径。
连通图： 无向图中任意两个顶点之间都连通。
强连通图： 对于每一对顶点i和j，从i到j和从j到i都有路径。
邻接矩阵是图的顺序存储结构，由邻接矩阵行数或列数可知图中顶点数。
无权图邻接矩阵： 有权图邻接矩阵： 邻接矩阵结构型定义：
typedef struct { int no; //定义顶点编号 char info; //可存储顶点其他信息，使用char类型 }VertexType; //顶点类型 typedef struct //图的定义 { int edges[maxSize][maxSize]; //邻接矩阵定义，有权图中，将int改为float int n,e; //n代表顶点数，e代表边数 VertexType vex[maxSize]; //存放结点信息 }MGraph; //图的邻接矩阵类型邻接表是图的链式存储结构，对图中每个顶点i建立一个单链表，每个单链表第一个结点存放顶点信息，其余结点存放边的信息。
图的邻接表存储： 邻接表存储表示的定义：
typedef struct ArcNode { int adjvex; //该边所指向的结点的位置 struct ArcNode *nextarc; //指向下一条边的指针 int info; //存储该边的相关信息 }ArcNode; typedef struct { char data; //顶点信息 ArcNode *firstarc; //指向第一条边的指针 }VNode; typedef struct { VNode adjlist[maxSize]; //邻接表 int n,e; //n表示顶点数，e表示边数 }AGraph; //图的邻接表类型任取一个顶点，访问，检查这个顶点的所有邻接顶点，递归访问其中未被访问过的顶点。
int visit[maxSize]; //为全局数组，作为顶点的访问标记，初始时元素均为0，对每个元素顶点进行标记 void DFS( AGraph *G, int v ) { ArcNode *p; //辅助指针 visit[v] = 1; //置已访问标记为1 Visit(v); //Visit()代表了一类访问顶点v的操作 p = G->adjlist[v].firstarc; //p指向顶点v的第一条边 while( p!=NULL ) //当p不为空时 { if( visit[p->adjvex] == 0 ) //若p的标记为0，即顶点未被访问 DFS( G, p->adjvex ); //递归访问顶点p p = p->nextarc; //p指向顶点v的下一条边的终点 } }广度优先遍历需用到一个队列，如二叉树的层次遍历。
任取图中一个顶点访问，入队，并将这个顶点标记为已访问队列非空时，出队，以此检查出队顶点的所有邻接顶点，访问未访问过的邻接顶点，并将其入队队列为空时跳出循环，广度优先遍历完成 void BFS( AGraph *G, int v, int visit[maxSize] ) { ArcNode *p; //辅助指针 int que[maxSize], front=0, rear=0; //队列定义的简单写法 int j; Visit(v); //任意访问顶点v的函数 visit[v] = 1; //已访问标记置为1 rear = (rear+1)%maxSize; que[rear] = v; //当前顶点v入队 while( front!= rear ) //队非空时继续遍历，队空时遍历完成 { front = (front+1)%maxSize; j = que[front]; //顶点出队 p = G->adjlist[j].firstarc; //p指向出队顶点j的第一条边 while(p!=NULL) //将p的所有邻接点中未被访问的入队 { if( visit[p->dajvex]==0 ) //若当前邻接顶点未被访问，则进队 { Visit(p->adjvex); visit[p->adjvex] = 1; //已访问标记置为1 rear = (rear+1)%maxSize; que[rear] = p->adjvex; //该顶点入队 } p = p->nextarc; //p指向j的下一条边 } } }