Logo

Navigation
  • Home
  • Services
    • ERP Solutions
    • Implementation Solutions
    • Support and Maintenance Solutions
    • Custom Solutions
    • Upgrade Solutions
    • Training and Mentoring
    • Web Solutions
    • Production Support
    • Architecture Designing
    • Independent Validation and Testing Services
    • Infrastructure Management
  • Expertise
    • Microsoft Development Expertise
    • Mobile Development
    • SQL Server Database and BI
    • SAP BI, SAP Hana, SAP BO
    • Oracle and BI
    • Oracle RAC
  • Technical Training
    • Learn Data Management
      • Business Intelligence
      • Data Mining
      • Data Modeling
      • Data Warehousing
      • Disaster Recovery
    • Learn Concepts
      • Application Development
      • Client Server
      • Cloud Computing Tutorials
      • Cluster Computing
      • CRM Tutorial
      • EDI Tutorials
      • ERP Tutorials
      • NLP
      • OOPS
      • Concepts
      • SOA Tutorial
      • Supply Chain
      • Technology Trends
      • UML
      • Virtualization
      • Web 2.0
    • Learn Java
      • JavaScript Tutorial
      • JSP Tutorials
      • J2EE
    • Learn Microsoft
      • MSAS
      • ASP.NET
      • ASP.NET 2.0
      • C Sharp
      • MS Project Training
      • Silverlight
      • SQL Server 2005
      • VB.NET 2005
    • Learn Networking
      • Networking
      • Wireless
    • Learn Oracle
      • Oracle 10g
      • PL/SQL
      • Oracle 11g Tutorials
      • Oracle 9i
      • Oracle Apps
    • Learn Programming
      • Ajax Tutorial
      • C Language
      • C++ Tutorials
      • CSS Tutorial
      • CSS3 Tutorial
      • JavaScript Tutorial
      • jQuery Tutorial
      • MainFrame
      • PHP Tutorial
      • VBScript Tutorial
      • XML Tutorial
    • Learn Software Testing
      • Software Testing Types
      • SQA
      • Testing
  • Career Training
    • Career Improvement
      • Career Articles
      • Certification Articles
      • Conflict Management
      • Core Skills
      • Decision Making
      • Entrepreneurship
      • Goal Setting
      • Life Skills
      • Performance Development
      • Personal Excellence
      • Personality Development
      • Problem Solving
      • Relationship Management
      • Self Confidence
      • Self Supervision
      • Social Networking
      • Strategic Planning
      • Time Management
    • Education Help
      • Career Tracks
      • Essay Writing
      • Internship Tips
      • Online Education
      • Scholarships
      • Student Loans
    • Managerial Skills
      • Business Communication
      • Business Networking
      • Facilitator Skills
      • Managing Change
      • Marketing Management
      • Meeting Management
      • Process Management
      • Project Management
      • Project Management Life Cycle
      • Project Management Process
      • Project Risk Management
      • Relationship Management
      • Task Management
      • Team Building
      • Virtual Team Management
    • Essential Life Skills
      • Anger Management
      • Anxiety Management
      • Attitude Development
      • Coaching and Mentoring
      • Emotional Intelligence
      • Stress Management
      • Positive Thinking
    • Communication Skills
      • Conversation Skills
      • Cross Culture Competence
      • English Vocabulary
      • Listening Skills
      • Public Speaking Skills
      • Questioning Skills
    • Soft Skills
      • Assertive Skills
      • Influence Skills
      • Leadership Skills
      • Memory Skills
      • People Skills
      • Presentation Skills
    • Finding a Job
      • Etiquette Tips
      • Group Discussions
      • HR Interviews
      • Interview Notes
      • Job Search Tips
      • Resume Tips
      • Sample Resumes
 

C Algorithms – Graph Theory

By Exforsys | on September 15, 2011 |
C Algorithms

The graph theory refers to the study of graphs. A graph is a mathematical object that captures the notion of connection. For example, you want to connect two or more dots that could be considered a graph. Leonhard Euler is the inventor of graph theory, as he tried to solve the known problem of the Seven Bridges of Konigsberg.

The townspeople supposedly posed the question “Is it possible to take a walk through town, crossing each of the seven bridges just once, and ending up wherever you started?”

A representation of the bridges:

Euler realized that all the points on the island (for example) were equivalent as far Mobdro Download App the question was concerned, so the island as well as the banks and the promontory could be represented with single points:

Notation:

A graph G is a pair of sets V and E together with a function f : E -> V x V . The elements of V are the vertices (a.k.a. nodes or points) of G. The elements of E are the edges of G. The function f sends an edge to the pair of vertices that are its endpoints, thus f is known as the edge-endpoint function. This terminology is unfortunate since f is generally only a relation.

