图

1、邻接矩阵

#include "stdafx.h"
#include<iostream>
using namespace std;
#define Max 100
typedef struct{
     char vertex[Max];
     int Edge[Max][Max];
     int numVertex,numEdge;
}Graph;

int Locate(Graph *g,char c)
{
    int i;
    for(i=0;i<g->numVertex;i++)
    {
        if(c==g->vertex[i])
            return i;
    }
}
void CreatGraph(Graph *g)
{
    int i,j;
    char p,q;
    int w;
    int m,n;
    cout<<"请输入图的定点数和边数:";
    cin>>g->numVertex>>g->numEdge;
    cout<<"请输入图的顶点:";
    for(i=0;i<g->numVertex;i++)
    {
        cin>>g->vertex[i];
    }
    for(i=0;i<g->numVertex;i++)
        for(j=0;j<g->numVertex;j++)
            g->Edge[i][j]=0;
    for(i=0;i<g->numEdge;i++)
    {
        cout<<"请输入图的边";
        cin>>p>>q;
        m=Locate(g,p);
        n=Locate(g,q);
        g->Edge[m][n]=1;
        g->Edge[n][m]=1;
    }
    
}
void PrintGraph(Graph *g)
{
    int i,j;
    cout<<"顶点:"<<endl;
    for(i=0;i<g->numVertex;i++)
        cout<<g->vertex[i];
    cout<<endl;
    cout<<"边:"<<endl;
    for(i=0;i<g->numVertex;i++)
    {
        for(j=0;j<g->numVertex;j++)
            cout<<g->Edge[i][j];
        cout<<endl;
    }


}
int _tmain(int argc, _TCHAR* argv[])
{
    Graph g;
    CreatGraph(&g);

    PrintGraph(&g);
    system("PAUSE");
    return 0;
}

2、邻接表

#include "stdafx.h"
#include<iostream>
using namespace std;
#define Max 100
typedef struct{
     char vertex[Max];
     int Edge[Max][Max];
     int numVertex,numEdge;
}Graph;
typedef struct EdgeNode{
    int positon;
    struct EdgeNode *next;

}EdgeNode;
typedef struct EdgeVertex{
    char name;
    EdgeNode * first;
}EdgeVertex,AdjList[Max];
typedef struct AdjGraph{
    AdjList adjlist;
    int numVertex,numEdge;
}AdjGraph;
int Locate(AdjGraph *g,char c)
{
    int i;
    for(i=0;i<g->numVertex;i++)
    {
        if(c==g->adjlist[i].name)
            return i;
    }
}

void PrintGraph(AdjGraph *g)
{
    int i;
    EdgeNode * p;
    for(i=0;i<g->numVertex;i++)
    { 
        cout<<g->adjlist[i].name<<":";
        p=g->adjlist[i].first;
        while(p)
        {
            cout<<p->positon;
                p=p->next;
        }
        cout<<endl;
    }


}
void CreatAdjList(AdjGraph *g)
{
    int i;
    char p,q;
    int m,n;
    EdgeNode * edgeNode;
    cout<<"请输入图的定点数和边数:";
    cin>>g->numVertex>>g->numEdge;
    cout<<"请输入图的顶点:";
    for(i=0;i<g->numVertex;i++)
    {
        cin>>g->adjlist[i].name;
        g->adjlist[i].first=NULL;
    }
    for(i=0;i<g->numEdge;i++)
    {
        cout<<"请输入图的边";
        cin>>p>>q;
        edgeNode=(EdgeNode *)malloc(sizeof(EdgeNode));
        m=Locate(g,p);
        n=Locate(g,q);
        edgeNode->positon=n;
        edgeNode->next=g->adjlist[m].first;
        g->adjlist[m].first=edgeNode;
    }
}
int _tmain(int argc, _TCHAR* argv[])
{

    AdjGraph g;
    CreatAdjList(&g);
    PrintGraph(&g);
    system("PAUSE");
    return 0;
}

3、广度优先遍历

