[b][size=4][color=FF00FF]我的blog，[url=http://www.9ite.cn]http://www.9ite.cn[/url]欢迎大家来踩[/color][/size][/b]

7-1  图的定义和术语
7-1-1  图的定义
7-1-2  图的相关术语
无向图（Undigraph）  
有向图（Digraph）
无向完全图
有向完全图
稠密图、稀疏图
顶点的度
权
网——边（或弧）上带权的图称为网（Network）
路径、路径长度
回路、简单路径、简单回路
子图
连通图、连通分量
强连通图、强连通分量
生成树
7-1-3  图的基本操作
7-2  图的存储表示
7-2-1  邻接矩阵
#define MAXLEN 10
typedef struct
{
char vexs[MAXLEN];
int edges[MAXLEN][MAXLEN];
int n,e;
}MGraph;
建立一个图的邻接矩阵存储的算法如下：
void CreateMGraph(MGraph *G)
{ 
int i,j,k;
char ch1,ch2;
printf("请输入顶点数和边数(输入格式为:顶点数,边数):\n");
scanf("%d,%d",&(G->n),&(G->e));
printf("请输入顶点信息(顶点号<CR>)每个顶点以回车作为结束:\n");
for(i=0;i<G->n;i++)
{
getchar();scanf("%c",&(G->vexs[i]));
}
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
G->edges[i][j]=0;
printf("请输入每条边对应的两个顶点的序号(输入格式为:i,j):\n");
for(k=0;k<G->e;k++)
{
getchar();
printf("请输入第%d条边的顶点序号：",k+1);
scanf("%c,%c",&ch1,&ch2);
for(i=0;ch1!=G->vexs[i];i++);
for(j=0;ch2!=G->vexs[j];j++);
G->edges[i][j]=1;
}
}
7-2-2  邻接表
    ＃define MAXLEN 10          // 最大顶点数为10
    typedef struct node{                // 边表结点
          int adjvex;                    // 邻接点域
          struct node  * next;          // 指向下一个邻接点的指针域
          //若要表示边上信息，则应增加一个数据域info
         }EdgeNode;        
    typedef struct vnode{               // 顶点表结点
          VertexType vertex;           // 顶点域
          EdgeNode  * firstedge;       // 边表头指针
         }VertexNode;       
    typedef VertexNode AdjList[MAXLEN]; // AdjList是邻接表类型
    typedef struct{  
         AdjList adjlist;              // 接表
         int n,e;                      // 顶点数和边数
        }ALGraph;                    // ALGraph是以邻接表方式存储的图类型
建立一个有向图的邻接表存储的算法如下：
 void CreateGraphAL (ALGraph *G)
 {
     int i,j,k;
     EdgeNode * s;
     printf("请输入顶点数和边数(输入格式为:顶点数,边数)：\n");
     scanf("%d,%d",&(G->n),&(G->e)); // 读入顶点数和边数
     printf("请输入顶点信息(输入格式为:顶点号<CR>)每个顶点以回车作为结束:\n");
     for (i=0;i<G->n;i++) // 立有n个顶点的顶点表
   { scanf("\n%c",&(G->adjlist[i].vertex)); // 读入顶点信息
   G->adjlist[i].firstedge=NULL; // 点的边表头指针设为空
   }
     printf("请输入边的信息(输入格式为:i,j)：\n");
     for (k=0;k<G->e;k++) // 建立边表
  { scanf("\n%d,%d",&i,&j); // 读入边<Vi,Vj>的顶点对应序号
   s=new EdgeNode; // 生成新边表结点s
   s->adjvex=j; // 邻接点序号为j
   s->next=G->adjlist[i].firstedge; // 将新边表结点s插入到顶点Vi的边表头部
   G->adjlist[i].firstedge=s;
 }
}
7-3  图的遍历
7-3-1  深度优先搜索
void DFSTraverseM(MGraph *G)
{
int i;
for(i=0;i<G->n;i++)
visited[i]=FALSE; // FALSE在c语言中定义为0，以下同
for(i=0;i<G->n;i++)
if(!visited[i]) 
DFSM(G,i);
}
    void DFSM(MGraph *G,int i)
{
int j;
printf("\t\t深度优先遍历结点: 结点%c\n",G->vexs[i]);
visited[i]=TRUE; // TRUE在c语言中定义为0，以下同
for(j=0;j<G->n;j++)
if(G->edges[i][j]==1&&!visited[j])
DFSM(G,j);
}
7-3-2  广度优先搜索
void BFSTraverseM(MGraph *G)
{
int i;
for (i=0;i<G->n;i++)
visited[i]=FALSE;
for (i=0;i<G->n;i++)
if (!visited[i]) 
BFSM(G,i);
}

void BFSM(MGraph *G,int k)
{ 
int i,j;
CirQueue Q;
InitQueue(&Q);
printf("广度优先遍历结点: 结点%c\n",G->vexs[k]);
visited[k]=TRUE;
EnQueue(&Q,k);
while (!QueueEmpty(&Q))
{
i=DeQueue(&Q);
for (j=0;j<G->n;j++)
if(G->edges[i][j]==1&&!visited[j])
{
printf("广度优先遍历结点:%c\n",G->vexs[j]);
visited[j]=TRUE;
EnQueue(&Q,j);
}
}
}
7-4  图的连通性
7-4-1  无向图的连通分量和生成树
7-4-2  最小生成树
1．最小生成树的基本概念
2．常用的构造最小生成树的方法
构造最小生成树的Prim算法
构造最小生成树的Kruskal算法
7-5  最短路径
小结
实验7  图子系统
1．实验目的
2．实验内容
3．操作举例
4．参考程序
#define MAXLEN 10
#include <stdio.h>
#define FALSE 0
#define TRUE 1
#define Error printf
#define QueueSize 30
typedef struct
{
char vexs[MAXLEN];
int edges[MAXLEN][MAXLEN];
int n,e;
}MGraph;

int visited[10];
void CreateMGraph(MGraph *G);
void DFSTraverseM(MGraph *G);
void BFSTraverseM(MGraph *G);
void DFSM(MGraph *G,int i);
void BFSM(MGraph *G,int i);

typedef struct
{ int front;
int rear;
  int count;
  int data[QueueSize];
}CirQueue;

void InitQueue(CirQueue *Q)
{Q->front=Q->rear=0;
 Q->count=0;
}

int QueueEmpty(CirQueue *Q)
{return Q->count=QueueSize;
}

int QueueFull(CirQueue *Q)
{return Q->count==QueueSize;
}

void EnQueue(CirQueue *Q,int x)
{ if (QueueFull(Q))
Error("Queue overflow");
     else
   { Q->count++;
Q->data[Q->rear]=x;
Q->rear=(Q->rear+1)%QueueSize;
   }
}
int DeQueue(CirQueue *Q)
{int temp;
 if(QueueEmpty(Q))
{ Error("Queue underflow");
return NULL;
}
else{temp=Q->data[Q->front];
Q->count--;
Q->front=(Q->front+1)%QueueSize;
return temp;
}
}

void main()
{MGraph *G,a;
 char ch1;
 int i,j,ch2;
 G=&a;
 printf("\n\t\t建立一个有向图的邻接矩阵表示\n");
 CreateMGraph(G);
 printf("\n\t\t已建立一个图的邻矩阵存储\n\t\t");
 for(i=0;i<G->n;i++)
{ for(j=0;j<G->n;j++)
printf("%5d",G->edges[i][j]);
printf("\n\t\t");                
}
getchar();
ch1='y';
while(ch1=='y'||ch1=='Y')
{
printf("\n\n\n\n\n\t\t图 子 系 统\n");
printf("\t\t*****************************************\n");
printf("\t\t*          1-------更新邻接矩阵            *\n");
printf("\t\t*          2-------深度优先遍历            *\n");
printf("\t\t*          3-------广度优先遍历            *\n");
printf("\t\t*          0-------退        出            *\n");
printf("\t\t*****************************************\n");
printf("\t\t请选择菜单号(0--3):");
scanf("%d",&ch2);     getchar();
switch(ch2)
{
case 1:CreateMGraph(G);
printf("\t\t\t图的邻接矩阵存储建立完毕.\n");
break;
case 2:DFSTraverseM(G);break;
case 3:BFSTraverseM(G);break;
case 0:ch1='n';break;
default:printf("\t\t输入错误！请重新输入！\n");
}
}
}

void CreateMGraph(MGraph *G)
{ 
int i,j,k;
char ch1,ch2;
printf("\t\t请输入顶点数和边数(输入格式为:顶点数,边数):\n\t\t");
scanf("%d,%d",&(G->n),&(G->e));
printf("\t\t请输入顶点信息(顶点号<CR>)每个顶点以回车作为结束:\n");
for(i=0;i<G->n;i++)
{ getchar();printf("\t\t");scanf("%c",&(G->vexs[i]));
}
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
G->edges[i][j]=0;
printf("\t\t请输入每条边对应的两个顶点的序号(输入格式为:i,j):\n");
for(k=0;k<G->e;k++)
{ getchar();
printf("\t\t请输入第%d条边的顶点序号：",k+1);
scanf("%c,%c",&ch1,&ch2);
for(i=0;ch1!=G->vexs[i];i++);
for(j=0;ch2!=G->vexs[j];j++);
G->edges[i][j]=1;
}
}

void DFSTraverseM(MGraph *G)
{int i;
 for(i=0;i<G->n;i++)
visited[i]=FALSE;
 for(i=0;i<G->n;i++)
if(!visited[i]) 
DFSM(G,i);
}
void BFSTraverseM(MGraph *G)
{
int i;
for (i=0;i<G->n;i++)
visited[i]=FALSE;
for (i=0;i<G->n;i++)
if (!visited[i]) 
BFSM(G,i);
}

void DFSM(MGraph *G,int i)
{
int j;
printf("\t\t深度优先遍历结点: 结点%c\n",G->vexs[i]);
visited[i]=TRUE;
for(j=0;j<G->n;j++)
if(G->edges[i][j]==1&&!visited[j])
DFSM(G,j);
}

void BFSM(MGraph *G,int k)
{ 
int i,j;
CirQueue Q;
InitQueue(&Q);
printf("\t\t广度优先遍历结点: 结点%c\n",G->vexs[k]);
visited[k]=TRUE;
EnQueue(&Q,k);
while (!QueueEmpty(&Q))
{ i=DeQueue(&Q);
for (j=0;j<G->n;j++)
if(G->edges[i][j]==1&&!visited[j])
{   printf("\t\t广度优先遍历结点:%c\n",G->vexs[j]);
visited[j]=TRUE;
EnQueue(&Q,j);
}
}
}
[url=http://www.9ite.cn]http://www.9ite.cn[/url]