Connections generally come in two forms, Mobdro APK those that are non-directional (e.g. the bridges of Konigsberg) and those that have an implicit direction (e.g. from one dot to another dot only). To distinguish these two cases we really need to define two different kinds of graphs. Thus the term graph will determine an undirected graph, and the term of digraph will determine a directed graph.

Representation of graphs :

In practice, there are different ways to represent a graph:

  • adjacent list – Vertices are stored as records or objects, and every vertex stores a list of adjacent vertices. This data structure allows to store additional data on the vertices.
  • incidence list – Vertices and edges are stored as records or objects. Each vertex stores its incident edges, and each edge stores its incident vertices. This data structure allows to store additional data on vertices and edges.
  • adjacency matrix – A two-dimensional matrix, in which the rows represent source vertices and columns represent destination vertices. Data on edges and vertices must be stored externally. Only the cost for one edge can be stored between each pair of vertices.
  • incidence matrix – A two-dimensional Boolean matrix, in which the rows represent the vertices and columns represent the edges. The entries indicate whether the vertex at a row is incident to the edge at a column.

Example:

The following example, an incidence matrix, will be used later on:

 1234
10110
20001
30001
40000

If you look closely at the table from above, at the intersection of 1 with 1, 2 with 2 and so on, the value is 0 because it points to the same node. At the intersection of 1 with 2, the value is 1 which is correct, because we have a road from 1 to 2, but not from 2 to 1, so there the value is 0.

A visual representation of the graph:

Some real life examples of using graphs:

  • Shipping routes – The vertices are shipping hubs and the edges are the routes between them
  • Telecommunications networks – The vertices are computers on the network and the edges are the network connections between them
  • Disease transmission – The vertices are organisms which can carry the disease and the edges represent one organism spreading it to another
  • « « C Algorithms – Gnome Sort
    C Algorithms – Topological Sort » »

Author Description

Avatar

Editorial Team at Exforsys is a team of IT Consulting and Training team led by Chandra Vennapoosa.

Free Training

RSSSubscribe 394 Followers
  • Popular
  • Recent
  • C Algorithms – Depth-First Search (DFS)

    September 16, 2011 - 0 Comment
  • C Algorithms – Shell Sort

    September 10, 2011 - 0 Comment
  • C Algorithms – Counting Sort

    September 12, 2011 - 0 Comment
  • C Algorithms – Radix Sort

    September 10, 2011 - 0 Comment
  • C Algorithms – The Problem of Sorting the Elements

    September 8, 2011 - 0 Comment
  • C Algorithms – Bucket Sort

    September 13, 2011 - 0 Comment
  • C Algorithms – Topological Sort

    September 15, 2011 - 0 Comment
  • C Algorithms – Gnome Sort

    September 14, 2011 - 0 Comment
  • C Algorithms – Merge Sort

    September 12, 2011 - 0 Comment
  • C Algorithms – Insertion Sort

    September 9, 2011 - 0 Comment
  • C Algorithms – Dijkstra’s Algorithm

    September 17, 2011 - 0 Comment
  • C Algorithms – Breadth-First Search (BFS)

    September 16, 2011 - 0 Comment
  • C Algorithms – Depth-First Search (DFS)

    September 16, 2011 - 0 Comment
  • C Algorithms – Topological Sort

    September 15, 2011 - 0 Comment
  • C Algorithms – Gnome Sort

    September 14, 2011 - 0 Comment
  • C Algorithms – Comb Sort

    September 14, 2011 - 0 Comment
  • C Algorithms – Bucket Sort

    September 13, 2011 - 0 Comment
  • C Algorithms – Quick Sort

    September 13, 2011 - 0 Comment
  • C Algorithms – Merge Sort

    September 12, 2011 - 0 Comment
  • C Algorithms – Counting Sort

    September 12, 2011 - 0 Comment

Exforsys e-Newsletter

ebook
 

Related Articles

  • C Algorithms – Dijkstra’s Algorithm
  • C Algorithms – Breadth-First Search (BFS)
  • C Algorithms – Depth-First Search (DFS)
  • C Algorithms – Topological Sort
  • C Algorithms – Gnome Sort

Latest Articles

  • Project Management Techniques
  • Product Development Best Practices
  • Importance of Quality Data Management
  • How to Maximize Quality Assurance
  • Utilizing Effective Quality Assurance Strategies
  • Sitemap
  • Privacy Policy
  • DMCA
  • Trademark Information
  • Contact Us
© 2023. All Rights Reserved.IT Training and Consulting
This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish.AcceptReject Read More
Privacy & Cookies Policy

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary
Always Enabled
Necessary cookies are absolutely essential for the website to function properly. This category only includes cookies that ensures basic functionalities and security features of the website. These cookies do not store any personal information.
Non-necessary
Any cookies that may not be particularly necessary for the website to function and is used specifically to collect user personal data via analytics, ads, other embedded contents are termed as non-necessary cookies. It is mandatory to procure user consent prior to running these cookies on your website.
SAVE & ACCEPT