void BFSTravel(AdjGraph *g)
{
    queue<int> q;
    int p;
    EdgeNode *node;
    int i;
    for(i=0;i<g->numVertex;i++)
    {
        visited[i]=false;;
    }
    for(i=0;i<g->numVertex;i++)
    {
        if(!visited[i])
        {
            q.push(i);
            visited[i]=true;
        while(!q.empty())
        {
            p=q.front();
            cout<<g->adjlist[p].name<<' ';
            node=g->adjlist[p].first;
            q.pop();
            while(node&&!visited[node->positon])
            {
                q.push(node->positon);
                visited[node->positon]=true;
                node=node->next;    
            }
        }
        }
    }

4、深度优先遍历
①递归

void DFS(AdjGraph *g,int i)
{
    EdgeNode *p;
    p=g->adjlist[i].first;
    visited[i]=true;
    cout<<g->adjlist[i].name<<' ';
    while(p)
    {
        if(!visited[p->positon])
        {
            DFS(g,p->positon);
        }
        p=p->next;
    }
}
void DFSTravel(AdjGraph *g)
{
    int i;
    for(i=0;i<g->numVertex;i++)
    {
        visited[i]=false;;
    }
    for(i=0;i<g->numVertex;i++)
    {
        if(!visited[i])
        {
            DFS(g,i);
        }
    }
}

②非递归

void DFSTravel(AdjGraph *g)
{
    int i;
    stack<int> s;
    EdgeNode *node;
    int p;
    for(i=0;i<g->numVertex;i++)
    {
        visited[i]=false;;
    }
    for(i=0;i<g->numVertex;i++)
    {
        if(!visited[i])
        {
            visited[i]=true;
            cout<<g->adjlist[i].name<<' ';
            s.push(i);
            p=s.top();
            node=g->adjlist[p].first;
            while(node||!s.empty())
            {   
                while(node)
                {
                    if(!visited[node->positon])
                    {
                      visited[node->positon]=true;
                      cout<<g->adjlist[node->positon].name<<' ';
                      s.push(node->positon);
                      node=g->adjlist[node->positon].first;
                    }
                    else
                        node=node->next;    
                }
                if(s.top())
                    node=g->adjlist[s.top()].first;
                s.pop();
            }
        }
    }

}

Dijkstra算法

void ShortPath(Graph *g)
{
    int * visited=new int[g->numVertex];
    int * path=new int[g->numVertex];
    int * p=new int[g->numVertex];
    int min;
    int i,j,m;
    int k;
    for(i=0;i<g->numVertex;i++)
    {
        visited[i]=0;
        path[i]=g->Edge[0][i];
        p[0]=0;
    }
    visited[0]=1;
    for(i=1;i<g->numVertex;i++)
    {
        min=inf;
        for(j=0;j<g->numVertex;j++)
        {
            if(!visited[j])
            {
                if(path[j]<min)
                {
                    min=path[j];
                    k=j;
                }
            }
        }
        visited[k]=1;
        for(m=0;m<g->numVertex;m++)
        {
            if(!visited[m]&&min+g->Edge[k][m]<path[m])
            {
                path[m]=min+g->Edge[k][m];
                p[m]=k;
            }
        }

    }
    for(i=0;i<g->numVertex;i++)
    {
         cout<<path[i]<<' ';
    }

}

Floyd-Warshall算法

void Floyd(Graph *g)
{
    int i,j,k;
    int A[20][20];
    int Path[20][20];
    stack<int> s;
    for(i=0;i<g->numVertex;i++)
        for(j=0;j<g->numVertex;j++)
        {
          A[i][j]=g->Edge[i][j];
          Path[i][j]=-1;
         }
      for(k=0;k<g->numVertex;k++)
          for(i=0;i<g->numVertex;i++)
              for(j=0;j<g->numVertex;j++)
              {
                  if(A[i][k]+A[k][j]<A[i][j])
                  {
                      A[i][j]=A[i][k]+A[k][j];
                      Path[i][j]=k;
                  }
              }

     for(i=0;i<g->numVertex;i++)
     {
         cout<<g->vertex[0]<<"-"<<g->vertex[i]<<":";
         cout<<g->vertex[0]<<"->";
         k=Path[0][i];
         while(k!=-1)
         {
             s.push(k);
             k=Path[0][k];

         }
         while(!s.empty())
            {
                cout<<g->vertex[s.top()]<<"->";
             s.pop();
            }
         cout<<g->vertex[i]<<' ';
         cout<<"Cost："<<A[0][i];
         cout<<endl;
     }

}

最小生成树Prime算法

void Prime(Graph *g)
{
    int *visited=new int[g->numVertex];
    int *dist=new int[g->numVertex];
    int i,j,k,sum;
    int min;
    for(i=0;i<g->numVertex;i++)
    {
        dist[i]=g->Edge[0][i];
        visited[i]=0;
    }
    visited[0]=1;
    sum=0;
    for(i=0;i<g->numVertex;i++)
    {
        min=9999;
        k=-1;
        for(j=0;j<g->numVertex;j++)
        {
            if(!visited[j]&&dist[j]<min)
            {
                min=dist[j];
                k=j;
            }
        }
     if(k!=-1)
     {
        sum=sum+min;
        visited[k]=1;
        for(j=0;j<g->numVertex;j++)
        {
            if(!visited[j]&&g->Edge[k][j]<dist[j])
            {
                dist[j]=g->Edge[k][j];
            }
        }
     }
    }
 cout<<"Cost:"<<sum<<endl;
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 216,402评论 6赞 499
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,377评论 3赞 392
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 162,483评论 0赞 353
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,165评论 1赞 292
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,176评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,146评论 1赞 297
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,032评论 3赞 417
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,896评论 0赞 274
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,311评论 1赞 310
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,536评论 2赞 332
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,696评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,413评论 5赞 343
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,008评论 3赞 325
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,659评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,815评论 1赞 269
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,698评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,592评论 2赞 353

推荐阅读更多精彩内容

  • 数据结构与算法（六），图
    图是一种比线性表和树更复杂的数据结构，在图中，结点之间的关系是任意的，任意两个数据元素之间都可能相关。图是一种多对...
    Alent阅读 2,306评论 1赞 22
  • 图的遍历与简单应用
    －DFS（Depth First Search）：深度优先搜索 访问完一个顶点的所有邻接点之后，会按原路返回，对应...
    Spicy_Crayfish阅读 2,836评论 1赞 0
  • 图结构
    https://zh.visualgo.net/graphds 浅谈图形结构https://zh.visualgo...
    狼之独步阅读 4,148评论 0赞 0
  • 基础-6：图的表示和遍历
    1 概述 图是数据结构中最复杂的形式，也是最烧脑的结构。无数的牛人乐此不疲地钻研，然而，时至今日，依然有很多问题等...
    CodingTech阅读 2,311评论 0赞 8
  • Flask Note 2
    用户第一次访问程序时,服务器会收到一个没有表单数据的 GET 请求,所以 validate_on_submit()...
    开罗酒吧阅读 224评论 0赞 1